recategorized by
8,210 views
39 votes
39 votes

A CFG $G$ is given with the following productions where $S$ is the start symbol, $A$ is a non-terminal and $a$ and $b$ are terminals.

  • $S \to aS \mid A$
  • $A \to aAb \mid bAa \mid \epsilon$

Which of the following strings is generated by the grammar above?

  1. $aabbaba$
  2. $aabaaba$
  3. $abababb$
  4. $aabbaab$
recategorized by

4 Answers

Best answer
43 votes
43 votes

$S→ aS$                        

$S→ aA$                       

$S→ aaAb$              

$S→ aabAab$                

$S→ aabbAaab$            

$S→ aabbaab$ 

Hence, (D) is the answer.

edited by
13 votes
13 votes

A→aAb∣bAa∣ϵ  => Generates some combinations of equal number of a and b

S→aS∣A => Generates a*A => a*some combinations of equal number of a and b

Hint from the above is grammer will be of form a* followed by equal a and b combinations.Also a's are atleast as many as b.

Option C:) has more b than a ,not possible,so through out.

Option A:) 3b are there means atleast 3 will be there.What ever extra a's are there these will be generatred by a*.So a* will give one a and then remaining string,abaaba will be generated by A.But you can't get a in start and end hence reject this option as well.

Similarly you can check option B will be rejected and D is the answer.

1 votes
1 votes

Option a) aabbaba

It start and end with a

$S\longrightarrow aS\longrightarrow aA$

now string end with a so we take $A\longrightarrow bAa$

$S\longrightarrow aS\longrightarrow aA\longrightarrow abAa$

as 'aa' in not formed at starting, option a is wrong.

Option b) aabaaba

It is starting with a and ending with a,

so same as above case 'aa' is not formed at starting, option b is wrong.

Option c) abababb

it is string starting with a and ending with b,

$S\longrightarrow aS\longrightarrow aA$

now string end with b so we take $A\longrightarrow aAb$

$S\longrightarrow aS\longrightarrow aA\longrightarrow aaAb$

as it has 'aa' in starting and we want 'ab' as the first two terminals,

option c is wrong.

Option d) aabbaab

it is string starting with a and ending with b,

$S\longrightarrow aS\longrightarrow aA$

now string end with a so we take $A\longrightarrow aAb$

$S\longrightarrow aS\longrightarrow aA\longrightarrow aaAb$

take $A\longrightarrow bAa$

$S\longrightarrow aS\longrightarrow aA\longrightarrow aaAb\longrightarrow aabAab$

take $A\longrightarrow bAa$

$S\longrightarrow aS\longrightarrow aA\longrightarrow aaAb\longrightarrow aabAab\longrightarrow aabbAaab$

$A\longrightarrow \epsilon$

$S\longrightarrow aS\longrightarrow aA\longrightarrow aaAb\longrightarrow aabAab\longrightarrow aabbAaab\longrightarrow aabbaab$

option d  is correct.

edited by
Answer:

Related questions

44 votes
44 votes
7 answers
2
Ishrat Jahan asked Oct 28, 2014
14,806 views
Consider a CFG with the following productions.$S \to AA \mid B$$A \to 0A \mid A0 \mid 1$$B \to 0B00 \mid 1$$S$ is the start symbol, $A$ and $B$ are non-terminals and 0 an...
54 votes
54 votes
8 answers
4
Ishrat Jahan asked Oct 29, 2014
11,778 views
Host $X$ has IP address $192.168.1.97$ and is connected through two routers $R1$ and $R2$ to an­other host $Y$ with IP address $192.168.1.80$. Router $R1$ has IP address...