Acceptance of PDA

In this class, We discuss the Acceptance of PDA.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of pushdown automata. Click Here.

Accepting a given input string in pushdown automata is done in two ways.

a) Acceptance by final state.

b) Acceptance by the empty stack.

Example: Take the language L = {aⁿbⁿ where n >0}

We assume the reader is good at constructing push down automata for language L.

We discussed constructing PDA for L in the previous class.

The below diagram shows the PDA for language L using acceptance by final state.

On state q1, if the input is epsilon. I.e. input is over, and the stack top is z0. We move to the final state.

The above PDA will accept the string by moving to the final state.

The below diagram shows the PDA for language L using acceptance by the empty stack.

On state q1, if we see the input symbol epsilon and the stack top is z0. We are popping z0 from the stack.

The stack is made empty by the end of the input string.

We can choose any one of the ways to construct PDA.

We show instantaneous descriptions for the input string aabb for both the acceptance.

ID(q0, aabb, z0)

ID(q0, abb, az0)

ID(q0, bb, aaz0)

ID(q1, b, az0)

ID(q1, ε, z0)

The last step for acceptance by the final state is the ID(qf, ε, z0)

The last step for acceptance by empty stack is the ID(q1, ε,ε)