The Gateway to Computer Science Excellence
+2 votes
376 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 by Veteran (105k points)
recategorized by | 376 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

by Boss (49.3k points)
+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
by Boss (33k points)
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.

by Boss (45.4k points)
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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,321 answers
198,402 comments
105,158 users