The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+20 votes

Let $L$ denote the languages generated by the grammar $S \to 0S0 \mid 00$.

Which of the following is TRUE?

- $L = 0^+$
- $L$ is regular but not $0^+$
- $L$ is context free but not regular
- $L$ is not context free

+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

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

+28 votes

Best answer

+1

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

strings are 0^{2 } , 0^{6} ,0^{10} ....they are in A.P .... regular expression possible.

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

S - > 0B | 00

B -> 0S.

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

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

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

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

**(Q**_{0}**)**_{-------------------0----------------------->}** (Q _{1})^{<-}_{-}^{-}_{-}^{-}_{-}^{-}_{-}^{0-}_{-}^{-}_{-}^{-}_{-}^{-}_{-}^{--}_{>}|**

Here Q_{0} is the initial state and Q_{1 }is the final state Q_{1} having self loop of 0.

Please explain why **(0) ^{+ }**is not a Regular language. ?????

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 556
- Exam Queries 553
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,903 questions

52,285 answers

182,209 comments

67,715 users