edited by
1,240 views
8 votes
8 votes

Over the alphabet $\{0, 1\}$, consider the language

$L = \{ w | \: w \text{ does not contain the substring  } 0011\}$
Which of the following is true about $L$.

  1. $L$ is not context free
  2. $L$ is regular
  3. $L$ is not regular but it is context free
  4. $L$ is context free but not recursively enumerable
edited by

2 Answers

Best answer
3 votes
3 votes

Let L1 be (0+1)*. L1 is regular.
Let L2 be Strings containing 0011 is regular.   (0+1)*0011(0+1)*

L1 - L2 = Regular. (Regular languages are closed under Difference).

Correct Answer: $B$

edited by
5 votes
5 votes

(B) $L$ is regular.

edited by
Answer:

Related questions

4 votes
4 votes
1 answer
1
go_editor asked May 19, 2016
2,064 views
Indicate whether the following statements are true or false, providing a short explanation to substantiate your answers.A DFA with $n$ states must accept at least one str...