3.5k views

Consider the CFG with $\left\{S, A, B\right\}$ as the non-terminal alphabet, $\{a, b\}$ as the terminal alphabet, $S$ as the start symbol and the following set of production rules:

$S \rightarrow aB$            $S \rightarrow bA$

$B \rightarrow b$               $A \rightarrow a$

$B \rightarrow bS$           $A \rightarrow aS$

$B \rightarrow aBB$       $S \rightarrow bAA$

Which of the following strings is generated by the grammar?

1. $aaaabb$
2. $aabbbb$
3. $aabbab$
4. $abbbba$

edited | 3.5k views
0
S -> aA ...from where ?
0
how did you get 3rd step from the second step??
+1
Hm. Sorry.    I did not notice bS is not present in production.
+1
Grammar(DCFL) for generating equal number of $a's$ and $b's$. Excluding $\epsilon$.
0
Just check for equal no of a's and b's .
+2

option C "aabbab" $S \rightarrow aB$
$\rightarrow aaBB$
$\rightarrow aabB$
$\rightarrow aabbS$
$\rightarrow aabbaB$
$\rightarrow aabbab$

Correct Answer: $C$
by
edited
+4
S->bAA ->baa

so it is not the grammer for generating equal numbers of a's and b's
+1

SbA

A
A  a

A
A         A aS

S

bAA

how will this generate aabbab? reply quick

0
are there two grammers here?? is the string supposed to be generated by both of them??
+6
No it is one grammar having all these productions

as S->aB  s->bA, can be written as S->aB|bA

we need to find which of the given string can be derived by Grammar.

and then for that string , how many different derivations are possible
0
thanks, i was confused that how could s-> bA lead to aabbab