Pushdown Automaton 문서 원본 보기

[[분류:계산 이론 개론]]
[[분류:컴퓨터 공학]]
상위 문서: [[Grammars#Context-Free Languages#Pushdown Automaton|Context-Free Languages]]

==개요==
정규 언어를 다루기 위해서는 FA(Finite Automaton)으로 충분하지만, 그보다 더 일반적인 언어인 CFG(Context-Free Languages)를 다루기 위해서는 PDA(Pushdown Automaton)<ref>해당 문서에서는 특별한 언급이 없는 이상 nondeterministic PDA를 기본으로 하여 서술한다.</ref>>가 사용된다. PDA는 FA의 한계를 보완하기 위해서 추가적인 기억 장치인 stack을 활용하며, 이를 통해서 추가적인 '기억'을 구현할 수 있다. 예를 들어 아래와 같은 언어를 고려해보자:
 <math>L = \{ww^R|w\in\Sigma*\}</math>
이는 아래와 같은 작동 과정을 거친다:
# 입력의 앞부분 w를 스택에 차례로 push 한다.
# w가 끝났다고 nondeterministically guess(추측)한다.
# 이후 입력의 나머지 부분을 읽으며, 스택에서 pop한 심볼과 비교한다.
# 모두 일치하고 스택이 비면 해당 문자열은 PDA에 의해서 accept된다.
이때, 모든 NFA는 PDA의 특수한 경우로 볼 수 있다. 왜냐하면 PDA는 스택을 가진 오토마타지만, 스택을 전혀 사용하지 않게 정의하면 그건 곧 NFA와 동일한 동작을 하기 때문이다. 이를 통해서 아래와 같은 명제가 성립한다:
 Regular Languages <math>\supseteq</math> Context-Free Languages

==Formal Definition of nondeterministic PDA==
PDA는 아래와 같은 5-튜플(<math>Q, \Gamma, \Sigma, \delta, q_0, F</math>)로 정의할 수 있다:
* <math>Q</math>: 유한 상태 집합
* <math>\Sigma</math>: 입력 알파벳
* <math>\Gamma</math>: 스택 알파벳
* <math>\delta</math>: <math>Q\times \Sigma \rightarrow Q</math>: 전이 함수(transition function), 현재 상태와 입력 기호를 다음 상태로 매핑
** <math>\delta: Q\times \Sigma_\epsilon \times \Gamma_\epsilon \rightarrow P(Q\times \Gamma_\epsilon)</math>
** 현재 상태, 입력 알파벳, 스택의 top 알파벳에 따라 여러 <math>(r,b) \in \delta(q,w,a)</math> 쌍을 반환한다.
* <math>q_0 \in Q</math>: 시작 상태(start state)
* <math>F \subseteq Q</math>: 수용 상태 집합(a set of accept states)
이때 전이함수는 nondeterministic PDA 위에서 정의되므로 주어진 전이 함수 <math>\delta(q,w,a)</math>는 여러 <math>(r,b)</math> 쌍을 가질 수 있다. 이때 <math>(r,b) \in \delta(q,w,a)</math>는 현재 상태가 q이고, 입력 알파벳이 w, 스택의 top 알파벳이 a일 때, 상태 r로 전이하며 스택에서 a를 pop하고 b를 push한다는 것을 의미한다. 만약 <math>(r,b) \in \delta(q,w,a)</math>에서 <math>a = \epsilon</math>이면 스택을 pop하지 않는 것이고, <math>b = \epsilon</math>이라면 스택에 push하지 않는 것이다. 이때 PDA의 스택이 비었는지를 직접 검사하는 것은 불가능하지만, 특수기호 $ 를 스택 바닥에 push하여 비어있음을 간접적으로 확인할 수 있다.

===Computation of a PDA===
PDA P가 입력 <math>w = w_1w_2\cdots w_m</math>을 수용(accept)한다는 것은 일련의 상태열 <math>r_0,r_1,\cdots r_m</math>과 스택 문자열열 <math>s_0,s_1,\cdots,s_m</math>이 존재해야 한다. 이를 위한 조건은 아래와 같다:
# <math>r_0=q_0, s_0=\epsilon</math>: PDA는 처음에 초기 상태 <math>q_0</math>에서 시작하고 스택이 비어있다.
# For <math>i=0,1,\cdots,m-1</math>, <math>(\exist a_i,b_i \in \Gamma_\epsilon) \land (t \in \Gamma*)</math> such that (<math>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>
#* 아래는 이를 쉽게 풀이한 것이다: 
## 현재 스택의 내용이 <math>s_i=a_it</math> 형토로 되어 있다면(즉, top에 <math>a_i</math>가 있다면)
## 입력 심볼 <math>w_{i+1}</math>를 읽고,
## PDA의 전이함수 <math>\delta</math>에 따라 <math>a_i</math>를 pop하고 <math>b_i</math>를 push하여 스택의 나머지 부분 t를 보존한다.
## 그 결과 PDA는 새로운 상태 <math>r_{i+1}</math>에 도달한다. 
#* 즉, DA가 스택의 맨 위를 조작하며 상태를 바꾸는 한 단계의 이동 규칙을 수학적으로 적은 것이다.
# <math>r_m \in F</math>: 마지막으로 PDA가 모든 입력을 처리한 후 accept 상태 집합 F에 속하는 상태에 도달해있다.

===Computation Example===
Figure 1은 아래 언어를 나타내는 언어의 구현을 나타낸 것이다:
 <math>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에 대한 설명이다:
# <math>q_1 \rightarrow q_2</math>: 시작 시 스택에 기호 $ 삽입 (스택바닥표시).
# <math>q_2</math>: a를 읽을 때마다 a를 push.
# <math>q_2 \rightarrow q_3</math>: <math>\epsilon</math> 전이를 통해 “a와 b 개수를 비교하는 경로”로 진입
# <math>q_3</math>: b를 읽을 때마다 a를 popg하여 i=j인 경우를 처리.
# <math>q_4</math>: i=k이므로 수용 상태에 계속 머무른다.
# <math>q_5\sim q_7</math>: 다른 경로 (nondeterminism)로 두 경우 모두 처리 가능하도록 설계.
<math></math>
<math></math>
<math></math>
<math></math>

==각주==