 | To insert a sample PDA into your document, select from the editor |
A pushdown automaton (PDA) is a state machine consisting of 6 components∶
Description | Math notation | Grafstate code |
|---|
 | Set of states Q |
| Q={s,a,q1,q2}. | Q={s,a,q1,q2} |
 | Input alphabet Σ |
| Σ={a,b}. | S={a,b} |
 | Stack alphabet Τ |
| Τ={$,a} | T={$,a} |
 | Transition |
| q1⟶q2∶b,a⟶ε | q1->q2:b,a->\e |
 | Starting state (q0) |
| q0=qs. | q0=qs |
 | Set of final states (F) |
| F={qf}. | F={q_f} |
The PDA uses a stack as its memory. A stack has 2 available operations∶
Operation | Action summary | Full description |
|---|
| pop(x) removes x from the top of the stack. | pop(x) takes one argument x, where x is either a symbol in the stack alphabet (Τ) or ε. pop(x) checks the stack to see if x can be popped. If so, then pop(x) removes x from the top of the stack and return TRUE. If x is a symbol that is not on the top of the stack, then pop(x) returns FALSE and the stack does not change. pop(ε) returns TRUE and has no effect on the stack. |
| | |
| push(x) adds x to the top of the stack. | push(x) takes one argument x, where x is either a symbol in the stack alphabet (Τ) or ε. If x ∈ Τ, then push(x) pushes x to the stack. push(ε) has no effect on the stack. |
The instruction part of each transition performs three operations∶
| read a symbol (or ε) from the input |
|
| pop a symbol (or ε) from the stack |
|
| push a symbol (or ε) to the stack |
|
The transition function δ takes 3 input parameters (a current state, a read symbol or ε, and a pop symbol or ε). Each transition produces 2 output parameters (a destination state and a push symbol or ε). Since a PDA is non-deterministic, the output value is a set of (state, push) pairs. In other words, the transition function δ is defined as
The transition function for a PDA is defined using the Grafstate State-to-State Notation.
State-to-State Notation for PDAs
The Grafstate State-to-State Notation separates the part of the transition that defines the current and destination states (the state-to-state part) from the instruction part of the transition that makes a decision based on the input. The state-to-state part of a transition is expressed as qi->qj , where qi is the source state and qj is the destination state. For a PDA, the instruction part describes the read, pop, and push operations. The two parts of the instruction are separated by a colon. Thus, a transition in a PDA has the following form∶
qi->qj:r, pop -> push
where
| qi is the source state, |
|
| qj is the destination state, |
|
| r is the symbol to be read from input (or ε), |
|
| pop is the symbol to be popped from stack (or ε), and |
|
| push is the symbol to be pushed to stack (or ε). |
|
| | The state-to-state part of a loop from state q back to state q can be abbreviated as q: . In other words, a loop from q to q has the form |
q: r, pop -> push
 | Elements appearing to the left of a right arrow are input parameters to δ, and elements to the right of a right arrow are output parameters from δ. |
Syntax constraints for a PDA
Each line of a PDA is checked against the following constraints. If a line violates a constraint, then you will receive an error message.
| Q , S , and T must be nonempty sets. |
|
| q0 must be defined as a state in Q . |
|
| F must be a subset of Q . |
|
| The current state and destination state for each transition must be defined in Q . |
|
| The instruction part of each transition must have the form r, pop ⟶ push, where r is defined in S , pop is either defined in T or \e , and push is either defined in T or \e . |
|
| Q , S , T , q0 , and F must be defined exactly once. |
|
| You may give a PDA an optional title to be displayed on the state diagram using the title instruction.  title place a title here . |
| You can add a comment to any line of the PDA code by typing /* followed by the comment. |
| Example |
Below is Grafstate code for a PDA that recognizes the language {anbn∣n ≥ 0}∶
Code |
|---|
:+ pda P
Q={qs,q1,q2,qf}
S={a,b}
T={$,a}
q0=qs
F={qf}
qs->q1:\e,\e->$ /* mark the bottom of the stack
q1:a,\e->a /* record a's
q1->q2:\e,\e->\e /* prepare to read b's
q2:b,a->\e /* match the b's to the a's
q2->qf:\e,$->\e /* finish if the stack is empty
done. |
The preceding Grafstate code produces the following PDA∶
| Pushdown automaton |
|---|
 |
PThe Grafstate Simulator will show all steps of the computation performed by a PDA M when reading an input string w that you supply. The steps are visualized as a stack trace. Each step in the stack trace contains the following information∶
| The current and destination states (state-to-state) |
|
| The symbol read from the input on that transition |
|
| The symbol to be popped from the stack on that transition |
|
| The symbol to be pushed to the stack on that transition |
|
| The contents of the stack |
|
| The input symbols that have yet to be read |
|
A string is accepted by a PDA if the stack trace ends in a final state with no input symbols left to be read.
You can simulate a PDA with the command.
The command above produces the following stack trace∶
Simulation |
|---|
Input aaabbb |
Result ACCEPTED |
Explanation The following table shows the steps of the computation∶ |
| | | | | Remaining input |
|---|
qs | | | | | aaabbb | qs⟶q1 | ε | ε | $ | | aaabbb | q1⟶q1 | a | ε | a | | aabbb | q1⟶q1 | a | ε | a | | abbb | q1⟶q1 | a | ε | a | | bbb | q1⟶q2 | ε | ε | ε | | bbb | q2⟶q2 | b | a | ε | | bb | q2⟶q2 | b | a | ε | | b | q2⟶q2 | b | a | ε | | ε | q2⟶qf | ε | $ | ε | | ε |
|
The following table shows the other possible branches of the computation∶
Branch 1 | Branch 2 | Branch 3 |
|---|
qs⟶q1∶ ε, ε⟶$
q1⟶q2∶ ε, ε⟶ε
q2⟶qf∶ ε, $⟶ε | qs⟶q1∶ ε, ε⟶$
q1⟶q1∶ a, ε⟶a
q1⟶q2∶ ε, ε⟶ε | qs⟶q1∶ ε, ε⟶$
q1⟶q1∶ a, ε⟶a
q1⟶q1∶ a, ε⟶a
q1⟶q2∶ ε, ε⟶ε |
|
Pushdown automaton∶ P
| To simulate an PDA from the menus, right-click on the state diagram and select Simulate. |