A pushdown automaton (pda) is given in the following extended notation of…

PYQ GATE 2000

A pushdown automaton (pda) is given in the following extended notation of finite state diagrams:

start → q₀
q₀ → q₀ : 1, s/1.s
q₀ → q₁ : 2, s/s
q₁ → q₁ : 1, 1.s/s

The nodes denote the states while the edges denote the moves of the pda. The edge labels are of the form d, s/s′ where d is the input symbol read and s, s′ are the stack contents before and after the move. For example the edge labeled 1, s/1.s denotes the move from state q₀ to q₀ in which the input symbol 1 is read and pushed on to the stack.

(a) Introduce two edges with appropriate labels in the above diagram so that the resulting pda accepts the language {x2xᴿ | x ∈ {0,1}*, xᴿ denotes reverse of x} by empty stack.

(b) Describe a non-deterministic pda with three states in the above notation that accept the language {0ⁿ1ᵐ | n ≤ m ≤ 2n} by empty stack.

Sign up free to check your answer

Sign up free

Explore the full course: Theory Of Computation

Loading lesson…