# Pushdown Automata Introduction

## Basic Structure of PDA

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.

Basically a pushdown automaton is −

**“Finite state machine” + “a stack”**

A pushdown automaton has three components −

- an input tape,
- a control unit, and
- a stack with infinite size.

The stack head scans the top symbol of the stack.

A stack does two operations −

**Push**− a new symbol is added at the top.**Pop**− the top symbol is read and removed.

A PDA may or may not read an input symbol, but it has to read the top of the stack in every transition.streaming film John Wick: Chapter 2 2017

A PDA can be formally described as a 7-tuple (Q, ∑, S, δ, q_{0}, I, F) −

**Q**is the finite number of states**∑**is input alphabet**S**is stack symbols**δ**is the transition function − Q × (∑ ∪ {ε}) × S × Q × S^{*}**q**is the initial state (q_{0}_{0}∈ Q)**I**is the initial stack top symbol (I ∈ S)**F**is a set of accepting states (F ∈ Q)

The following diagram shows a transition in a PDA from a state q_{1}to state q_{2}, labeled as a,b → c −

This means at state **q _{1}**, if we encounter an input string

**‘a’**and top symbol of the stack is

**‘b’**, then we pop

**‘b’**, push

**‘c’**on top of the stack and move to state

**q**.

_{2}### Instantaneous Description

The instantaneous description (ID) of a PDA is represented by a triplet (q, w, s) where

**q**is the state**w**is unconsumed input**s**is the stack contents

### Turnstile Notation

The “turnstile” notation is used for connecting pairs of ID’s that represent one or many moves of a PDA. The process of transition is denoted by the turnstile symbol “⊢”.

Consider a PDA (Q, ∑, S, δ, q_{0}, I, F). A transition can be mathematically represented by the following turnstile notation −

(p, aw, Tβ) ⊢ (q, w, αb)

This implies that while taking a transition from state **p** to state **q**, the input symbol **‘a’** is consumed, and the top of the stack **‘T’** is replaced by a new string **‘α’**.

**Note** − If we want zero or more moves of a PDA, we have to use the symbol **(⊢ ^{*})** for it.

There are two different ways to define PDA acceptability.

### Final State Acceptability

In final state acceptability, a PDA accepts a string when, after reading the entire string, the PDA is in a final state. From the starting state, we can make moves that end up in a final state with any stack values. The stack values are irrelevant as long as we end up in a final state.

For a PDA (Q, ∑, S, δ, q_{0}, I, F), the language accepted by the set of final states **F** is −

L(PDA) = {w | (q_{0}, w, I) ⊢^{*} (q, ε, x), q ∈ F}

for any input stack string **x**.

### Empty Stack Acceptability

Here a PDA accepts a string when, after reading the entire string, the PDA has emptied its stack.

For a PDA (Q, ∑, S, δ, q_{0}, I, F), the language accepted by the empty stack is −

L(PDA) = {w | (q_{0}, w, I) ⊢^{*} (q, ε, ε), q ∈ Q}

### Example

Construct a PDA that accepts **L= {0 ^{n} 1^{n} | n ≥ 0}**

### Solution

This language accepts L = {ε, 01, 0011, 000111, ……………………….. }

Here, in this example, the number of **‘a’** and **‘b’** have to be same.

- Initially we put a special symbol
**‘$’**into the empty stack. - Then at state
**q**, if we encounter input 0 and top is Null, we push 0 into stack. This may iterate. And if we encounter input 1 and top is 0, we pop this 0._{2} - Then at state
**q**, if we encounter input 1 and top is 0, we pop this 0. This may also iterate. And if we encounter input 1 and top is 0, we pop the top element._{3} - If the special symbol ‘$’ is encountered at top of the stack, it is popped out and it finally goes to the accepting state q
_{4}.

### Example

Construct a PDA that accepts L= { ww^{R} | w = (a+b)^{*} }

**Solution**

Initially we put a special symbol ‘$’ into the empty stack. At state**q _{2}**, the

**w**is being read. In state

**q**, each 0 or 1 is popped when it matches the input. If any other input is given, the PDA will go to a dead state. When we reach that special symbol ‘$’, we go to the accepting state q

_{3}**.**

_{4}If a grammar **G** is context-free, we can build an equivalent nondeterministic PDA which accepts the language that is produced by the context-free grammar **G**. A parser can be built for the grammar **G**.

Also, if P is a pushdown automaton, an equivalent context-free grammar G can be constructed where

**L(G) = L(P)**

In the next two topics, we will discuss how to convert from PDA to CFG and vice versa.

### Algorithm to find PDA corresponding to a given CFG

Input − |
A CFG, G= (V, T, P, S) |

Output − |
Equivalent PDA, P= (Q, ∑, S, δ, q_{0}, I, F) |

Step 1 | Convert the productions of the CFG into GNF. |

Step 2 | The PDA will have only one state {q}. |

Step 3 | The start symbol of CFG will be the start symbol in the PDA. |

Step 4 | All non-terminals of the CFG will be the stack symbols of the PDA and all the terminals of the CFG will be the input symbols of the PDA. |

Step 5 | For each production in the form A → aX where a is terminal and A, X are combination of terminal and non-terminals, make a transition δ (q, a, A). |

**Problem**

Construct a PDA from the following CFG.

**G = ({S, X}, {a, b}, P, S)**

where the productions are −

**S → XS | ε , A → aXb | Ab | ab**

**Solution**

Let the equivalent PDA,

P = ({q}, {a, b}, {a, b, X, S}, δ, q, S)

where δ −

δ (q, ε , S) = {(q, XS), (q, ε )}

δ(q, ε , X) = {(q, aXb), (q, Xb), (q, ab)}

δ(q, a, a) = {(q, ε )}

δ(q, 1, 1) = {(q, ε )}

### Algorithm to find CFG corresponding to a given PDA

Input − |
A CFG, G= (V, T, P, S) |

Output − |
Equivalent PDA, P = (Q, ∑, S, δ, q_{0}, I, F) such that the non- terminals of the grammar G will be {X_{wx} | w,x ∈ Q} and the start state will be A_{q0},F. |

Step 1 | For every w, x, y, z ∈ Q, m ∈ S and a, b ∈ ∑, if δ (w, a, ε) contains (y, m) and (z, b, m) contains (x, ε), add the production rule X_{wx} → a X_{yz}b in grammar G. |

Step 2 | For every w, x, y, z ∈ Q, add the production rule X_{wx} → X_{wy}X_{yx} in grammar G. |

Step 3 | For w ∈ Q, add the production rule X_{ww} → ε in grammar G. |