# UGCNET-Sep2013-III: 18

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

recategorized
0

something is missing from grammar.Please update the question.

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

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

## Related questions

1 vote
1
595 views
Non-deterministic pushdown automaton that accepts the language generated by the grammar: $S \rightarrow aSS \mid ab$ ...
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
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
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)$