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/sThe 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 freeLoading lesson…

