푸시다운 자동 기계

3. 형식적 정의

푸시다운 오토마톤(PDA)은 다음과 같은 7-튜플로 정의된다.

:$M=(Q,\; \backslash Sigma,\; \backslash Gamma,\; \backslash delta,\; q\_\{0\},\; Z,\; F)$

여기서

• $Q$는 ''상태''의 유한 집합이다.
• $\backslash Sigma$는 ''입력 알파벳''이라고 하는 유한 집합이다.
• $\backslash Gamma$는 ''스택 알파벳''이라고 하는 유한 집합이다.
• $\backslash delta$는 ''전이 관계''이다.
• $q\_\{0\}\; \backslash in\; Q$는 ''시작 상태''이다.
• $Z\; \backslash in\; \backslash Gamma$는 ''초기 스택 기호''이다.
• $F\; \backslash subseteq\; Q$는 ''수락 상태'' 집합이다.

• $\backslash delta$는 $Q\; \backslash times\; (\backslash Sigma\; \backslash cup\; \backslash \{\backslash varepsilon\backslash \})\; \backslash times\; \backslash Gamma$를 $Q\; \backslash times\; \backslash Gamma^*$의 유한 부분 집합에 매핑하는 ''전이 함수''이다.

4. 문맥 자유 문법과의 관계

모든 문맥 자유 문법은 그에 상응하는 비결정적 푸시다운 오토마톤(NPDA)으로 변환될 수 있으며, 그 역도 성립한다.^[1] 이는 문맥 자유 문법이 푸시다운 오토마톤의 계산 능력과 정확히 일치함을 의미한다.

4. 1. 촘스키 위계

5. 튜링 기계와의 비교

푸시다운 자동 기계(PDA)는 두 개의 테이프를 가진 '제한된' 튜링 기계(TM)와 계산적으로 동등하다. 첫 번째 테이프에서 TM은 입력을 읽고 왼쪽에서 오른쪽으로만 이동하며 변경할 수 없다. 두 번째 테이프에서는 데이터를 '푸시'하고 '팝'할 수 있는데, 이는 문자열의 가장 왼쪽 문자를 삭제(팝)하거나 왼쪽에 추가(푸시)하는 동작으로 제한된다.

PDA가 TM보다 약한 이유는 '팝' 절차가 일부 데이터를 삭제하기 때문이다. PDA를 TM만큼 강력하게 만들려면 '팝'으로 손실된 데이터를 저장해야 한다. 두 번째 스택을 도입하면 이를 해결할 수 있는데, 이는 3개의 테이프를 가진 TM과 동일하다. 여기서 첫 번째는 읽기 전용 입력 테이프, 두 번째와 세 번째는 '푸시 및 팝'(스택) 테이프이다. 이러한 PDA가 주어진 TM을 시뮬레이션하려면, 첫 번째 테이프에 PDA의 입력을 제공하고 두 스택을 비운다. 입력 테이프에서 첫 번째 스택으로 모든 입력을 푸시한 후, 일반 TM처럼 진행한다. 테이프에서 오른쪽 이동은 첫 번째 스택에서 기호를 팝하고 두 번째 스택으로 푸시하는 것과 같고, 왼쪽 이동은 두 번째 스택에서 기호를 팝하고 첫 번째 스택으로 푸시하는 것과 같다. 따라서 2개의 스택을 가진 PDA는 모든 TM을 시뮬레이션할 수 있다.

푸시다운 오토마톤은 일반적인 유한 오토마톤과 다음 두 가지 점에서 다르다.

• 스택의 최상단을 사용하여 수행해야 할 상태 전이를 판단한다.
• 전이 실행의 일부로 스택 조작을 수행할 수 있다.

6. 확장

푸시다운 자동 기계의 한 종류인 일반화된 푸시다운 자동 기계(GPDA)는 한 번에 스택에 문자열 전체를 쓰거나 읽을 수 있다는 특징이 있다.

GPDA는 6-튜플 ($Q,\; \backslash Sigma,\; \backslash Gamma,\; \backslash delta,\; q\_0,\; F$)로 표현되는데, 여기서 $Q,\; \backslash Sigma,\; \backslash Gamma,\; q\_0,\; F$는 일반적인 푸시다운 자동 기계(PDA)와 동일하게 정의된다. 전이 함수 $\backslash delta$는 $Q\; \backslash times\; \backslash Sigma\_\{\backslash epsilon\}\; \backslash times\; \backslash Gamma^\{*\}\; \backslash longrightarrow\; P(Q\; \backslash times\; \backslash Gamma^\{*\})$로 정의된다.

GPDA의 계산 규칙은 PDA와 유사하지만, 기호 대신 문자열을 사용한다는 차이점이 있다. GPDA는 PDA와 동등하며, 이는 한쪽에서 인식되는 언어가 다른 쪽에서도 인식될 수 있음을 의미한다.

GPDA와 PDA의 동등성은 다음과 같은 시뮬레이션을 통해 증명할 수 있다. GPDA의 전이 $\backslash delta(q\_1,\; w,\; x\_1x\_2...x\_m)\; \backslash longrightarrow\; (q\_2,\; y\_1y\_2...y\_n)$ (여기서 $q\_1,\; q\_2\; \backslash in\; Q,\; w\; \backslash in\; \backslash Sigma\_\{\backslash epsilon\},\; x\_1,\; x\_2,\; \backslash ldots,\; x\_m\; \backslash in\; \backslash Gamma^\{*\},\; m\; \backslash geq\; 0,\; y\_1,\; y\_2,\; \backslash ldots,\; y\_n\; \backslash in\; \backslash Gamma^\{*\},\; n\; \backslash geq\; 0$)가 주어지면, PDA는 다음과 같은 전이를 구성한다.

:$\backslash begin\{array\}\{lcl\}$

\delta'(q_1, w, x_1) &\longrightarrow& (p_1, \epsilon) \\

\delta'(p_1, \epsilon, x_2) &\longrightarrow& (p_2, \epsilon) \\

&\vdots& \\

\delta'(p_{m-1}, \epsilon, x_m) &\longrightarrow& (p_m, \epsilon) \\

\delta'(p_m, \epsilon, \epsilon) &\longrightarrow& (p_{m+1}, y_n) \\

\delta'(p_{m+1}, \epsilon, \epsilon) &\longrightarrow& (p_{m+2}, y_{n-1}) \\

&\vdots& \\

\delta'(p_{m+n-1}, \epsilon, \epsilon) &\longrightarrow& (q_2, y_1)

\end{array}

6. 1. 교대 푸시다운 오토마톤 (APDA)

• $Q=Q\_\backslash exists\; \backslash cup\; Q\_\backslash forall$ 여기서 $Q\_\backslash exists\; \backslash cap\; Q\_\backslash forall=\backslash emptyset$

6. 2. 스택 오토마타

참조

_[1] 웹사이트 Pushdown Automata https://www.cs.odu.e[...] 2024-04-07
_[2] 서적 Computing with Foresight and Industry 2019
_[3] 논문 Stack Automata and Compiling
_[4] 논문 One-Way Stack Automata
_[5] 논문 Nonerasing Stack Automata
_[6] 논문 Alternation
_[7] 논문 Alternating Pushdown and Stack Automata
_[8] 서적 Computer Science – Theory and Applications