푸시다운 오토마타 시뮬레이터

유한 상태 기계에 스택 하나를 추가로 붙인 계산 모형입니다. 상태와 입력만으로는 괄호 짝맞추기 같은 언어를 판정할 수 없는데(정규언어의 펌핑 보조정리로 증명됨), 스택에 «지금까지 열린 괄호 수» 같은 무한한 정보를 쌓아 둘 수 있어 문맥자유언어까지 판정할 수 있습니다.

「상태, 입력기호, 스택꼭대기」세 가지를 보고 「새 상태, 새로 쌓을 문자열」로 바뀝니다. 스택꼭대기 기호 하나를 반드시 뽑아서 그 자리에 새 문자열을 쌓습니다 — 문자열이 비어 있으면(ε) 뽑기만 하는 것이고, 여러 글자면 여러 개를 쌓는 것입니다. 새로 쌓는 문자열은 왼쪽 글자가 맨 위에 옵니다.

입력을 소비하지 않고도 전이할 수 있다는 뜻입니다. 괄호를 다 처리한 뒤 스택 바닥만 남았을 때 수락 상태로 넘어가는 것처럼, 입력과 무관하게 스택 상태만 보고 움직이고 싶을 때 씁니다.

입력을 다 읽고(더 적용할 전이도 없고) 지금 상태가 수락 상태 집합에 있으면 수락입니다(최종상태로 수락 방식). 스택이 완전히 비어야 수락하는 «빈 스택으로 수락» 방식도 있지만 이 계산기는 다루지 않습니다.

진짜 PDA는 같은 상황에서 여러 전이가 동시에 가능한 비결정적 모형까지 포함하는데, 그러면 모든 경우의 수를 다 시도해 봐야 해 계산이 복잡해집니다. 이 계산기는 «입력을 소비하는 전이를 ε전이보다 먼저 시도한다»는 우선순위를 고정해 항상 하나의 경로만 따라가는 결정적 시뮬레이션을 합니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고 입력값은 이 기기에만 남습니다.