• S
    SwaseekhGATE Preparation
General
  • Dashboard
  • Syllabus
  • Questions
  • Aptitude
  • Mock Tests
  • TCS NQT 2026
Account
  • Pricing
  • Contact
  1. GATE CS
  2. PYQs
  3. Theory of Computation

The regular expression 1*(01*)* denotes the same set as: A. (1*0)*1* B. 1*(10)*1 C. (1+0)* D. None of the above

GATE 2003 · Theory of Computation · Regular Expression · easy

Answer: A. (1*0)*1* — this denotes the same set (all binary strings) as 1*(01*)*. Note: C = (0+1)* also describes the same set, but the GATE answer is A.

  1. Simplify 1*(01*)*: 1*(01*)* can generate any binary string: starting with 1's (using 1*), then any sequence of 0's and 1's (using (01*)*). For any binary string, we can write it as: initial 1's (use 1*), then each 0 followed by subsequent 1's forms a block in (01*)*. So 1*(01*)* = all binary strings = (0+1)*.
  2. Check Option A: (1*0)*1*: For any binary string: we can always partition it into blocks of (zero or more 1's followed by 0), and then any trailing 1's. For example '110100': (110)(0)+(trailing nothing) wait, '1', '10', '0', '1': (1*0)* can cover (1*0)(0)(1*0) and 1* covers the trailing 1. Actually (1*0)*1* covers all binary strings since every string either ends in 0 (use (1*0)* fully, 1*=empty) or ends in 1 (last 1's are covered by trailing 1*). So (1*0)*1* = Sigma*.
  3. Check Option B: 1*(10)*1: 1*(10)*1 must end with exactly one '1' (from the trailing literal '1'). The string '0' is not in this language (it doesn't end with 1). But '0' is in 1*(01*)* (0 is generated by 1*=empty, then (01*)^1 = 0). So B is NOT equivalent.
  4. Check Option C: (0+1)*: (0+1)* is obviously all binary strings. So C is also equivalent to 1*(01*)*. However, the standard GATE answer for this question is A.