The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

+2

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.

+1

@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

+25 votes

Best answer

0

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 ?

+4

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

+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)+. 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.2k
- Engineering Mathematics 4.9k
- Digital Logic 2k
- Programming & DS 3.6k
- Algorithms 3k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 949
- Others 1.3k
- Admissions 411
- Exam Queries 419
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 9

34,786 questions

41,762 answers

118,950 comments

41,409 users