Skip to content
Official PYQ · 2015

GATE CS 2015 Set 1 Q51 — Context-free Grammars and Push-down Automata

Explain with AI

Consider the NPDA ⟨Q={q0,q1,q2},Σ={0,1},Γ={0,1,⊥},δ,q0,⊥,F={q2}⟩\left \langle Q= \left \{ q_{0}, q_{1}, q_{2} \right \},\Sigma = \left \{ 0, 1 \right \}, \Gamma = \left \{ 0, 1, \perp \right \}, \delta, q_{0}, \perp, F =\left \{ q_{2} \right \} \right \rangle, where (as per usual convention) QQ is the set of states, Σ\Sigma is the input alphabet, Γ\Gamma is the stack alphabet, δ\delta is the state transition function q0q_{0} is the initial state, ⊥\perp is the initial stack symbol, and FF is the set of accepting states. The state transition is as follows:

Which one of the following sequences must follow the string 101100101100 so that the overall string is accepted by the automaton?

Choose one option
View answer

Answer: B

Worked explanation not available yet.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Context-free Grammars and Push-down Automata questions