The GATE Grind

GATE 2015 CS (CS2) – Question 60

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

Over {0,1}, λ denotes the empty string. A regular grammar satisfies X0=1X1, X1=0X1+1X2, X2=0X1+{λ}. Which expression denotes X0?

  1. 10(0*+(10)*)1
  2. 10(0*+(10)*)*1
  3. 1(0+10)*1
  4. 10(0+10)*1+110(0+10)*1

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) 1(0+10)*1

Explanation

Substitute X2 into X1: X1=0X1+10X1+1=(0+10)X1+1. By Arden’s lemma X1=(0+10)*1 because the coefficient lacks λ. Then X0=1X1=1(0+10)*1, C.

More Regular Expressions and Finite Automata questions

All Regular Expressions and Finite Automata questions →