in Theory of Computation edited by
33 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
in Theory of Computation edited by


I don't understand that how this grammar can be regular. It is neither left linear nor right linear. A regular grammar is always either right linear or left linear.

same doubt, It is neither left linear nor right linear so why regular.I agree thatattern will generate but grammar not satisfying here

It is neither left linear nor right linear so why regular.

 @Set2018 L is language not the grammar! so in question they are asking if the language generated by the grammar is regular or not.
A non-regular grammar also can generate regular language, right?




 a non regular grammar may or may not generate RL

in the question type of the language generated by the grammar is asked and not the grammar itself

DFA fr the given grammar ....

edited by
On the first sight the language appeared to be $0^{n}000^{n}$ which is CFL. :o

you are not interpreting in right way

"but not 0+ means the language is not 0+ it is 00+".

Language L will always contain even number of zeroes but Language 0can have odd number of zeroes too in their strings, like : one zero or three zeroes etc.

@manu thakur, dude you just saved me, all day long I am solving gate questions, and the only mistakes I made so far were all silly! just like this one! thanks for answering

Subscribe to GO Classes for GATE CSE 2022

3 Answers

42 votes
Best answer

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

edited by


What will be the answer if grammar is S-> s0s0|00 ?
edited by

it is regular , as we can't give a regular expression for it.

strings are 0 , 06 ,010 ....they are in A.P .... regular expression possible.


^^ $00(0000)^*$ 

yup ! corrected myself. thanks . I made a mistake .
is the grammar itself regular ?


@Peaveen sir --- can we write above grammar as -

  S - > 0B | 00

  B -> 0S.

And let me know whether it is a RG or not ??

^^ Yes this is correct , and RG also , S->00S|00 too. 


@vijaycs @Praveen Saini   SIR ,

Can we write  S → 0S0 | 00.  as  0 (00 )+0 ? Is this RE denote RL ?  Correct me if wrong 


^ I think, No. 

Does your language contain string 00 ? I think no, but it is being generated by the given grammar. right ??

L = 0(00)*0.

L = { 00, 0000, 000000,......... all even length string(contains 0 only).. ...( except - epsilon) } 

@vijaycs SIR , How 00 generated ?  There is no epsilon production the grammer

S -> 0S0 | 00.

So, S -> 00.

And please don't call me sir ...  :)

got it :)

@vijaycs , 
I used to call people with more knowledge SIR :)
I more thing, 

0(00)* 0 can also be written as (00)+ b ut How to prove it in RE Technique ?


^ Yes, we can also write (00)+.

=> A language can be represented as many expression.

Here - L =00(00)*

          L = (00)*00

          L = (00)+

          L = 0(00)*0

..... and many more if possible.

=> A language can be generated by many grammars

Here - S -> 0S0 | 00

          S -> 00S | 00

          S -> S00 | 00

          S -> 0B | 00 , B -> 0S.

......and many more if possible.

But any regular language can be accepted by one one minimal DFA. 

Again, It can be accepted by many NFA.

Thank you so much :)
How is $0^+$ not regular? we can write its expression as $0(0)^*$, or RL as $\{0, 00, 000, 0000, ...\}$ . Please explain.
How is 0+ is not regular? we can write its RL as {0,00,000,0000,...} Please explain.
@abhishek L is regular and L $L \ne \{0^+\}$ and it doesn't mean $0^+$ is non-regular
I know that L is regular and also 0+ won't generate the required string.

But c option says that , L is regular but 0+ is not regular (As per my understanding)

What option C exactly means I am not able to understand.
6 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.

1 comment

As (0)+  = ^ - (0)* .
We can represent (0)+ as a regular Language because there exist a DFA for (0)+

(Q0)-------------------0-----------------------> (Q1)<--------0---------->|

Here Q0 is the initial state and Q1 is the final state Q1 having self loop of 0. 

Please explain why (0)is not a Regular language. ?????

1 vote

answer is B

language generated is 0^2n+2 which is regular and not 0^+.


Related questions