2.1k 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
edited | 2.1k 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.

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

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

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 ?

+7

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

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)+. Option B :  Hence This option is Correct, because L is Regular but not 0+, as  proved above.

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

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

1