The NPDA animation allows the user to draw and run Nondeterminstic Push-Down Automata; all of the basics of drawing diagrams and running on input strings is as in the Finite Automata, with the differences as below. Go to your saved NPDA’s or draw a new one yourself!
Drawing NPDA’s
Five types of states exist, selected with the following keys when the state is selected:
- [↑] gives a pop state, which transitions based on the symbol popped from the stack, or Δ on an empty stack, via [ctrl]-[shift]-D.
- [→] gives a read state, which transitions based on the symbol read from the input string, or Δ for end-of-input, via [ctrl]-[shift]-D.
- [alt]-A gives a halt-and-accept state, which halts the current branch with a result of accept.
- [alt]-R gives a halt-and-reject state, which halts the current branch with a result of reject.
- [.] gives a generic state, which simply allows branching and additional flexibility on positioning when drawing diagrams.
Pushes to the stack are indicated on transitions: press [↓] to enter the symbols to be pushed.
Running NPDA’s
Nondeterminism is handled via branching: when more than one matching transition is available, you will be prompted to select one via [↑/↓], moving forward with [→]. Backtracking is performed via [←]. (Picture traversing a tree of branches extending rightward.)