CFG는 String을 생성하고 PDA는 Input String을 인식한다. 관점은 다르지만 다음이 성립한다.

CFG에서 PDA로

핵심은 Stack에 현재 만들어야 할 Sentential Form을 저장하고 Leftmost Derivation을 모사하는 것이다.

  1. Stack에 Start Variable 를 넣는다.
  2. Stack Top이 Variable 이면 Production 하나를 Nondeterministically 선택하여 를 로 교체한다.
  3. Stack Top이 Terminal 이고 다음 Input도 이면 둘을 동시에 제거한다.
  4. Input과 Stack이 모두 비면 Accept한다.

Production 선택에는 Input을 소비하지 않는 ε-transition을 사용한다.

예제

Grammar

를 PDA로 모사한다. Input 에 대해 Stack의 를 로 두 번 확장하고, Terminal a를 Input과 Matching한다. 이후 를 선택하고 b를 Matching하면 Accept한다.

이 PDA의 Nondeterminism은 Grammar에서 어떤 Production을 선택할지에 대응한다.

PDA에서 CFG로

역방향 변환은 더 복잡하다. PDA가 State 에서 Stack Symbol 를 제거하여 State 로 갈 수 있는 모든 Input을 생성하는 Variable을 만든다.

라는 Variable은 “State 에서 시작해 Stack Top 를 제거하고 State 에 도달하게 하는 String”을 나타낸다.

PDA Transition이 Stack에 Symbol을 Push하면, 그 Symbol들이 이후 어떤 중간 State를 거쳐 Pop되는지 가능한 State Sequence를 Production에 반영한다. State가 유한하므로 Grammar도 유한하게 만들 수 있다.

동등성의 의미

동등하다는 것은 각 CFG에 같은 Language를 인식하는 NPDA가 있고, 각 NPDA에 같은 Language를 생성하는 CFG가 있다는 뜻이다. Grammar와 Automaton의 크기나 동작 방식이 동일하다는 뜻은 아니다.

Deterministic PDA와 CFG

모든 CFG에 대응하는 PDA는 Nondeterministic일 수 있다. Deterministic Context-Free Language는 CFL의 진부분집합이다. 예를 들어 일반적인 Programming Language Parser는 문법을 LL, LR과 같은 제한된 형태로 설계해 Deterministic Parsing을 가능하게 한다.

정리

  • CFG의 Variable 확장을 PDA Stack Rewrite로 모사할 수 있다.
  • Terminal은 Input과 Stack Top을 Matching하여 소비한다.
  • PDA에서 CFG로 갈 때 State Pair와 Stack Symbol을 Variable로 인코딩한다.
  • CFG와 NPDA는 정확히 CFL을 표현한다.

연습 문제

1번

Grammar 를 모사하는 PDA가 Input 을 처리하는 주요 Stack 단계를 적는다.

2번

CFG를 PDA로 변환한 모델에서 Variable Expansion Transition이 Input을 소비하지 않아야 하는 이유를 설명한다.

풀이

1번

Stack Top의 왼쪽이 먼저 처리된다고 보면 주요 변화는

과 같은 내용을 Stack에 만들고 Terminal을 Input과 Matching하는 과정이다. 두 번 을 선택한 뒤 를 선택하면 Input 전체와 일치한다.

2번

Production을 선택하는 것은 Grammar의 구조를 확장하는 내부 계산이며 아직 Terminal을 읽는 단계가 아니다. Input은 Stack Top이 Terminal이고 같은 Input Symbol을 만났을 때만 소비해야 Derivation의 Yield와 정확히 일치한다.