The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+20 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
asked in Theory of Computation by Veteran (52k points)
edited by | 2.1k views
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 ....


Please explain why 0+ is not regular.


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.

3 Answers

+28 votes
Best answer

B. is the answer for this question
Language generated by this grammar is $L = (00)^+$  that is regular but not $0^+$

answered by Boss (42.3k points)
edited by
What will be the answer if grammar is S-> s0s0|00 ?

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.
+5 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.

answered by Loyal (9.3k points)

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. ?????

0 votes

answer is B

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

answered by (203 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,535 questions
54,117 answers
71,028 users