푸시다운 자동 기계

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

오토마타 벤 다이어그램

(각 레이어를 클릭하면 해당 글로 이동합니다.)

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

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

같이 보기 편집

이 글은 컴퓨터 과학에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다.