The regular expression corresponding to the language L where \(L=\{ x \in…
2015
The regular expression corresponding to the language L where
\(L=\{ x \in \{0,1\}^* \mid x \text{ ends with 1 and does not contain substring 00 } \}\)
- A.
(1+01)* (10+01)
- B.
(1+01)* 01
- C.
(1+01)* (1+01)
- D.
(10+01)* 01
Attempted by 52 students.
Show answer & explanation
Correct answer: C
Key idea: every 0 in any string of the language must be immediately followed by a 1 (otherwise the substring 00 would appear).
Because 00 is forbidden, each 0 can only occur as the substring "01".
Therefore every string in the language is a concatenation of the blocks "1" and "01".
The language requires strings to end with 1, so at least one block must appear (the empty string is not allowed).
Putting this together, a correct regular expression is (1+01)+, which is equivalent to the form (1+01)*(1+01).
Examples of matched strings: 1, 11, 101, 0101, 10101.
A video solution is available for this question — log in and enroll to watch it.