edited by
10,291 views
40 votes
40 votes

Let $L$ denote the languages generated by the grammar $S \to 0S0 \mid 00$.
Which of the following is TRUE?

  1. $L = 0^+$
  2. $L$ is regular but not $0^+$
  3. $L$ is context free but not regular
  4. $L$ is not context free
edited by

4 Answers

Best answer
49 votes
49 votes

Correct Option: B
Language generated by this grammar is $L = (00)^+$  which is regular and $L$ is not $0^+$

edited by
7 votes
7 votes

Option A : L is not 0+ , because 0+ will contain any arbitrary string over alphabet 0 with any no of 0's ( except empty string ), for ex: {0, 00, 000,00000}, but L will only have the strings as { 00, 0000, 000000,...}, i.e only even no of  0's ( excluding empty string}.

 Option D : L is a Context Free Language, because the Grammar G which generates the language L is Context Free Grammar. A Grammar G is CFG if all of its productions are of the form A->α, where A is a single non-terminal and α belongs to (V∪ T)* , i.e  α can be a string of terminals and/or Non-terminals. (V represents a non-terminal and T represents a terminal)   

Option C : L is a Regular Language, Because we are able to write a regular expression for it ( and also able to make a Finite Automaton), which is (00)+.DFA (00)+ (1)    Option B :  Hence This option is Correct, because L is Regular but not 0+, as  proved above.

0 votes
0 votes

For those who think that L is not regular because the pumping lemma say’s so. i.e if they are taking w = 0000 and y =0 then pumping i=2 ; w2 = 00000 which does not belong to L.

Then check this link : https://stackoverflow.com/questions/14705091/pumping-lemma-for-regular-language

It has cleared a misconception which you might have missed while proving Languages not Regular.

“In short we need to check for every possible y in the assumed w and we can say the language is not regular only when there is no such y in w which satisfy all the rules of P.L.”

Answer:

Related questions

28 votes
28 votes
5 answers
1
Kathleen asked Sep 14, 2014
11,369 views
Let $S$ and $T$ be languages over $\Sigma=\{a,b\}$ represented by the regular expressions $(a+b^*)^*$ and $(a+b)^*$, respectively. Which of the following is true?$S \subs...
41 votes
41 votes
6 answers
4
Kathleen asked Sep 14, 2014
11,865 views
Which of the following need not necessarily be saved on a context switch between processes?General purpose registersTranslation look-aside bufferProgram counterAll of the...