Log In
0 votes

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?

Please verify.

in Theory of Computation
edited by

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

Not X


@Registered user 48

Yes sorry..will edit that :P

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

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

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

Please log in or register to answer this question.

Related questions

1 vote
1 answer
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
asked Jan 28, 2019 in Theory of Computation Mayank Bansal 270 views
0 votes
0 answers
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$
asked Jan 15, 2019 in Theory of Computation Magma 206 views
0 votes
0 answers
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.
asked Jan 15, 2019 in Theory of Computation MiNiPanda 375 views
0 votes
1 answer
Consider the following Statements : There Exist a non-deterministic CFL whose reversal is DCFL. There exist a non regular CSL whose Kleene Closure is regular. Which of following are True ? Explain with reasons.
asked Jan 13, 2019 in Theory of Computation Na462 532 views