# MadeEasy Test Series 2019: Theory of computation - Grammer

336 views

Let L be the language of all strings on [0,1] ending with 1.

Let X be the language generated by the grammar G.

$S \rightarrow 0S/1A/ \epsilon$

$A \rightarrow 1S/0A$

Then $L \cup X=$

1. ∑*
2. L
3. X

Ans given : B. ∑*

They said that X is a language which contains all strings that do not end with 1. But is it so?

Can’t we generate 11 from the grammar?

edited
0

They said that L is a language which contains all strings that do not end with 1.

Not X

0

@Registered user 48

Yes sorry..will edit that :P

0
I thought the question itself was given like that and you interpreted it wrong :p
0

@Registered user 48

Oh it was right before only.. I suddenly got confused. See their solution..

They said that L(X) = not ending with 1. But 11 is a valid string.

0
the DFA shown in the figure is of language generated by x   i.e. no of 1’s should be even

so the string 11 will be accepted by X

i hope your doubt got cleared
0
now i have a question what about the string which have odd no of 1’s and end with a zero

how they are present in the language

## Related questions

1 vote
1
270 views
Let L = {w| w ∈ {0,1}*; w contains 01 and 011 as substring}. The number of states in the minimal DFA corresponding to the complement of L is equal to My Answer: Correct if I am wrong. Its complement will be all strings which don’t have 01 as substring. so if we make its dfa then minimum number of states will be 3. Answer given is 4
Consider the following NFA M , over the alphabet {a} let L(M) be the language accepted by the NFA M . let $M'$ denote the machine obtained by the final and non final states respect . then which of the following statement is true about L(M) and $L (M' )$ 1 ) $L (M' ) \supseteq L(M))$ 2) $L (M' ) \cap L(M)) = phi$ $L (M' ) - L(M)) = phi$ $L (M' ) \cup L(M)) = phi$
Consider the following language over ∑={0,1} $L_{1} = \left \{ a^{\left \lfloor \frac{m}{n} \right \rfloor}| m,n \geq 1; n<m \right \}$ $L_{2} = \left \{ a^{m^{n}}| m,n \geq 1; n<m \right \}$ Which of them are regular? Both L1 and L2 Only L2 Only L1 None Ans. A. Both Please explain.