나는 {a^i b^j | i = j }이 정규식이 아니므로 펌프 보조 정리로 증명할 수 있음을 알고 있습니다. 유사하게 나는 정규 표현식이 아닌 것을 증명하기 위해 펌프 보조 정리를 사용할 수있다. 그러나 나는 그런 언어가 실제로 규칙적이라고 말하는 유사한 문제를 보았다고 생각한다. 그리고 나는 보조 정리를 펌핑하는 것에 대한 나의 지식에 대해 확신하지 못하기 때문에이 나쁜 질문을하고 있습니다. 죄송합니다.이 언어는 정규입니까? {a^i b^j | i = j mod 19}
이것이 내가 증명하는 방법입니다.이 단어가 a^p b^(19k+p) 인 것은 분명히 언어입니다. 그럼 내가 펌프하면 펌프가 a^(p+1) b^(19k+p)이된다. 그것은 실패합니다. 그러므로, 그것은 규칙적인 것이 아닙니다.
내 증거가 맞습니까?
this answer을 살펴보십시오. 즉, 문자열을 올바르게 펌핑하지 않습니다. 펌핑 보조 정리에 따르면 문자열 w은 w = xyz으로 나눌 수 있습니다. 여기서 |xy| ≥ p 및 y은 비어 있지 않습니다. 그런 다음 모든 XY로 내가 Z를 문자열을 펌프 할 수 있습니까 ≥ 0
여기서 핵심, 펌핑 보조 정리가 문자열의 부문이 존재 함을 주장한다는 것입니다 w 이러한 특성을 만족, 당신은하지 않습니다 분열을 선택하고 xy로만 문자열을 펌핑 할 수 있음 i z.
그러나이 언어는 규칙적이어서 언어가 규칙적인지 증명하기 위해 펌프 보조 정리를 사용할 수 없으며 언어가 불규칙한 경우에만 증명할 수 있습니다 (충분하지만 충분하지는 않음). 언어가 규칙적임을 나타 내기 위해 언어를 정확히 설명하는 DFA, NFA 또는 정규 표현식을 만들 수 있습니다. 하나는 이러한 정규 표현식은 다음과 같습니다
(a^19)*(e|ab|aabb|aaabbb|...|a^18b^18)(b^19)*
곳 e은 빈 문자열입니다.
귀하의 언어가 오토마타 또는 계산의 입문 과정의 한 예라고 여겨집니다. 관심이 있으시면 Myhill-Nerode theorem은 입문 자료에서 다루어지지 않는 경우가 많지만,이 경우에는 규칙적인 확장의 증거가됩니다. b, bb, bbb, ..., b^19라는 고유 한 확장을 고려하면, 그것으로부터 쉽게.