recategorized by
2,499 views
2 votes
2 votes

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 by

3 Answers

3 votes
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 votes
1 votes
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
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.

Answer:

Related questions

1 votes
1 votes
0 answers
1
go_editor asked Jul 22, 2016
974 views
Non-deterministic pushdown automaton that accepts the language generated by the grammar: $S \rightarrow aSS \mid ab$ is$\delta (q_0, \lambda , z)= \{ (q_1, z) \}; \delta...
1 votes
1 votes
1 answer
3
go_editor asked Jul 22, 2016
2,736 views
The language $L=\{a^n b^n a^m b^m \mid n \geq 0, m \geq 0 \}$ isContext free but not linearContext free and linearNot context free and not linearNot context free but line...