The GATE Grind

GATE 2014 CS (CS1) – Question 26

Theory of Computation · Regular Expressions and Finite Automata · 1 mark · Multiple choice

For the finite automaton shown, find the set of reachable states after input 0011.

Diagram for GATE 2014 CS (CS1) question 26
  1. $\{q_0,q_1,q_2\}$
  2. $\{q_0,q_1\}$
  3. $\{q_0,q_1,q_2,q_3\}$
  4. $\{q_3\}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $\{q_0,q_1,q_2\}$

Explanation

Start with{q₀}. Both leading0symbols leave onlyq₀. The first1 reaches{q₀,q₁}; the second1 reaches q₀,q₁ fromq₀ andq₂ fromq₁. Thus the final reachable set is **{q₀,q₁,q₂}, A**. q₃ needs a further symbol after enteringq₂.