Let L denote the language generated by the grammar S -> 0S0 | 00. Which of the…
2000
Let L denote the language generated by the grammar S -> 0S0 | 00. Which of the following is true?
- A.
L = 0+
- B.
L is regular but not 0+
- C.
L is context free but not regular
- D.
L is not context free
Attempted by 7 students.
Show answer & explanation
Correct answer: B
The production S -> 00 gives the base string 00. Each use of S -> 0S0 adds one 0 to the left and one 0 to the right, so every derivation adds two more zeroes.
Hence L = {0^(2n) | n >= 1} = (00)+. This language is regular, because it is described by the regular expression (00)+. However, it is not equal to 0+, since 0+ also contains odd-length strings such as 0 and 000.
Therefore, L is regular but not 0+, so option B is correct.