푸시다운 자동 기계

위키백과, 우리 모두의 백과사전.
(푸시다운 오토마타에서 넘어옴)
이동: 둘러보기, 검색
푸시다운 자동 기계의 도표

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

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

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

관련 항목[편집]

바깥 고리[편집]