0
저는 L = {a^n!}이라는 언어를 증명하려고합니다. | n> = 0}은 펌핑 보조 정리를 사용하여 컨텍스트 프리가 아닙니다. 하지만 난 uvxyz 자체로 나눌 방법에 붙어있다. 그것의 유일한 symol 때문에 나는 그것을 매우 까다롭게 찾습니다.펌핑 보조 정리를 사용하여 언어가 컨텍스트 프리가 아닌 것을 증명합니까?
A
답변
0
주어진 단어 w를 L에서 펌핑 한 결과 인 언어 P를 봅니다. | wy | wy | 다음 펌프는 모든 펌핑에 | vy | 기호.
반면에 두 계승 사이의 간격은 항상 커집니다. 분명히 예를 들어 (| vy | +2)! - (| vy | +1)! > | vy |. 그러나 이것은 P에 a^(| vy | +1) 사이에 어떤 단어가 있음을 의미합니다! 와 a^(| vy | +2)! 이 단어가 L이 아니므로 펌핑 조건이 위반됩니다.