## 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 a
^{n}b^{n}n≥1 - DPDA for number of a(w) = number of b(w)
- DPDA for a
^{n}b^{n}c^{m}n,m≥1 - DPDA for a
^{n}b^{m}c^{c}n,m≥1 - DPDA for a
^{n}b^{n}c^{m}d^{m}n,m≥1 - DPDA for a
^{n}b^{2n}n≥1 - DPDA for a
^{n}b^{2n+1}n≥1 - DPDA for wcw
^{R}w ε (a,b)^{*} - NPDA for ww
^{R}w ε (a,b)^{*}