[계산이론](15)[CFG->PDA]

CFG와 PDA는 동일한 힘을 가졌다
즉, CFG가 나타내는 CFL을 PDA도 accept할 수 있고
PDA가 recognize하는 language를 CFG가 만들 수 있다!

 

CFL -> PDA

A가 CFL이라 한다면 CFG가 존재한다
이 CFG가 생성하는 language를 어떤 PDA가 전부 accept하면 된다.

 

문제점

1. 어떤 rule을 따를지 어케앎?
   -> nondeterminism을 이용하셈
   모든 rule을 따르게 분기를 만든다
2. 변수가 stack 가운데에 박히면 어떻게 접근함?
   -> 변수를 stack 최상위에 위치하게 하셈
   변수 위의 terminal들은 input과 match시켜 stack에서 뺴버리기

변환 과정
    총 3개의 state($q_{start}, q_{loop}, q_{accept}$)로 만든다

1. 스택에 $(stack끝 보기용), S(start variable) 집어넣기
2. 각 CFG rule 처리하기 (이때는 string 통으로 취급)
   case 1: variable이 나올 때
       스택에서 변수 꺼내고 rule대로 처리하면 됨case 2: terminal이 나올 때
       스택에서 해당 기호와 input과 match해서 지워버리기case 3: $ 처리
       걍 $ 빼고 accept로 ㄱㄱ
3. string을 집어넣는 걸 각 문자를 집어넣게 분해

예) S -> 0S1 | ε 를 PDA로 나타내어라

1. $, S stack에 집어넣기

2. CFG rule 처리

3. string -> alphabet 처리

이렇게 CFG를 PDA로 변환하였다.

 

PDA -> CFG

복잡하다고 교수님께서 생략하심...