The Gateway to Computer Science Excellence
+1 vote

The following Context-Free Grammar (CFG) :

$S \rightarrow aB | bA$

$A \rightarrow a | as | bAA$

$B \rightarrow b | bs | aBB$ 

will generate

  1. Odd numbers of $a's$ and odd numbers of $b's$
  2. Even numbers of $a's$ and even numbers of $b's$ 
  3. Equal numbers of $a's$ and $b's$
  4. Different numbers of $a's$ and $b's$ 
closed as a duplicate of: UGCNET-Dec2014-II-35
in Theory of Computation by Boss (30.8k points)
closed by | 330 views

3 Answers

+1 vote

Refer this for Solution

by Boss (45.4k points)
0 votes
Admin check the link also tells A there (hence C here) by mistake may be u marked X.
by (455 points)
edited by
0 votes
Answer C: Equal number of a's and b's

Option A is false because we can get even number of a's and even number of b's.

Example1: S -> bA -> bbAA -> bbaA -> bbaa

option B is false because we can get odd number of a's and odd number of b's.

Example2: S -> aB -> ab

The above two examples are creating equal number of a's and b's. This makes option D false
by (215 points)
edited by
please explain your answer in detail.

give reasons why other options are incorrect.

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,385 answers
105,385 users