Push Down Automata Introduction
Push Down Automata are machines used to accept context free grammar/languages.
Structure of PDA:
Symbol | Meaning |
---|---|
Q | Set of States |
Σ | Input Alphabets |
δ | Output Function: Q*{Σ U ε}*τ -> Q * τ* |
Z | Bottom of Stack |
F | Final State |
τ | Stack Alphabet |
Types of PDA
There are two types of PDA:- Deterministic Push Down Automata aka DPDA
- Non Deterministic Push Down Automata aks NPDA
DPDA
We have shown the structure above.NPDA
The only difference is of output function:Output Function: Q*{Σ U ε}*τ -> 2 (Q * τ*)
Note: NPDA is more powerful than DPDA so we can't say for a given NPDA, a DPDA will exist
Here are some PDA examples
- DPDA for anbn n≥1
- DPDA for number of a(w) = number of b(w)
- DPDA for anbncm n,m≥1
- DPDA for anbmcc n,m≥1
- DPDA for anbncmdm n,m≥1
- DPDA for anb2n n≥1
- DPDA for anb2n+1 n≥1
- DPDA for wcwR w ε (a,b)*
- NPDA for wwR w ε (a,b)*