언어가 일반이 아닌 것을 직접 볼 수있는 방법

Question

L = {a^n b^n c^n},이 언어가 규칙적이지 않은 생산 규칙을 ​​보지 않고 어떻게 직접 말할 수 있습니까? 나는 펌핑 보조 정리를 사용할 수 있지만, 어떤 사람들은 이것이 규칙적인 것이 아니라는 문법을보고 있다고 말하고 있습니다. 그게 어떻게 가능해?

Answer 1

알파벳에는 3 개의 문자가 있습니다. 그것들 모두는 같은 변수에 의존합니다 : n. 자, 두 개 밖에 없다면 {a^n b^n}을 상상해보세요.이 생산물로 쉽게 작업을 수행 할 수 있습니다 :

S -> ab | aSb

하지만 그 중 3 개가 있으며 동일한 변수에 모두 연결할 수있는 방법이 없습니다. 두 가지 구문 범주를 사용해야하지만, 그렇게하면 연결이 끊어 지므로 각 범주에서 다른 문자열을 생성 할 수 있습니다. 그 (것)들을 연결하는 유일한 방법은 단 하나의 구문 범주를 가지고 있으며 그것은 불가능합니다.

당신은 할 수 없습니다

S를 -> ABC | aSbc

사실, 최종 문자열에는 구문 범주를 사용할 수 없으므로 문자열이 아닙니다. 다시 변환해야합니다. 그리고 그 시점에서 무엇을 할 수 있습니까?

aabcbc

또는 당신이 할 수 있습니다 : 당신은 할 수

aaSbcbc

첫 번째 문자열이며, 언어의 일부가 아닙니다. 두 번째는 아직 문자열이 아닙니다. 그러나 그것으로부터 허용 된 문자열을 관리 할 수 ​​없다는 것을 보는 것은 매우 쉽습니다.