The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
1.7k views

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.6k points)
edited by | 1.7k views
+4
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.
+3
@ARJUN SIR

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


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?

+1

:(

yes

 a non regular grammar may or may not generate RL

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

DFA fr the given grammar ....

+1

Please explain why 0+ is not regular.

0
@sambhrant

you are not interpreting in right way

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

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 (41.1k points)
edited by
0
What will be the answer if grammar is S-> s0s0|00 ?
0

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.

+2

^^ $00(0000)^*$ 

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

No.

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

  S - > 0B | 00

  B -> 0S.

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

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

0

@vijaycs @Praveen Saini   SIR ,

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

+1

^ 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) } 

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

S -> 0S0 | 00.

So, S -> 00.

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

+1
got it :)
+2

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

+6

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

+1
Thank you so much :)
0
How is $0^+$ not regular? we can write its expression as $0(0)^*$, or RL as $\{0, 00, 000, 0000, ...\}$ . Please explain.
0
How is 0+ is not regular? we can write its RL as {0,00,000,0000,...} Please explain.
0
@abhishek L is regular and L $L \ne \{0^+\}$ and it doesn't mean $0^+$ is non-regular
0
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.
+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.6k points)
0

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 (191 points)
Answer:

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

42,658 questions
48,639 answers
156,230 comments
63,953 users