### A pushdown automaton is a way to implement a context-free grammar in a similar way we design DFA for a regular grammar. A DFA can remember a finite amount of information, but a PDA can remember an infinite amount of information.

### A stack does two operations −**Push** − a new symbol is added at the top.**Pop** − the top symbol is read and removed.

**Push**− a new symbol is added at the top.

**Pop**− the top symbol is read and removed.

### Pushdown Automata

- A pushdown automaton (PDA) is a finite automaton equipped with a stack-based memory.
- Each transition
- is based on the current input symbol and the top of the stack,
- optionally pops the top of the stack, and
- optionally pushes new symbols onto the stack.
- Initially, the stack holds a special symbol Z0 that indicates the bottom of the stack.

### Our First PDA

- Consider the language L = { w ∈ Σ* | w is a string of balanced digits } over Σ = { 0, 1 }
- We can exploit the stack to our advantage:
- Whenever we see a 0, push it onto the stack.
- Whenever we see a 1, pop the corresponding 0 from the stack (or fail if not matched)
- When input is consumed, if the stack is empty, accept.

## 0 comments:

## Post a Comment