CFL Pumping Lemma의 올바른 적용
나는 그 언어를 보여주는 것에 대한이 질문을 보았습니다. $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$문맥이 없지만 Peter Linz의 책에서는 선형 적이 지 않습니다. 선형 언어에 대한 별도의 펌핑 기본형 (Linz의 책에서 제공됨)으로 쉽게 수행 할 수 있지만 내 질문은 다릅니다.
분명히 이것은 CFL이고 그것을 위해 푸시 다운 오토 마톤을 구성 할 수 있습니다. 그러나 CFL에 펌핑 기본형을 적용하면 해당 언어에 속하지 않는 문자열을 펌핑 할 수 있다는 것을 알게됩니다. 즉, 해당 언어가 CFL이 아님을 의미합니다. 분명히 나는 뭔가 잘못하고 있습니다.
Linz에서 제공하는 "게임과 유사한"형식을 따르십시오. $w = a^mb^mc^{2m}$, $|w| \ge m$. 공격자는 여러 가지 분해를 선택할 수 있습니다.$w = uvxyz$, 그들은 다음과 같이 보일 수 있습니다.
- $v = a^k, y = a^l$: 경우 $|vxy|$ 안에 포함되어 있습니다 $a$의 문자열입니다. 펌프$i = 0$, 그리고 $w_0 = a^{m – (k + l)}b^mc^{2m}$ 평등이 더 이상 유효하지 않기 때문에 언어에있을 수 없습니다.
- $v = a^k, y = b^l$: 경우 $v$ 에 $a$ 부분, $x$ 에 걸쳐 $a$'모래 $b$'모래 $y$ 에 $b$부분. 다시 펌프$i = 0$. $w_0 = a^{m – k}b^{m – l}c^{2m}$ 언어가 될 수 없습니다.
이와 같은 경우가 더 있습니다. CFL PL의 적용에서 내가 잘못되는 부분은 무엇입니까?
답변
CFL의 펌핑 기본형은 다음과 같이 말합니다. $L$ CFL이고 상수가 있습니다. $N \ge 1$ 모두를 위해 $\omega \in L$ 와 $\lvert \omega \rvert \ge N$ 분열이있다 $\sigma = u v w x y$ 와 $\lvert v w x \rvert \le N$ 과 $v x \ne \varepsilon$ 그런 $u v^k w x^k y \in L$ 모든 $k \ge 0$.
(일반 언어에 대한 펌핑 기본형은 유사하며 아래 논의는 약간의 변경 사항이 적용됩니다).
당신은 모순으로 증명하고 싶습니다 $L$CFL이 아닙니다. 그래서 당신은 가정$L$CFL이고 기본형과 모순됩니다. 이는 구체적으로 다음을 의미합니다.
- 같이 $L$CFL이며 기본형을 충족합니다. 특히 상수가 있습니다.$N$ 그런 ...
- 기본형에 모든 긴 문자열이 명시되어 있으므로$L$ 나눌 수 있으므로 작업하기 쉬운 것을 자유롭게 선택할 수 있습니다.
- 보조 정리 상태가 일부 의 분할$\omega$그런 .... 모두를 위해 $k \ge 0$...; 기본형을 모순하려면 분할 작업이 없음 을 증명해야 합니다. 실제로, 당신은 당신의 주어진 부분을$\omega$( 모든 부문) 및 일부를 선택$k$언어로 된 문자열을 제공하지 않습니다. 이것을 케이스로 나누어야 할 수도 있습니다.
언어에 속하지 않거나 다음보다 짧은 문자열은 어떻게 되나요? $N$, 완전히 관련이 없습니다. 일부 문자열을 펌핑 할 수 있고 일부 값은$k$모든 문자열에서 작동합니다. 중요한 것은 하나의 문자열에 대해$\omega$(선택한 것) 어떤 부문도 하나의 값으로 작동 하지 않습니다.$k$(다시, 당신이 고른). 표제어는 주장이 그것 작동 모두 에, 충분히 문자열 일부 에 대한 부문 모두 $k$, 하나의 반례로 충분합니다. 무한한 예는 아무것도 증명하지 않습니다.