search
Log In
2 votes
974 views

Given the following production of a grammar:

$S \rightarrow aA \mid aBB$;

$A \rightarrow aaA \mid \lambda$;

$B \rightarrow bB \mid bbC$;

$C \rightarrow B$

Which of the following is true?

  1. The language corresponding to the given grammar is a set of even number of a’s
  2. The language corresponding to the given grammar is a set of odd number of a’s
  3. The language corresponding to the given grammar is a set of even number of a’s followed by odd number of b’s
  4. The language corresponding to the given grammar is a set of odd number of a’s followed by even number of b’s
in Theory of Computation
recategorized by
974 views
0

something is missing from grammar.Please update the question.

3 Answers

3 votes

B is calling C and C is calling B so that part will never end so ignore this

considering S->aA and A->aaA|λ which will give either a or aaa or aaaaa and so on so 

correct ans is B

1 vote
The grammar is not proper.

Once it goes to production B, it endlessly produce bs. there is no stopping condition for B

Assume that we never go to B production.

We can produce A--> aA-->aλ--> a //odd number

hence A is wrong

B is correct
0 votes

Answer : B

if we consider each options one by one 

The language corresponding to the given grammar is a set of even number of a’s then Language generated by it would be 

L1 = {∈ , aa , aaaa .......}

The language corresponding to the given grammar is a set of odd number of a’s then Language generated by it would be 

L2 = {a . aa , aaaaa ......}

The language corresponding to the given grammar is a set of even number of a’s followed by odd number of b’s

L3 = {b , bbb ,bbbbb , bbbbbbb , aab , aabbb , aaaab ,aaaabbb... , }

The language corresponding to the given grammar is a set of odd number of a’s followed by even number of b’s

L4 = {a ,aaa ,aaaaa ,aaaaaaa , abb ,abbbb ,aaabb ,aaabbbb.........}

Language L1 can generate "∈" but not grammar so option 1 is not correct

Language L3 can generate "b" but not grammar so option 3 is not correct

Language L4 can generate "abb" but not grammar so option 4 is not correct.

Grammar can generate all the strings which can be generate by option 2 language.

0
In the question there is no terminal present to stop the repetition of B or C .without that production how we can give answer?
0
@leen i did not check whether it is stoping or not i just explored the possiblities that option b can be correct among all given options.....just think about it do we have to care whether B or c stoping or not to answer this question....and please tell me whats wrong in it
Answer:

Related questions

1 vote
0 answers
1
595 views
Non-deterministic pushdown automaton that accepts the language generated by the grammar: $S \rightarrow aSS \mid ab$ ...
asked Jul 22, 2016 in Theory of Computation jothee 595 views
2 votes
3 answers
2
2k views
Assume statements $S_1$ and $S_2$ defined as: $S_1$: $L_2 - L_1$ is recursive enumerable where $L_1$ and $L_2$ are recursive and recursive enumerable respectively. $S_2$: The set of all Turing machines is countable. Which of the following is true? $S_1$ is correct and $S_2$ ... correct Both $S_1$ and $S_2$ are correct Both $S_1$ and $S_2$ are not correct $S_1$ is not correct and $S_2$ is correct
asked Jul 22, 2016 in Theory of Computation jothee 2k views
1 vote
1 answer
3
1.2k views
The language $L=\{a^n b^n a^m b^m \mid n \geq 0, m \geq 0 \}$ is Context free but not linear Context free and linear Not context free and not linear Not context free but linear
asked Jul 22, 2016 in Theory of Computation jothee 1.2k views
2 votes
1 answer
4
1.8k views
The language accepted by the non-deterministic pushdown automaton $M=( \{ q_0, q_1, q_2\}, \{a, b\}, \{ a, b, z\}, \delta, q_0, z, \{q_2\})$ with transitions $\delta (q_0 a, z) = \{ (q_1 a), (q_2 \lambda) \}$; $\delta (q_1, b, a) = \{ (q_1, b) \}$ $\delta (q_1, b, b) = \{ (q_1 b) \}, \delta (q_1, a, b) = \{ (q_2, \lambda ) \}$ is $L(abb*a)$ $\{a\} U L(abb*a)$ $L(ab*a)$ $\{a\} U L(ab*a)$
asked Jul 22, 2016 in Theory of Computation jothee 1.8k views
...