Session 4: �Equivalence of Pushdown automata and CFL

By

Dr. Ashok Kumar

Amity School of Engineering & Technology

N-pda for CFG

Conversion of CFG to NPDA

Amity School of Engineering & Technology

Construction Principles

• We will construct an nPDA that can in some way, carry out a leftmost derivation of any string in the language

​

• We assume that the given CFG is in Greibach Normal Form.

​

Amity School of Engineering & Technology

Construction Principles

• The PDA will represent the derivation by keeping the variables in the right part of the sentinel form on its stack, while the left part consisting entirely of terminals, is identical with the input read.

​

• To begin with we put the Start symbol S on top of the stack.

z

S

Stack

Amity School of Engineering & Technology

Construction Principles

Then for the productions of the type

z

Stack

A 🡪 a X

S

A

Amity School of Engineering & Technology

Construction Principles

Then for the productions of the type

z

A

Stack

A 🡪 a X

S

Current Input Symbol

Amity School of Engineering & Technology

Construction Principles

Then for the productions of the type

z

A

Stack

A 🡪 a X

S

Amity School of Engineering & Technology

Construction Principles

Then for the productions of the type

z

Stack

A 🡪 a X

S

Amity School of Engineering & Technology

Construction Principles

Then for the productions of the type

z

Stack

A 🡪 a X

S

X

Amity School of Engineering & Technology

Example #1

Construct a PDA that accepts the language generated by the Grammar with productions

S 🡪 a S bb | a

Step #1: Check whether the given Grammar is in GNF, if not convert it into GNF

Converting the the Grammar in to GNF we have:

S 🡪 a S A | a

A 🡪 b B

B 🡪 b

Amity School of Engineering & Technology

Generally

The PDA will have three states, q₀, q₁, q₂, out of which q₀ is the initial state and q₂ is the final state.

Step #2: First the Start Symbol S is pushed on to the Stack

δ ( q₀, λ , z) = { (q₁, Sz) }

Step #3: Now we will convert the productions in to transition function one by one:

Prod: 1

S 🡪 a S A

δ ( q1, a , S ) = { ( q1, SA ) }

Amity School of Engineering & Technology

Step #4:

Prod: 2

S 🡪 a (λ )

δ ( q1, a , S ) = { ( q1, λ ) }

Step #5:

Prod: 3

A 🡪 b B

δ ( q1, b , A ) = { ( q1, B ) }

Amity School of Engineering & Technology

Step #6:

Prod: 4

B 🡪 b (λ )

δ ( q1, b , B ) = { ( q1, λ ) }

Step #6:

For Entering in to the final state

δ ( q1, λ , z ) = { ( q2, λ ) }

Amity School of Engineering & Technology

The PDA for the given Grammar is:

CFG

S 🡪 a S A | a

A 🡪 b B

B 🡪 b

δ ( q₀, λ , z) = { (q₁, Sz) }

δ ( q1, a , S ) = { ( q1, SA ) }

δ ( q1, a , S ) = { ( q1, λ ) }

δ ( q1, b , A ) = { ( q1, B ) }

δ ( q1, b , B ) = { ( q1, λ ) }

δ ( q1, λ , z ) = { ( q2, λ ) }

q₂ is the final state

Equivalent PDA

Amity School of Engineering & Technology