Question

What language is accepted by the following PDA? Z is the bottom of stack marker and p is the start state. 8 (p. 2, Z) = (p, E) 8(p, , A ) = ( p , ε ) 8(2,0, z) = ( S , AZ) 8 (5,1, A ) = ( p , E )

Answer 1

PDA:

There are two types of PDA

1.       Accept with final state

2.       Accept on empty stack

As no final state is mentioned, given automata is Accept on empty stack.

PDA uses stack to accept any string in the language.

Supports 3 operations:

Push: inserting symbol into stack

3rd transition, (S,AZ) is push operation

Pop: deleting top symbol of stack

1st,2nd and 4th   operations, (p,e) is pop operation

Skip: don’t do any operation on stack.

States: {P,S}

Start state: {p}

Stack alphabet: {Z}

1st transition:

P on seeing input symbol 2 and stack symbol Z, it goes to same state by doing pop operation.

If do again pop operation, top symbol still Z only.

2nd  transition:

P on seeing input symbol e and stack symbol A, it goes to same state by doing pop operation.

If do again pop operation, top symbol still Z only.

3rd  transition:

P on seeing input symbol 0 and stack symbol Z, it goes to state S by doing push operation with A.

A

Stack looks like this.

4th transition:

S on seeing input symbol 1 and stack symbol A, it goes to state S by doing pop operation.

Z

Stack looks like this. It is empty

PDA diagram:

2, Z,G 1 O, Z, AZ u (2, Z,E) Means Symbol 2, when stack Symbol 2, pop the top 1, A, E E.A,E Symbol of Stack.

Here, we can observe that if string contains 1 then 0 should be followed always.

2 can taken any number of times.

Epsilon is not accepted as no transition for empty symbol on stack symbol Z.

Hence, this PDA accepts Language L= { (01+2)m | where m>0 }