일반 아닌 그 언어의 예는 다음과 같습니다왜 {a^nb^n | n> = 0} 정규 아닌가요? 내가 거기 복용 해요 CS 과정에서
{a^nb^n | n >= 0}
내가 어떤 유한 상태 오토 마톤/기계 쓸 수 없습니다 이후 일반 아니라는 것을 이해할 수 유효성을 검사하고 메모리 구성 요소가 없기 때문에이 입력을 허용합니다. (제발 내가 틀렸다면 제발 정정 해주세요)
wikipedia entry on Regular Language도이 예제를 나열하지만 그것이 정규적이지 않은 이유를 (수학적으로) 증명하지는 않습니다.
누구든지이 사실을 깨닫고 이에 대한 증거를 제공하거나 나에게 좋은 자료를 가르쳐 줄 수 있습니까?
당신이 찾고있는 것은 Pumping lemma for regular languages입니다. |
하자 L = {A m B m :
예 : 여기
은 정확한 문제가있는 example입니다 m ≥ 1}.
그러면 L은 규칙적이지 않습니다.
증명 : Pumping Lemma에서 n을 n이라고하자.
w = a n b n으로합시다.
w = xyz는 Pumping Lemma와 동일하게합니다.
따라서 xy z ∈ L이지만 xy z에는 b보다 a가 더 많이 포함되어 있습니다.
'a'와 'b'기호가 동일한 순서로 '카운트되는'유한 상태 머신을 작성할 수 없기 때문에 요컨대, FSMs는 '셀 수 없다'. FSM을 상상해보십시오. 얼마나 많은 주에서 기호 'a'를 주겠습니까? 얼마나 많은 'b'? 입력 시퀀스에 더 많은 것이 있다면?
X가 정수 값인 X가있는 < = X가있는 경우, 많은 FSM을 준비 할 수 있습니다 (상태는 많이 있지만 유한 번호 임). 그러한 언어는 규칙적입니다.
유한 상태 오토 마톤에는 데이터 구조 (스택)가 없습니다 - 푸시 다운 오토 마톤의 경우처럼 메모리. 그래, 그것은 당신에게 어떤 'b'가 뒤따라 올 수 있지만 'a'의 정확한 양은 그 다음에 'b'가 없다.
감사합니다. 내가 뭘 찾고 있었는지. –
마지막 주장은 더 나은 설명이 필요합니다. x2yz 단어는 한 종류의 문자를 더 많이 포함하거나 (y가 b보다 많거나 그 반대 인 경우) 또는 b를 사용하면 문자 순서를 깨뜨릴 수 있습니다. –
불완전한 증명. x, y, z를 정의하지 않았습니다. x는 | xy | <= p, 여기서 p는 펌핑 길이입니다. (a | ab | b)에 기초한 y 문자열을 사용하여 증명을 세 가지 경우로 나누어야합니다. xy는 a보다 더 b보다 잘 구성 될 수 있습니다. x = a, y = b^n, z = b – oligofren