푸시다운 오토마타 (pushdown automaton (PDA))

한 줄 정의: 유한 오토마타에 스택 하나를 추가하여 임의 깊이의 중첩 구조를 인식할 수 있도록 확장한 계산 모델로, 문맥 자유 언어를 정확히 인식하는 능력을 가진다.

쉽게 풀면

푸시다운 오토마타는 유한 오토마타에 '스택'이라는 메모리를 하나 더 붙인 기계다. 이 스택 덕분에 여는 괄호를 만나면 쌓아두고 닫는 괄호를 만나면 꺼내는 식으로, 괄호의 짝이 맞는지 같은 중첩 구조를 판별할 수 있게 된다. 이것이 바로 문맥 자유 문법으로 정의되는 언어(문맥 자유 언어)를 정확히 인식할 수 있는 계산 모델이며, 프로그래밍 언어의 구문 분석기가 내부적으로 이런 스택 기반 동작 원리를 사용한다.

왜 중요한가

푸시다운 오토마타는 문맥 자유 언어라는 언어 계급을 정확히 규정하는 계산 모델이라, 컴파일러 이론과 프로그래밍 언어 설계뿐 아니라 이론 컴퓨터과학에서 계산 능력의 위계(촘스키 위계)를 논의할 때 빠지지 않는 기준점입니다. 자연어처리 분야에서도 문장의 중첩 구조를 다루는 파서를 설계할 때 이 모델의 개념이 이론적 근거로 자주 인용됩니다.

핵심 정리

푸시다운 오토마타(PDA)는 유한 오토마타에 스택(후입선출 메모리) 하나를 더한 계산 모형입니다. 형식적으로는 상태 집합 Q, 입력 기호 Σ, 스택 기호 Γ, 전이 함수 δ, 시작 상태, 시작 스택 기호, 수용 상태 집합의 7-튜플로 정의됩니다.
각 단계에서 입력 기호(또는 ε)와 스택 맨 위 기호를 보고 상태를 바꾸고 스택 맨 위를 다른 문자열로 바꿉니다. 수용 방식은 ‘수용 상태에서 끝남’과 ‘스택이 빔’의 두 가지가 있고 서로 같은 능력입니다.
PDA가 인식하는 언어의 집합이 정확히 문맥 자유 언어입니다. 문맥 자유 문법과 PDA가 동등하다는 결과는 1960년대 초 Chomsky(1962) 등이 보였습니다.
비결정적 PDA(NPDA)는 결정적 PDA(DPDA)보다 강합니다. 예컨대 회문 w wᴿ(가운데를 모르고 대칭을 맞추는 언어)는 NPDA는 인식하지만 DPDA는 못 합니다. 이 점이 유한 오토마타(결정/비결정이 동등)와 다릅니다.

예시로 보기

괄호의 짝이 맞는지 판별하는 PDA의 아이디어를 코드로 돌려 보았습니다. 여는 괄호는 스택에 쌓고, 닫는 괄호는 하나 꺼냅니다. 꺼낼 것이 없거나 끝에 남으면 거부합니다.

입력	결과	스택 최대 깊이
`(()())`	받아들임	2
`(()`	거부	2
`())(`	거부	1
`((()))`	받아들임	3

스택 깊이가 괄호 중첩의 깊이만큼 커져야 하므로 상태 수가 정해진 유한 오토마타로는 모든 깊이를 처리할 수 없습니다. 같은 이유로 PDA는 aⁿbⁿ(n ≥ 0)은 인식하지만, aⁿbⁿcⁿ은 스택 하나로 세 개의 개수를 동시에 맞출 수 없어 인식하지 못합니다(이 언어는 문맥 자유 언어가 아니며 펌핑 보조정리로 보입니다).

자주 하는 오해

오해	바로잡기
스택이 있으면 계산 능력이 무한하다.	스택 하나는 문맥 자유 언어까지입니다. 스택을 둘로 늘리면(또는 테이프를 쓰면) 튜링 기계와 같은 능력이 됩니다.
결정적 PDA와 비결정적 PDA는 같다.	능력이 다릅니다. 결정적으로 인식되는 언어는 결정적 문맥 자유 언어이고 더 좁습니다.
컴파일러의 파서는 임의의 PDA이다.	실제 파서(LL, LR 등)는 결정적 PDA에 가까운 방식이 주로 쓰입니다.
PDA는 프로그래밍 언어 구문에만 쓰인다.	자연어 구문 분석 모형, 형식언어 이론의 위계, 신경망의 표현력 비교 등에도 기준 모형으로 쓰입니다.

논문에서는 이렇게 쓰입니다

실제 논문에서

이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.

예시 문장

아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.

"구문 분석기는 푸시다운 오토마타의 동작 원리에 따라 스택을 이용해 중첩된 괄호와 블록 구조를 처리한다."

컴파일러의 구문 분석 과정이 스택 기반으로 동작하는 이론적 이유를 설명할 때 사용된다.

"자연어의 통사 구조를 모델링하기 위해 문맥 자유 문법과 이에 대응하는 푸시다운 오토마타 기반 파서를 사용하여 문장의 중첩된 구(句) 구조를 분석하였다."

자연어처리 연구에서 문장의 계층적 구조를 다루는 데 푸시다운 오토마타의 이론적 틀이 활용된 사례이다.

"제안된 신경망 기반 시퀀스 모델은 외부 스택 메모리를 추가함으로써 푸시다운 오토마타가 인식하는 언어 부류를 더 잘 학습하는 것으로 나타났다."

딥러닝 모델의 표현력을 논의할 때 전통적 계산 모델인 푸시다운 오토마타가 비교 기준으로 쓰인 예이다.

조금 더 깊게 보면

푸시다운 오토마타가 인식하는 언어 부류인 문맥 자유 언어는 촘스키 위계에서 정규 언어보다 상위에, 문맥 의존 언어보다 하위에 위치하며, 이 위계는 각 언어 부류를 인식하는 데 필요한 최소한의 계산 자원(메모리 구조)이 무엇인지를 보여줍니다. 결정적 푸시다운 오토마타와 비결정적 푸시다운 오토마타는 인식 능력이 서로 다르다는 점도 이론적으로 중요하게 다뤄지며, 실제 컴파일러의 구문 분석기는 이 중 결정적 모델에 가까운 방식을 주로 사용합니다.

주의할 점

푸시다운 오토마타는 스택 하나만 가지므로, 두 개 이상의 독립적인 셈을 동시에 해야 하는 언어(예: a^n b^n c^n 형태)는 인식할 수 없다는 한계가 있다.

헷갈리기 쉬운 용어

촘스키 위계의 계산 모형과 문법을 짝지어 보면 구분이 쉽습니다.

계산 모형	메모리	인식하는 언어 부류	대응 문법
유한 오토마타	상태만(유한)	정규 언어	정규 문법
푸시다운 오토마타	스택 하나	문맥 자유 언어	문맥 자유 문법
튜링 기계	무한 테이프	재귀적 가산 언어	무제한 문법

위계 전체는 촘스키 위계 페이지를 참고하세요.

참고 문헌

Sipser, M. (2013). Introduction to the Theory of Computation (3rd ed.). Cengage Learning.
Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Pearson.
Chomsky, N. (1962). Context-free grammars and pushdown storage. MIT Research Laboratory of Electronics Quarterly Progress Report, 65.

표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.