Grab The Knowledge: Push down automaton notes

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.

A PDA can be formally described as a 7-tuple (Q, ∑, S, δ, q₀, 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₀ ∈ 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₁ to state q₂, labeled as a,b → c −

This means at state q₁, 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 stateq₂.

Terminologies Related to PDA

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₀, 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₀, I, F), the language accepted by the set of final statesF is −

L(PDA) = {w | (q₀, 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₀, I, F), the language accepted by the empty stack is −

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

Example

Construct a PDA that accepts L= {0ⁿ 1ⁿ | 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.
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.
If the special symbol ‘$’ is encountered at top of the stack, it is popped out and it finally goes to the accepting state q₄.

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₂, 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₄.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 grammarG. 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₀, 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, Xare 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₀, 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_yzb in grammar G.
Step 2	For every w, x, y, z ∈ Q, add the production rule X_wx → X_wyX_yx in grammar G.
Step 3	For w ∈ Q, add the production rule X_ww → ε in grammar G.Parsing is used to derive a string using the production rules of a grammar. It is used to check the acceptability of a string. Compiler is used to check whether or not a string is syntactically correct. A parser takes the inputs and builds a parse tree. A parser can be of two types − Top-Down Parser − Top-down parsing starts from the top with the start-symbol and derives a string using a parse tree. Bottom-Up Parser − Bottom-up parsing starts from the bottom with the string and comes to the start symbol using a parse tree. Design of Top-Down Parser For top-down parsing, a PDA has the following four types of transitions − Pop the non-terminal on the left hand side of the production at the top of the stack and push its right-hand side string. If the top symbol of the stack matches with the input symbol being read, pop it. Push the start symbol ‘S’ into the stack. If the input string is fully read and the stack is empty, go to the final state ‘F’. Example Design a top-down parser for the expression "x+yz" for the grammar G with the following production rules − P: S → S+X \| X, X → XY \| Y, Y → (S) \| id Solution If the PDA is (Q, ∑, S, δ, q₀, I, F), then the top-down parsing is − (x+yz, I) ⊢ (x +yz, SI) ⊢ (x+yz, S+XI) ⊢ (x+yz, X+XI) ⊢(x+yz, Y+X I) ⊢ (x+yz, x+XI) ⊢ (+yz, +XI) ⊢ (yz, XI) ⊢ (yz, XYI) ⊢ (yz, yYI) ⊢ (^z,YI) ⊢ (z, YI) ⊢ (z, zI) ⊢ (ε, I) Design of a Bottom-Up Parser For bottom-up parsing, a PDA has the following four types of transitions − Push the current input symbol into the stack. Replace the right-hand side of a production at the top of the stack with its left-hand side. If the top of the stack element matches with the current input symbol, pop it. If the input string is fully read and only if the start symbol ‘S’ remains in the stack, pop it and go to the final state ‘F’. Example Design a top-down parser for the expression "x+yz" for the grammar G with the following production rules − P: S → S+X \| X, X → XY \| Y, Y → (S) \| id Solution If the PDA is (Q, ∑, S, δ, q₀, I, F), then the bottom-up parsing is − (x+yz, I) ⊢ (+yz, xI) ⊢ (+yz, YI) ⊢ (+yz, XI) ⊢ (+yz, SI) ⊢ (yz, +SI) ⊢ (^z, y+SI) ⊢ (^z, Y+SI) ⊢ (^z, X+SI) ⊢ (z, X+SI) ⊢(ε, zX+SI) ⊢ (ε, YX+SI) ⊢ (ε, X+SI) ⊢ (ε, SI)