이 언어에는 PDA (Pushdown Automata)가 있습니까?

Question

언어이다 : {A ^N B ^(2N) C ^N | where n> = 0}

당신이 다음과 같이 처리 할 수 ​​있기 때문에 다음과 같이 처리 할 수 ​​있다고 생각합니다 : 스택 A에서 푸시 A, 푸시 B, 스택에서 세 번 각각 팝 3 번, 스택 C가없고 스택이 비어 있으면 true를 반환합니다. 그렇지 않으면 거짓을 반환합니다.

Answer 1

펌핑 보조 정리를 사용하여 상황에 맞는 언어가 아닌 것을 증명하십시오.

는 S가 ^P2P C ^{는 P}
그렇다면 우리 vxy, |vxy|<=p, |vy|>0 고려 B 및 UV ^I XY를 = 고려 ^{I L
에} Z 우리 가능성이

1. vxy = a ^j, jB ^K= P
2. vxy = A ^J, J + K < = P
3. vxy = B ^J, J < = P
4. vxy = B ^J C ^K , J + K = P <
5. vxy = C J, J = P <

어쨌든, 상수는 u 및 v이다. 이 단지 vxy에서 두 심볼이 될 수 있으며, 우리가 다음 u 또는 v

귀하의 제안 오토마타 사실 반환, AAAC 실패까지의 보여주기 위해 세 번째의 변수 금액을 필요하기 때문에 문자열은 L입니다. A의 B보다 두 배 많은 B가 있다고 보장 할 수는 없습니다.

Answer 2

이 언어는 컨텍스트 프리가 아니기 때문에 PDA가 존재하지 않습니다. 여기에 이것에 대한 간단한 증거가 있습니다. 이것은 inverse homomorphism (as mentioned in these slides) 하에서 context-free 언어가 닫혀 있다는 사실에 의존합니다.= {A ^N B ^2N C ^N 언어 L 주어

| N N에서}하는

H (B) = BB

H (C) = C

의 역을

• H (A)에서 정의 된 동형 H를 = 고려 L에 적용된이 유사 동형어는 언어이다. ^-1 (L) = {x in Σ * | h (x) ∈L}. h의 선택을 살펴보면, 이것은 언어입니다. {A ⁿ B ⁿ C ⁿ | n in N}. 이 언어는 컨텍스트가없는 언어의 표준적인 예입니다. Howver, CFL은 inverse homomorphism 하에서 닫히기 때문에 h ^-1 (L)은 context-free가 아니기 때문에, L은 context-free가 될 수 없다. 따라서 PDA가 없습니다.

  희망이 도움이됩니다.