푸시다운 자동 기계

오토마타 벤 다이어그램

푸시다운 자동 기계의 도표

푸시다운 자동 기계(pushdown automaton, PDA)는 컴퓨터 과학에서 스택을 사용하는 자동 기계의 한 종류이다.

주로 기계에 의한 계산에 관련된 이론 분야에서 사용되며, 튜링 기계보다는 유한 상태 기계에 더 많이 사용된다. 또한 입력하면 형식 문법을 만들어 낼 수 있기 때문에, 구문 분석 디자인에도 사용된다.

'푸시다운'이라는 용어는 스택이 어떤 작업이 한 요인 때문에 정지될 시 그 요인을 음식점의 식기 분출 기계처럼 밀어내리는 역할을 하는 것을 의미한다.

같이 보기

• 문맥 자유 문법
• 유한 상태 기계

외부 링크

• non-deterministic pushdown automaton Archived 2007년 10월 31일 - 웨이백 머신
• JFLAP