Project ForgeWhich of the regular expressions given below represent the following DFA (q0 start non-final with self-loop on 0; q1 final with self-loop on 1; q0 --1--> q1; q1 --0--> q0)?
I) 0*1(1+00*1)* II) 0*1*1+11*0*1 III) (0+1)*1
- AI and II only
- I and III only
- CII and III only
- DI, II, and III
Explanation
The DFA accepts exactly the strings ending in '1' (since being in the accepting state q1 exactly tracks 'last symbol read was 1'), i.e. L=(0+1)*1 — so III is trivially TRUE. Expression I builds a string as a concatenation of blocks 0*1 (each block ending in 1), which is exactly all strings ending in 1 — I is TRUE. Expression II = 0*1*1 + 11*0*1 can only produce strings of the restricted forms 0^a1^(b+1) or 1^(c+1)0^d1 — it CANNOT produce a string like '0101' (0's then 1's then 0 then 1), which ends in 1 and should be in the language but isn't generated by either branch — so II is FALSE.
Source: GATE CS 2014 (Session 1) (2014)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.