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

### 10 Comments

## 3 Answers

### 20 Comments

@vijaycs @Praveen Saini SIR ,

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

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

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.

### 1 comment

As** (0) ^{+} = ^ - (0)*** .

We can represent (0)

^{+ }as a regular Language because there exist a DFA for (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. ?????