[Compiler] 9. Pushdown automata

 

Pushdown automata (PDA)

context-free language (CFL)은 Pushdown automata가 허용하는 language이다.

Roughly speaking : PDA == [ε-NFA + "a stack"]

- FSM 과 pushdown Schematic

• Finite state machine

• Pushdown automata

 

Stack이 왜 필요할까?

L = {(0^n)(1^n) | n >= 1}이 있다고 가정, CFL language이다.

이 때 몇 번까지 읽었는지 counting을 해주는 것이 stack의 역할이다.

Regular Language는 몇 번까지 읽었는지 counting을 할 수 없다.

 

Pushdown automata (PDA)

PDA는 7-tuple P = (Q, ∑, Γ, δ, q0, Z0, F)로 정의된다.

• Q : state의 유한개 집합
• ∑ : input symbol의 유한개 집합
• Γ : 유한 Pushdown 저장소 (스택), stack symbol, alphabet
• δ : transition fuction
• q0 : start state
• Z0 : stack의 start symbol, Z0 ∈ Γ
• F : final state의 유한 집합,  F ⊆ Q

 

δ : transition fuction

new stack top은 바뀔수도 아닐수도

δ(q, a, X) = {(p, Y), ... } -> 여러개인 경우 non-deterministric(결정적이지 않은, 하나로 가지 않는)

• state transition : q ->(a) p
• a : next input symbol
• X : current stack top symbol
• Y : replacement for X -> Γ*

Y = ?	Action
Y = ε	Pop(X)
Y = X	Pop(X) Push(X)
Y = Z1Z2...Zk	Pop(X) Push(Zk) Push(Z_(k-1)) ... Push(Z1)

• δ(q, a, X) = {
  
  • (P, Y) -> pop(X)
  • (P, X) -> unchang
  • (P, Z1....Zk) -> Pop(X), Push(Zk)...Push(Z1)

 

Example of PDA

Lwwr = { w(w^R) | w ∈ (0 + 1)*} = {ε, 00, 0110, 1111, 0000, ...}

• R : Reverse
• 언제까지 기억을 해뒀다가 reverse해야한다.

Lwwr을 CFG로 만들면

• S -> 0S0 | 1S1 | ε

Lwwr을 PDA로 구성

• P = (Q, ∑, Γ, δ, q0, Z0, F)
    = ({q0, q1, q2}, {0,1}, {0,1,Z0}, δ, q0, Z0, {q2})

 

Transition function of P

• δ(q0, 0, Z_0) = {(q0, 0Z_0)}
• δ(q0, 1, Z_0) = {(q0, 1Z_0)}
  // 앞의 표에서 3번째 경우, Y = 0Z_0 일 때 -> pop(Z_0), push(Z_0), push(0)
• δ(q0, 0, 0) = {(q0, 00)}
• δ(q0, 0, 1) = {(q0, 01)}
• δ(q0, 1, 0) = {(q0, 10)}
• δ(q0, 1, 1) = {(q0, 11)}
  
  
• δ(q0, ε, 0) = {(q1, 0)}
• δ(q0, ε, 1) = {(q1, 1)}
• δ(q0, ε, Z_0) = {(q1, Z_0)}
  
  
• δ(q1, 0, 0) = {(q1, ε)}
• δ(q1, 1, 0) = {(q1, ε)}
  
• δ(q1, 0, 0) = {(q1, ε)}
  // Y = ε -> pop(0)
• δ(q1, ε, Z_0) = {(q2, Z_0)}

 

PDA as a state diagram

표현력 : DFA = NFA

but

표현력 : NPDA > DPDA

 

How does the PDA for Lwwr work on input "1111"?

 

Language L accepted by PDA P

1. input을 다 읽었을 때, final state에 도달했을 때

• L(P) = {w | (q0, w, Z_0) =*> (q, ε, A)}, q ∈ F

2. input을 다 읽었을 때, PDA의 stack이 비었을 때

• L(P) = {w | (q0, w, Z_0) =*> (q, ε, ε)}, any q ∈ Q

* final state와 empty stack은 equivalent하다고 한다.

 

Deterministic PDA

PDA는 deterministic 하다.

• δ(q, a, X) 일 때, 특정 상황에서 한 가지만 선택할 수 있다.
  a를 입력받았을 때는 a로만(ε이 없어야 함) state transition
  ε이 있다면 ε으로만 transition
  => 특정 상황에서 최대 한가지만 선택할 수 있다.
• 어떤 ∑의 a가 δ(q, a, X) 일 때 non-empty라면, δ(q, ε, X)는 반드시 empty이어야 한다.
  

 

Deterministic PDA and Nondeterministic PDA

Non-deterministic PDA (NPDA)는 deterministic PDA(DPDA)보다 훨씬 많은 표현을 할 수 있다.

• context-free language는 DPDA를 accept할 수 없다.

Deterministic Context Free Language (DCFL)

• CFL보다 더 적은 것을 인지한다.