The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+18 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 (59.5k points)
edited by | 1.5k 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 ....

3 Answers

+25 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 (39.8k 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 :)
+4 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 (8.2k 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 (195 points)

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

37,117 questions
44,701 answers
43,765 users