CFG를 NDPA로 변환하는 규칙은 무엇입니까?

Question

나는이 문법을 사용하여 FA를 정의 할 수 있습니다

S -> aSb 
S -> c 
S -> dA 
A -> Sd 

가 어떻게 첫 번째 규칙과 마지막을 관리합니까? 둘째로 나는 다른 상태 (마지막 상태)를 만들고 S와이 새로운 상태를 만들어야한다고 생각합니다. 세 번째 대신에 나는 상태 "A"를 만들고 "d"를 전달하여 S에 연결해야한다고 생각합니다.

Answer 1

CFG에서 PDA를 가져 오는 데 사용할 수있는 알고리즘이 있습니다. 예를 들어 하향식 및 상향식 파서를 살펴보십시오. PDAs가 CFG에 의해 생성 된 언어를 받아들이며, 그 반대의 경우도 그런 구조를 사용한다는 평범한 증거로 생각합니다.

대안은 문법에 의해 생성 된 언어를 이해하고 직접적으로 PDA를 설계하는 것입니다. 이것은 덜 기계적이지만보다 간결한 PDA를 산출 할 잠재력이 있습니다. 이 경로를 이동하려면, 우리는 먼저 안전하게위한 유일한 생산의 RHS로 대체 될 수있는 비 터미널을 인식하여 문법을 단순화 할 수 있습니다 :

S -> aSb 
S -> c 
S -> dSd // removed A -> Sd and replaced here 

방법이 문법이 작동합니까?

1. 두 번째 작품의 중간에 c이 있습니다.
2. c 왼쪽과 오른쪽에 일치하는 d이 있습니다.
3. 왼쪽에 a 초가 있고 c 오른쪽에 b 초가 붙습니다.
   1. 읽기 a들과 d의 당신이 c가 나타날 때까지 다음과 같이

   PDA를 작동합니다. 스택에있는 모든 것을 밀어 넣으십시오. c이 표시되면 다음 상태로 이동하고 c을 누르지 마십시오.

4. 읽기 b들과 d들까지, 스택에서 a들과 d들 터지는 : 이
   • 최상위 스택 기호 입력과 일치하지 않습니다 추락.
   • 스택에 심볼이있는 채 입력이 부족합니다. 추락.
   • 입력이 남아있는 스택 기호가 부족합니다. 추락.
   • 스택이 부족하여 동시에 입력되었습니다. 받아 들인다. 우리가 빈 스택에 의해 1 분기에 동의하면, 이러한 전환은 충분히

     q s  x q' s' 
     ------------------------------ 
     q0 a,d,Z a q0 aa,ad,aZ 
     q0 a,d,Z d q0 da,dd,dZ 
     q0 a,d,Z c q1 a,d,Z 
     q1 a  b q1 - 
     q1 d  d q1 - 
     

     :

여기 전환 테이블입니다. 빈 스택을 수락하거나 상태를 수락하려면 f(q1, Z, -) = (q2, Z)과 같은 전환을 추가하고 q2을 수락 할 수 있습니다. PDA는 비결정적으로 전환 할 것이며 입력이 고갈되지 않는 한 충돌 할 것입니다.