Automata

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:
  1. Deterministic Push Down Automata aka DPDA
  2. 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
  1. DPDA for anbn n≥1
  2. DPDA for number of a(w) = number of b(w)
  3. DPDA for anbncm n,m≥1
  4. DPDA for anbmcc n,m≥1
  5. DPDA for anbncmdm n,m≥1
  6. DPDA for anb2n n≥1
  7. DPDA for anb2n+1 n≥1
  8. DPDA for wcwR w ε (a,b)*
  9. NPDA for wwR w ε (a,b)*




Quantitative Aptitude
Reasoning
Programming
Interview