[계산이론] - (15) 푸시다운 오토마타 (Pushdown Automata)

 

 

 

 

문맥-자유 문법은 유한 오토마타로는 인식될 수 없으며, 푸시다운 오토마타에 의해서 인식될 수 있습니다.

푸시다운 오토마타는 오토마타와 비슷한 생김새를 지녔으나, 스택(Stack)을 추가로 사용합니다.

 

 

 

 

 

 

 

비결정적 푸시다운 오토마타 (NFDA)

푸시다운 오토마타는 다음과 같이 표현됩니다.

 

제어 유닛의 각 움직임은 입력 파일로부터 하나의 심벌을 읽고, 동시에 스택 연산을 통하여 스택의 내용을 바꿉니다.

제어 유닛의 각 움직임은 현재의 입력뿐 아니라, 현재 스택의 Top에 있는 심벌에 의하여 결정됩니다.

움직임의 결과는 제어 유닛의 새로운 상태와 스택의 톱에서의 변화입니다.

 

 

 

 

 

 

비결정적 푸시다운 인식기 (nondeterminisitc pushdown acceptor, npda)는 다음과 같이 정의됩니다.

$$M = (Q, \Sigma, \Gamma, \delta, q_0, z, F)$$
$Q$ : 제어 유닛의 내부 상태들의 유한 집합
$\Sigma$ : 입력 알파벳
$\Gamma$ : 심벌들의 유한집합으로, 스택 알파벳이라 불린다. (Stack Alphabet)
$\delta$ : $Q \times (\Sigma \cup \left\{\lambda \right\}) \times \Gamma \to 2^{Q \times \Gamma^{*}}$ 인 전이함수입니다. 단 $\delta$ 의 치역은 $Q \times \Gamma^{*}$ 의 유한 부분 집합만을 포함합니다.
$q_0 \in Q$ : 제어 유닛의 초기 상태.
$z \in \Gamma$ : 스택 시작 심벌
$F \subseteq  Q$ : 승인상태들의 집합

 

 

 

 

예시

한 npda의 전이 규칙들의 집합이 다음과 같은 전이를 포함하고 있다고 가정하겠습니다.

$$\delta(q_1, a, b) = \left\{(q_2, cd), (q_3, \lambda)  \right\}$$
만약 어떤 시점에서 제어 유닛이 상태 $q_1$ 에 있고,
읽혀진 입력 심벌이 a이면서,
스택의 Top에 위치한 심벌이 b라면 다음 이동이 발생합니다.

1. 제어 유닛은 상태 $q_2$ 로 들어가고, 스택의 top에 있는 문자 b가 제거되며, 문자열 cd가 스택에 들어옵니다. 
(들어오는 순서는 d, c 이며, 따라서 해당 전이 이후 스택에 Top에 위치하는 심벌을 c이다.)

2. 제어 유닛은 상태 $q_3$ 로 들어가고, 스택의 top에 있는 문자 b가 제거됩니다.

 

 

 

위 npda는 어떻게 동작할 것인지 생각해 보도록 하겠습니다.

우선 전이가 모든 가능한 입력 심벌과 스택 심벌의 조합에 대하여 규정되어 있지 않습니다.

 

규정되지 않은 전이는 공집합으로 간주되며 npda에 대한 종말 형상(dead configuration)을 나타냅니다.

 

중요한 전이들은 a가 읽혀질 때 스택에 1을 하나 추가하는 $\delta(q_1, a, 1) = \left\{ (q_1, 11)\right\}$ 과

b를 만날 때 1을 하나 제거하는 $\delta(q_2, b, 1) = \left\{( q_2, \lambda) \right\}$ 입니다.

 

이 두 단계로 인해 a와 b의 개수가 맞추어지며, 나머지 전이들까지 분석하면 npda에 의해 인식되는 문자열이 다음 언어에 속하는 것을 알 수 있습니다.

$$L = \left\{ a^{n}b^{n} : n \geq 0\right\} \cup \left\{ a \right\}$$

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

전이 그래프

npda를 표현하는데 전이 그래프를 이용할 수 있습니다.

전이 그래프에서는 간선에 세 개의 요소로 라벨을 부여합니다.

현재 입력 심벌
스택의 톱 심벌
전이를 통해 스택에 톱에 삽입될 문자열

 

 

위의 예시에 대한 전이 그래프를 그려보겠습니다.

 

 

 

 

그래프는 npda를 설명하는 데에는 편리하나, 증명을 하는 데에는 유용하지 않습니다.

내부 상태들뿐 아니라 스택의 내용을 기억하기 때문에, 형식적인 증명을 하는 데에는 전이 그래프를 사용하는 것이 어렵습니다.

 

이에 대한 대안으로, 문자열을 처리하는 동안 npda의 연속적인 형상(configuration)들을 설명하기 위한 간결한 표기법이 있는데, 바로 순간적 묘사입니다.

 

 

 

 

 

 

 

 

 

 

 

 

순간적 묘사  (instantaneous description)

문자열을 처리하는 데 있어서 관련된 요소들은 다음과 같습니다.

제어 유닛의 현재 상태
입력 문자열의 읽지 않은 부분
스택의 현재 내용

이들 모두 합하여 npda에서 가능한 모든 진행들을 결정합니다.

 

이때 다음과 같은 세 원소쌍을 순각적 묘사라 부릅니다.

$$(q, w, u)$$

$q$ : 제어 유닛의 상태
$w$ : 입력 문자열의 읽지 않은 부분
$u$ :  스택의 내용 (가장 왼쪽 심벌이 스택의 Top을 나타냄)

 

 

 

 

 

 

 

 

 

이동(move)

한 순간적 묘사로부터 다른 순간적 묘사로의 이동을 의미하며, 심벌 $\vdash $ 로 표기합니다.

또한 0번을 포함한 임의의 여려 단계들을 포함하는 이동들을 $\overset{*}{\vdash}$ 로 표기합니다.

 

 

 

 

예시

위의 예시에서 살펴보았던 다음 언어를 인식하는 푸쉬다운 오토마타를 계속해서 사용하도록 하겠습니다.

 $$L = \left\{ a^{n}b^{n} : n \geq 0\right\} \cup \left\{ a \right\}$$

 

이때 언어 aaabbb를 인식하는 과정을 살펴보도록 하겠습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

푸시다운 오토마타에 의해 인식되는 언어

$M = (Q, \Sigma, \Gamma, \delta , q_0, z, F)$가 비결정적 푸시다운 오토마타일 때, M에 의해 인식되는 언어는 다음과 같습니다.
$$L(M) = \left\{  w \in \Sigma^{*} : (q_0, w, z) \overset{*}{\vdash} \;(p, \lambda, u), \;\; p \in F, u \in \Gamma^{*}  \right\}$$

말로 설명하면 M에 의하여 인식되는 언어는 M이 다 읽고 종료상태에 놓일 수 있는 문자열들의 집합입니다.
이때 스택의 내용 u는 인식의 정의와 무관하므로, 종료 상태에서 남아있는 스택은 신경쓰지 않습니다.

 

 

 

예시

1.

다음 언어를 인식하는 NPDA를 구한 후, 문자열 bbaaaabb이 인식되는지 확인해보겠습니다.

$$L = \left\{ w \in \left\{ a,b\right\}^{*} : n_a(w) = n_b(w) \right\}$$

 

 

 

따라서 해당 문자열은 승인됩니다.

 

 

 

 

 

 

2.

다음 언어를 인식하는 NPDA를 구해보겠습니다.

$$L = \left\{ ww^{R} \in \left\{ a,b\right\}^{+} \right\}$$

 

 

 

 

 

 

 

 

 

 

 

 

 

 

푸시다운 오토마타와 문맥 자유 언어

모든 문맥 자유 언어에 대하여 그 언어를 인식하는 npda가 존재하고, 역으로 npda에 의하여 인식되는 언어는 문맥 자유 언어입니다.

 

 

 

 

문맥 자유 언어에 대한 푸시다운 오토마타

우선 문맥 자유 언어에 대하여, 이를 인식하는 npda가 존재하는 것을 알아보겠습니다.

 

논의를 단순하게 하기 위하여, 다음 가정들을 따르겠습니다.

언어는 Greibach 정규형인 문법에 의하여 생성됩니다.

언어에 속한 모든 문자열의 좌측우선 유도를 이용합니다.

구성하려는 pda는 문장 형태(sentential form)의 오른쪽 부분에 있는 변수들을 스택에 유지하면서 문자열 유도를 표현합니다.

단말(terminal)로 이루어진 왼쪽 부분은 읽은 입력과 일치시킵니다.

 

처음에는 스택에 시작 심벌을 추가한 후 시작합니다.

이후 생성규칙 $A \to ax$ 의 적용을 하기 위하여, 스택의 Top에 변수 A가 있어야 하며, 읽는 입력 심벌은 단말 a이어야 합니다.

스택의 변수는 제거되고, 변수들의 문자열 x로 교체됩니다.

 

 

 

이에 대한 일반적인 정리를 하기 전에 간단히 예제를 하나 살펴보겠습니다.

예시

아래 주어진 생성규칙들을 가지는 문법으로 생성된 언어를 인식하는 pda를 구성해보겠습니다.

$$S \to aSbb \;|\; a$$

 

이는 Greibach 정규형이 아니므로, Grebiach 정규형으로 바꿔보겠습니다.

$$S \to aSA \; | a$$

$$ A \to bB$$

$$ B \to b$$

 

이에 대응되는 오토마타는 총 3개의 상태 $\left\{ q_0, q_1, q_2 \right\}$ 를 가지며, $q_0$ 는 초기 상태, $q_2$ 는 승인 상태입니다.

 

 

먼저 스택에 시작 심벌을 넣습니다.

문법의 생성규칙 중 시작 심벌은 S이므로, 다음 전이를 통해 이를 스택에 놓습니다.

$$\delta (q_0, \lambda, z) = \left\{ q_1, Sz \right\}$$

 

 

모든 생성규칙들에 대응되는 전이를 표현합니다.

생성규칙 $S \to aSA$ 는 입력으로부터 $a$ 를 읽는 동안, 스택에서 $S$ 를 제거하고, $SA$ 를 추가함으로써, pda에서 시뮬레이트 될 것입니다.

이와 유사하게 생성규칙 $S \to a$는 pda로 하여금 스택에서 S를 제거하는 동안 a를 읽도록 합니다.

즉 이 둘은 pda에서 다음과 같은 전이로 표현됩니다.

$$\delta(q_1 , a, S) = \left\{ (q_1,SA), (q_1, \lambda)   \right\}$$

 

나머지 생성규칙들에 대해서도 유사하게 표현합니다.

$$\delta(q_1 , b, A) = \left\{ (q_1,B) \right\}$$

$$\delta(q_1 , b, B) = \left\{ (q_1,\lambda) \right\}$$

 

 

 

스택의 시작 심벌이 스택의 Top에 나타나면, 유도의 완료를 뜻하며, pda는 다음 전이에 의해 승인상태에 놓입니다.
$$\delta(q_1 ,\lambda, z) = \left\{ (q_2,\lambda) \right\}$$

 

 

 

 

 

 

정리

$\lambda$ 가 $L(G)$ 에 속하지 않는 모든 문맥 자유 언어에 대하여 L에 대한 Greibach 정규형인 문맥-자유 문법이 존재합니다.
$G = (V, T, S, P)$ 를 그러한 문법이라 하면, 이 문법의 좌측우선 유도를 시뮬레이트하는 npda를 구성합니다.

제시된 바와 같이, 시뮬레이션은 문장 형태(Sentential form)에서 처리되지 않은 부분은 스택에 놓여있도록 하고, 반면에 문장 형태의 단말 전위부는 입력 문자열의 대응되는 전위부와 일치하도록 행해집니다.

npda는 다음과 같이 만들어집니다.
$$M = (\left\{ q_0, q_1, q_f\right\}, T, V \cup \left\{ z\right\} ,\delta , q_0, z, \left\{ q_f \right\}    )$$
여기서 $z \notin V$ 입니다.
M의 입력 알파벳은 G의 단말(T)들과 동일하고,
스택 알파벳은 문법의 변수들의 집합(V)을 포함합니다.

전이 함수는 M의 첫 번째 이동 후 스택이 유도의 시작 심벌 S를 가지도록 다음 전이를 포함합니다.
$$\delta (q_0 , \lambda, z) = 
\left\{ (q_1, Sz)\right\}$$
(스택 시작 심벌 z는 유도의 끝을 감지할 수 있도록 하는 표식입니다)

이에 더하여 전이 규칙들의 집합은 다음을 만족하도록 구성합니다.

P에 속한 각 생성규칙 $A \to au$ 에 대하여 다음이 성립합니다.
$$(q_1, u) \in \delta(q_1, a, A)$$
해당 전이를 이용하여, M은 입력 a를 읽고 변수 A를 스택에서 제거하고 u로 교체합니다.

마지막으로 M이 승인 상태로 들어가게 하기 위하여 다음의 전이를 갖습니다.
$$(q_1, \lambda, z) = \left\{ (q_f,z )\right\}$$

만약 $\lambda \in L$ 이라면, 우리는 구성된 npda에 빈 문자열이 승인되도록 전이 $\delta(q_0, \lambda, z) = \left\{ q_f, z\right\}$ 를 추가합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

결정적 푸시다운 오토마타 (dpda)

결정적 푸시다운 인식기(deterministic pushdown accepter, dpda)는 이동에 있어서 선택의 여지가 없는 푸시다운 오토마타입니다.

푸시다운 오토마타 $M = (Q, \Sigma, \Gamma, \delta, q_0, z, F)$ 이 비결정적 푸시다운 오토마타의 정의와 동일하며,
다음의 제약 조건을 만족하면 결정적이라 합니다.
모든 $q \in Q$ ,  $ a \in \Sigma, \cup \left\{ \lambda \right\}$, 그리고 $b \in \Gamma$ 에 대하여,

1. $\delta(q, a, b)$ 는 많아야 한 개의 원소를 포함하고 (많아야 하나의 이동만이 가능하고)
2. 만약  $\delta(q, \lambda, b)$ 가 공집합이 아니라면, 모든 $c \in \Sigma$ 에 대하여, $\delta (q, c, b)$ 는 공집합이어야 합니다.
(람다 이동이 정의되었다면, 람다 이동 말고는 그 어떠한 이동도 없어야 한다는 뜻입니다)

 

첫 번째 조건은 단순히 주어진 입력 심벌과 스택의 Top 심벌에 대하여, 많아야 하나의 이동많이 행해질 수 있다는 것입니다.

두 번째 조건은 어떤 형상에서 $\lambda$ - 이동이 가능할 경우, 어떠한 입력을 사용하는 이동도 주어지지 않는다는 것입니다.

 

 

dpda의 어떠한 전이는 공집합, 즉 정의되지 않을 수도 있으며, 이는 종말 형상(dead configuration)이 있을 수도 있다는 뜻입니다.
이는 dpda의 정의에 영향을 주지 않으며, 결정성(determinism)에 대한 기준은 단지 모든 상황에서 많아야 하나의 가능한 이동만이 존재한다는 것입니다.