The GATE Grind

GATE 2014 CS (CS1) – Question 46

Theory of Computation · Regular Expressions and Finite Automata · 2 marks · Multiple choice

Which regular expressions represent the shown DFA? I: 0*1(1+00*1)*; II: 0*1*1+11*0*1; III: (0+1)*1.

Diagram for GATE 2014 CS (CS1) question 46
  1. I and II only
  2. I and III only
  3. II and III only
  4. I, II and III

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) I and III only

Explanation

The DFA’s state records the last symbol, accepting exactly strings ending in1. ExpressionIII,(0+1)*1, gives this directly. ExpressionI allows initial zeros, the first1, then blocks1 or00*1, also precisely this language. ExpressionII omits some patterns, so **I and III only,B**.