PDA (Push Down Automata) | TOC

PDA (Push Down Automata)

Formal Defination:

Push Down Automata is a set of seven tupples.

PDA=(Q,Σ,𝜏,q0,z0,F,δ)

where:

Q is a set of states

Σ is set of input symbol

𝜏(tau) is set of stack symbol.

q0 is initial state

z0 initial stack symbol

F set of final state

δ is transition function

PDA (Push Down Automata)

A PDA is a way to implement a CFG in a similar way we design Finite Automata for Regular Grammar.It is more powerful than Finite State Machine.It is more powerful than Finite State Machine.Finite State Machine has a very limited memory but PDA has more memory. 

PDA = FSM + Stack

# Transition function in the case of PUSH

(q,a,x) → (q',AX)

Previous top (x)

Current top (A)

Ex: (q,a,x) → (q',AX)

# Transition function in the case of POP

(q,b,A) → (q',ε)

# Skip representation

(q,x,z) → (q',z)

δ: Q x Σ x 𝜏 → Q x 𝜏*

where : 𝜏* (A,X,ε,z)

Example:

# Construct a Push Down Automata

1. {aⁿ bⁿ | n>=1}

Strings such as {ab , aabb , aaabbb ..... }

Flow chart for logic:

where :

    Q = { qₒ , q₁}

    Σ = { a , b }

    𝜏 = { X , A }

    qₒ = qₒ

    zₒ = X

Suppose the string is aabb than δ will be

    δ( qₒ , a , x ) → ( qₒ , AX )

    δ( qₒ , a , A ) → ( qₒ , AA )

    δ( qₒ , b , A ) → ( q₁ , ε )

    δ( q₁ , b , A ) → ( q₁ , ε )

    δ( q₁ , ε  , x ) → POP x (Accepted)

Now here stack is empty so string is accepted.

Note: Some rejected conditions are:

1. Number of b is more than a

    δ( q₁ , b , X ) → Rejected

2. Number of a is more than b

    δ( q₁ , ε , A ) → Rejected

3. δ( qₒ , b , X ) → Rejected

4.  δ( q₁ , a , A ) → Rejected (a does not come in q₁

There are two method for implementing push down automata.

1. Empty stack method (It is a default method)

2. Final stack method

1. Empty stack method (It is a default method):

    String is accepted when scanning is completed and stack is empty

        F= φ

2. Final stack method:

    String is accepted or rejected on any final state.

        F≠ φ

Example:

Empty stack method (It is a default method)

1. Find whether aaabbb is accepted or not. 

Solution:

    δ( qₒ , aaabbb , X ) → ( qₒ , AX )

    δ( qₒ , aabbb , AX ) → ( qₒ , AAX )

    δ( qₒ , abbb , AAX ) → ( qₒ , AAAX )

    δ( qₒ , bbb , AAAX ) → ( q₁ , AAX )

    δ( q₁ , bb , AAX ) → ( q₁ , AX )

    δ( q₁ , bb , AX ) → ( q₁ , X )

    δ( q₁ , ε , X ) → POP X (Accepted)

  

where: 

δ: Q x ( Σ U ε ) 𝜏 → Q x 𝜏*

    Q = { qₒ , q₁}

    Σ = { a , b }

    𝜏 = { X , A }

    qₒ = qₒ

    zₒ = X

    F= φ

2. Find whether aaabb is accepted or not. 

Solution:

    δ( qₒ , aaabb , X ) → ( qₒ , AX )

    δ( qₒ , aabb , AX ) → ( qₒ , AAX )

    δ( qₒ , abb , AAX ) → ( qₒ , AAAX )

    δ( qₒ , bb , AAAX ) → ( q₁ , AAX )

    δ( q₁ , b , AAX ) → ( q₁ , AX )

    δ( q₁ , ε , AX ) → Rejected (here stack is not empty)

    

3. Construct a PDA for

    {aⁿ b²ⁿ | n>=1}

Strings such as { abb , aabbbb ..... }

Flow chart for logic:

where :

    Q = { qₒ , q₁ , q₂}

    Σ = { a , b }

    𝜏 = { X , A }

    qₒ = qₒ

    zₒ = X

    F= φ

Suppose string is aabbbb than δ will be

    δ( qₒ , a , x ) → ( qₒ , AX )

    δ( qₒ , a , A ) → ( qₒ , AAX )

    δ( qₒ , b , A ) → ( q₁ , AX )

    δ( q₁ , b , A ) → ( q₂ , AX )   :No change /Skip

    δ( q₂ , b , A ) → ( q₁ , AX )   :No change /Skip

    δ( q₁ , b , A ) → ( q₂ , X )   :POP A

    δ( q₂ , ε  , x ) → POP x (Accepted)

3. Construct a PDA for

Solution:

Strings such as { aabbcc , aaabbccc ..... }

Flow chart for logic:

where :

Q = { qₒ , q₁ , q₂}

Σ = { a , b }

𝜏 = { X , A }

qₒ = qₒ

zₒ = X

F= φ

Suppose string is aabbcc than δ will be

δ( qₒ , a , x ) → ( qₒ , AX )

δ( qₒ , a , A ) → ( qₒ , AAX )

δ( qₒ , b , A ) → ( q₁ , AAX )   :No change /Skip

δ( q₁ , b , A ) → ( q₁ , AAX )   :No change /Skip

δ( q₁ , c , A ) → ( q₂ , AX )   :POP A

δ( q₂ , c , A ) → ( q₂ , X )   :POP A

δ( q₂ , ε  , x ) → POP X (Accepted)

4. Construct a PDA for

Solution:

Strings such as 

if w= aab than   wr (reverse of w) =bba

So string will be   

    a a b c b a a    (or)  a b b c b b a

Flow chart for logic:

where :

Q = { qₒ , q₁}

Σ = { a , b }

𝜏 = { X , A  , B }

qₒ = qₒ

zₒ = X

F= φ

Suppose string is  a a b c b a a  than δ will be

δ( qₒ , a , x ) → ( qₒ , AX )

δ( qₒ , a , A ) → ( qₒ , AAX )

δ( qₒ , b , AA ) → ( qₒ , BAAX )  

δ( qₒ , c , B ) → ( q₁ , BAAX )   :No change /Skip

δ( q₁ , b , A ) → ( q₁ , AAX )   :POP B

δ( q₁ , a , A ) → ( q₁ , AX )   :POP A

δ( q₁ , a , A ) → ( q₁ , X )   :POP A

δ( q₁ , ε  , x ) → POP X (Accepted)

Suppose string is  b b a c a b b  than δ will be

δ( qₒ , b , x ) → ( qₒ , BX )

δ( qₒ , b , A ) → ( qₒ , BBX )

δ( qₒ , a , AA ) → ( qₒ , ABBX )  

δ( qₒ , c , A ) → ( q₁ , ABBX )   :No change /Skip

δ( q₁ , a , A ) → ( q₁ , BBX )   :POP A

δ( q₁ , b , B ) → ( q₁ , BX )   :POP B

δ( q₁ , b , B ) → ( q₁ , X )   :POP B

δ( q₁ , ε  , x ) → POP X (Accepted)

5. Construct a PDA for

where :

Q = { qₒ , q₁}

Σ = { a , b }

𝜏 = { X , A  , B }

qₒ = qₒ

zₒ = X

F= φ

δ( qₒ , a , x ) → ( qₒ , AX )

δ( qₒ , b , A ) → ( qₒ , BX )

δ( qₒ , a , A ) → ( qₒ , AA X)  / ( qₒ , ε ) 

δ( qₒ , a , B ) → ( qₒ , ABX )  

δ( qₒ , b , A ) → ( qₒ , BAX ) 

δ( qₒ , b , B ) → ( qₒ , B, B ) / ( q₁ , ε )

δ( q₁ ,  ε , X ) → ( q₁ , X )   :JUMP ON q₁

δ( q₁ , a , A ) → ( q₁ , ε )   :POP A

δ( q₁ , b , B ) → ( q₁ , ε )   :POP B

δ( q₁ , ε  , x ) → POP X (Accepted)

Question: What is difference between Deterministic and Non deterministic PDA with the help of example.?

Answer: do your self

 Hint: Take example 4 from above for Deterministic. and example 5 for Non Deterministic.

Download Hand written Notes of PDA Push Down Automata -1 Push Down Automata -2 Push Down Automatay -3 Push Down Automata -4 Push Down Automata -5 Push Down Automata -6 Push Down Automata -7 Push Down Automata -8 Push Down Automata -9 Push Down Automata -10 Push Down Automata -11 Push Down Automata -12 Push Down Automata -13 Push Down Automata -14 Push Down Automata -15 Push Down Automata by Final state method -01 Push Down Automata by Final state method -02 Push Down Automata by Final state method -03 Push Down Automata by Final state method -04 Push Down Automata by Final state method -05 Push Down Automata by Final state method -06 Push Down Automata by Final state method -07 Download Hand written Notes of Convert Grammar to PDA Convert Grammar to PDA -01 Convert Grammar to PDA -02 Convert Grammar to PDA -03 Convert Grammar to PDA -04 Convert Grammar to PDA -05 Convert Grammar to PDA -06 Convert Grammar to PDA -07 Download Hand written Notes of Convert PDA to Grammar Convert PDA to Grammar-01 Convert PDA to Grammar-02 Convert PDA to Grammar-03 Convert PDA to Grammar-04 Convert PDA to Grammar-05 Convert PDA to Grammar-06 Convert PDA to Grammar-07 Convert PDA to Grammar-08