[일반] 오토마타 생성규칙의 한계가 있나요??

[익명(125.61)]

이거 어떻게 푸나요??

생성규칙으로 만들 수 없다는 걸 어떻게 알수 있나요??

[다믜(damhiya)]

L이 가능한건 좀 생각하면 금방 나올거고, 후자는 불가능하고 pumping lemma로 증명한다고 알려져 있음

[익명(223.53)]

네 혹시 후자가 안된다는거 좀 설명부탁드릴 수 있을까요 이런거 배우려면 뭐라 검색해야되나여?

[다믜(damhiya)]

나도 저기까진 제대로 안배워서. formal language, context free grammar, chomsky hierarchy 같은거 배우면 나옴

[다믜(damhiya)]

저 책을 일단 더 읽어보면 되지 않을까?

[익명(223.38)]

저 책은 과제모음이라 저게 끝이야ㅜ

[다믜(damhiya)]

https://en.m.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages

[다믜(damhiya)]

저 문제 답은 여기 있음

[익명(223.38)]

감사합니다아