Pushdown Automaton

상위 문서: Context-Free Languages

개요

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

[math]\displaystyle{ L = \{ww^R|w\in\Sigma*\} }[/math]

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

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

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

Regular Languages [math]\displaystyle{ \supseteq }[/math] Context-Free Languages

Formal Definition of nondeterministic PDA

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

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

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

Computation of a PDA

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

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

Computation Example

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

[math]\displaystyle{ L = \{a^ib^jc^k|i,j,k \ge 0 \and  (i = j \lor i = k)\} }[/math]

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

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

[math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math]