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

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

쉽게 풀면

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

왜 중요한가

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

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

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

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

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

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

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

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

조금 더 깊게 보면

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

주의할 점

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