Pushdown Automaton

상위 문서: Context-Free Languages

개요

정규 언어를 다루기 위해서는 FA(Finite Automaton)으로 충분하지만, 그보다 더 일반적인 언어인 CFG(Context-Free Languages)를 다루기 위해서는 PDA(Pushdown Automaton)>가 사용된다. PDA는 FA의 한계를 보완하기 위해서 추가적인 기억 장치인 stack을 활용하며, 이를 통해서 추가적인 '기억'을 구현할 수 있다. 예를 들어 아래와 같은 언어를 고려해보자:

$L=\{w{w}^R|w\in \mathrm{\Sigma }*\}$

이는 아래와 같은 작동 과정을 거친다:

1. 입력의 앞부분 w를 스택에 차례로 push 한다.
2. w가 끝났다고 nondeterministically guess(추측)한다.
3. 이후 입력의 나머지 부분을 읽으며, 스택에서 pop한 심볼과 비교한다.
4. 모두 일치하고 스택이 비면 해당 문자열은 PDA에 의해서 accept된다.

이때, 모든 NFA는 PDA의 특수한 경우로 볼 수 있다. 왜냐하면 PDA는 스택을 가진 오토마타지만, 스택을 전혀 사용하지 않게 정의하면 그건 곧 NFA와 동일한 동작을 하기 때문이다. 이를 통해서 아래와 같은 명제가 성립한다:

Context-Free Languages $\supseteq$ Regular Languages

Formal Definition of nondeterministic PDA

PDA는 아래와 같은 5-튜플($Q,\mathrm{\Gamma },\mathrm{\Sigma },\delta ,q_0,F$)로 정의할 수 있다:

• $Q$: 유한 상태 집합
• $\mathrm{\Sigma }$: 입력 알파벳
• $\mathrm{\Gamma }$: 스택 알파벳
• $\delta$: $Q\times \mathrm{\Sigma }\to Q$: 전이 함수(transition function), 현재 상태와 입력 기호를 다음 상태로 매핑
  • $\delta :Q\times {\mathrm{\Sigma }}_{ϵ}\times {\mathrm{\Gamma }}_{ϵ}\to P(Q\times {\mathrm{\Gamma }}_{ϵ})$
  • 현재 상태, 입력 알파벳, 스택의 top 알파벳에 따라 여러 $(r,b)\in \delta (q,w,a)$ 쌍을 반환한다.
• $q_0\in Q$: 시작 상태(start state)
• $F\subseteq Q$: 수용 상태 집합(a set of accept states)

이때 전이함수는 nondeterministic PDA 위에서 정의되므로 주어진 전이 함수 $\delta (q,w,a)$는 여러 $(r,b)$ 쌍을 가질 수 있다. 이때 $(r,b)\in \delta (q,w,a)$는 현재 상태가 q이고, 입력 알파벳이 w, 스택의 top 알파벳이 a일 때, 상태 r로 전이하며 스택에서 a를 pop하고 b를 push한다는 것을 의미한다. 만약 $(r,b)\in \delta (q,w,a)$에서 $a=ϵ$이면 스택을 pop하지 않는 것이고, $b=ϵ$이라면 스택에 push하지 않는 것이다. 이때 PDA의 스택이 비었는지를 직접 검사하는 것은 불가능하지만, 특수기호 $ 를 스택 바닥에 push하여 비어있음을 간접적으로 확인할 수 있다.

Computation of a PDA

PDA P가 입력 $w=w_1{w}_2\cdots w_m$을 수용(accept)한다는 것은 일련의 상태열 $r_0,r_1,\cdots r_m$과 스택 문자열열 $s_0,s_1,\cdots ,s_m$이 존재해야 한다. 이를 위한 조건은 아래와 같다:

1. $r_0=q_0,s_0=ϵ$: PDA는 처음에 초기 상태 $q_0$에서 시작하고 스택이 비어있다.
2. For $i=0,1,\cdots ,m-1$, $(\mathrm{\exists }{a}_i,b_i\in {\mathrm{\Gamma }}_{ϵ})\wedge (t\in \mathrm{\Gamma }*)$ such that ($s_i=a_{i}t,s_{i+1}=b_{i}t)\wedge ((r_{i+1},b_i)\in \delta (r_i,w_{i+1},a_i))$
   • 아래는 이를 쉽게 풀이한 것이다:
   1. 현재 스택의 내용이 $s_i=a_{i}t$ 형토로 되어 있다면(즉, top에 $a_i$가 있다면)
   2. 입력 심볼 $w_{i+1}$를 읽고,
   3. PDA의 전이함수 $\delta$에 따라 $a_i$를 pop하고 $b_i$를 push하여 스택의 나머지 부분 t를 보존한다.
   4. 그 결과 PDA는 새로운 상태 $r_{i+1}$에 도달한다.
   • 즉, DA가 스택의 맨 위를 조작하며 상태를 바꾸는 한 단계의 이동 규칙을 수학적으로 적은 것이다.
3. $r_m\in F$: 마지막으로 PDA가 모든 입력을 처리한 후 accept 상태 집합 F에 속하는 상태에 도달해있다.

Computation Example

Figure 1은 아래 언어를 나타내는 언어의 구현을 나타낸 것이다:

$L=\{a^i{b}^j{c}^k|i,j,k\ge 0\wedge (i=j\vee i=k)\}$

즉, a,b,c의 개수 관계가 i=j 또는 i=k인 문자열을 인식한다. 아래는 Figure 1에 나타난 PDA에 대한 설명이다:

1. $q_1\to q_2$: 시작 시 스택에 기호 $ 삽입 (스택바닥표시).
2. $q_2$: a를 읽을 때마다 a를 push.
3. $q_2\to q_3$: $ϵ$ 전이를 통해 “a와 b 개수를 비교하는 경로”로 진입
4. $q_3$: b를 읽을 때마다 a를 popg하여 i=j인 경우를 처리.
5. $q_4$: i=k이므로 수용 상태에 계속 머무른다.
6. $q_5\sim q_7$: 다른 경로 (nondeterminism)로 두 경우 모두 처리 가능하도록 설계.

PDA and CFG

모든 CFG는 어떤 PDA에 의해 인식되며, 이는 CFG → PDA 변환이 가능하다는 뜻이다. 이때 CFG를 PDA로 변환하는 것은 아래와 같이 스택을 이용하여 실현된다:

1. 스택은 아직 남은 입력 문자열을 도출하기 위해 필요한 문장형식(sentential form)을 유지한다.
   • CFG에서 문장을 생성할 때에는 "시작 비단말기 S"에서 여러 변환 규칙을 걸치면서 생성된다.
   • PDA에서는 스택에 그 현재 문장형식(예: $S\to aSb\to aabb$) 의 “아직 처리되지 않은 부분”을 저장한다.
2. 스택의 top에 단말기가 있을 때, 그것이 현재 입력 문자열의 첫 글자와 비교한다.
   • 두 문자가 같다면 스택에서 pop하고 입력에서도 consume한다.
   • 같지 않다면 PDA의 그 “계산 경로(computation path)”는 실패한다.
3. 만약 스택의 top이 비단말기라면, CFG의 생성 규칙 중 하나를 비결정적(nondeterministically) 선택한다.
   • 만약 선택된 생성 규칙이 $A\to aBb$라면, 스택의 top인 $A$를 pop하고, $b,B,a$를 역순으로 push한다.
4. 스택의 내용이 다 처리되어 비면 PDA는 accept state 로 이동한다.

Some Details

CFG에서 만든 PDA는 아래와 같은 세 가지 핵심적인 상태를 가진다:

1. $q_{s}tart$: 시작 상태
   • 스택에 $\mathrm{\$}S$를 push한다.
   • 다음 상태는 $q_{loop}$이다.
2. $q_{loop}$: 반복 상태
   • 스택의 top이 단말기면 입력과 비교하여 “match” 후 pop한다.
   • 스택의 top이 비단말기면 CFG의 생성 규칙 중 하나를 비결정적으로 선택하여 스택을 확장한다.
   • 스택의 top이 $이면 $q_{accept}$로 이동
3. $q_{accept}$: Accept 상태
   • 스택이 완전히 비고 입력이 끝난 상태이다.

이때 만약 여러 symbol을 한꺼번에 push해야 할 때는, “extra states”를 임시로 만들어 연속 push를 구현한다.

CFG to PDA Example

아래와 같은 CFG가 주어졌다고 가정해보자:

$S\to aTb|b$
$T\to Ta|ϵ$

이를 구현하기 위해서는 $q_{start},q_{loop},q_{accept}$를 구현해야 하며, 스택을 CFG 규칙에 맞추어 조작해야 한다. 이는 figure 2를 관찰하면 어떻게 구현이 되었는지 잘 이해할 수 있다.

${\displaystyle }$ ${\displaystyle }$${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$