[계산이론](14)[pushdown automata]

 

pushdown automata

NFA + stack처럼 행동
(만약 stack이 가물가물하면 [[5 자료구조 정리]] 참고)
PushDownAutomata (PDA)

• NFA
  nondeterministic하다
  물론, deterministic한 DPDA가 있지만, 이건 일반적인 PDA(NPDA)보다 힘이 약하다
• stack
  stack의 크기는 무한
  top에서 쓰거(push)나 읽은 후 지울(pop) 수 있음
  -> 무한한 정보를 저장 가능

 

수학적 정의

정의 ($Q$, $\sum$, $\Gamma$ $\delta$, $q_0$, $F$)

• $Q$: 상태의 유한 집합
• $\sum$: input alphabet의 유한 집합
• $\Gamma$: stack alphabet의 유한 집합
• $\delta$: transition function
  $\delta : Q \times \sum_{ε} \times \Gamma_{ε} \rightarrow P(Q \times \Gamma_{ε})$
  즉, input과 stack을 보고 다음 행동과 stack을 결정하겠다는 뜻이다!
• $q_0$: start state
  $q_0 \in Q$
• $F$: accept state
  $F ⊆ Q$

push: 스택에 새로운 문자 집어넣기
    δ(q1, 0, ε) = (q1, 0)
        q1에서 0을 읽었으면 스택의 비어있는 top(ε)에 0을 집어넣어라
pop: 스택의 top문자 지워버리기
    δ(q1, 1, 0) = (q1, ε)
        q1에서 1을 읽었으면 스택의 top에 0이 있다면 지워버려라(ε)

 

PDA의 계산

r0 = q0이고, stack은 비어있는채로 시작
각 trans에 맞게 이동
만약 모든 문자를 소비했고 accept state라면 accept

어떻게 stack이 비어있음을 알까?

물론 accept 조건엔 stack이 비어있음은 없으나, language를 표현하는 과정에서 필요하다. 따라서 이걸 알아야 하는데...
-> $로 구분하자!
만약 처음에 $를 stack에 넣고 모든 연산이 끝난 후 $만 스택에 남아있다면 그 스택은 빈 것이다!

예) 다음과 같은 PDA가 주어질 떄,

• 0011을 accept하는지 판단해라
  stack과 input의 상태를 차근차근 보면,

    input: {0 0 1 1}, stack: {           }, state: q1
    input: {0 0 1 1}, stack: {         $ }, state: q2
    input: {  0 1 1}, stack: {       0 $ }, state: q2
    input: {     1 1}, stack: {    0 0 $ }, state: q2
    input: {        1}, stack: {       0 $ }, state: q3
    input: {          }, stack: {         $ }, state: q3
    input: {          }, stack: {           } , state: q4

  즉, input을 모두 소비했을 때 accept state인 q4에 있으므로
  PDA accepts 0011
• 011을 accept하는지 판단해라
  stack과 input의 상태를 보면,

    input: {0 1 1}, stack: {           }, state: q1
    input: {0 1 1}, stack: {         $ }, state: q2
    input: {  1 1}, stack:  {      0 $ }, state: q2
    input: {      1}, stack: {        $ }, state: q3
    근데 더이상 stack에 읽을 0이 없으니
    갈 곳이 없어서 die...

  즉, input을 다 못 소비하고 죽었으므로
  PDA doesn't accept 011

nondeterminism의 이용

${a^ib^jc^k \ | \ i,j,k\ge 0, and \ i=j \ or \ i=k}$를 PDA로 나타내고 싶으면?
-> NFA 떄와 마찬가지로 ε를 이용해 i=j, i=k조건을 동시에 따라가보자!

이 PDA는 q2를 기점으로 ε,ε→ε를 통해 2가지 분기로 나뉜다
이때 ε,ε→ε는 어떤 input도 소비하지 않고 stack도 건들지 않은
완전히 동등한 분기를 만든다.

즉 nondeterminism을 사용해 마치 regular expression의 union마냥 행동 가능