GATE IT 2008 | Question: 78

Question

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?

• A. $aabbaba$
• B. $aabaaba$
• C. $abababb$
• D. $aabbaab$

Comments

@Arjun Sir this question is given in ambiguous form in GO pdf please update this. 

---

If seen carefully grammar won't be able to generate strings starting and ending with same symbol except a*.

aaaaabbaa ---- also in the lanfuage, isn't it ?

---

Yes @Shaik Masthan wrongly interpreted by me 

---

This question can be solved easily,first see that every string length is 7 that is odd so we need first production S->aS ,else we can't build odd length string.
After that just match second alphabet and last alphabet ,third alphabet and second last alphabet,so on (leaving first 'a' , because it is created by production S->a)
Now if we find (a,b) or (b,a) then it is match else (a,a) or (b,b) means no match because there is no production of form S->aSa|bSb.

Answer 1

$S→ aS$                        

$S→ aA$                       

$S→ aaAb$              

$S→ aabAab$                

$S→ aabbAaab$            

$S→ aabbaab$ 

Hence, (D) is the answer.

Comments

@Hemant Parihar then in 

option d) 

String is  aabbaab, again left the initial "a" and string becomes abbaab

Now ab -------> ()

ba --------------> )( ------> How's this balanced?!

last ab ---------> ()

---

Yeah you are correct. We should not do like this.

---

Oh brother, I reeked my brain so much over this. Anyways, thanks

Answer 2

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.

Answer 3

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.

Comments

How such questions can be solved during exams ,do we have to check for every option? Pls guide

---

Just by properly observing the grammar you can quickly eliminate the options, say in above question number of b's will be always less than or equal to a, so option C can be eliminated.

Similarly, the strings starting and ending with a won't have 'aa' at starting, so option A and B can be quickly eliminated and for making sure answer is D just try to derive the string from given grammar.

---

Thankyou so much for your response @Parth Shah 

​I liked the approach.

---

simply by checking the grammer we can infer that no of b can equal to a but cannot be greater than a so C is ruled out

next since second production is used when we want to generate the string which have different start and last symbol and this production should be used only to generate even length string or single alphabet

so for option A -after generating aa we are left with 5 character so  second prodcution can't be used

for option B - after generating aa we are left with 5 characters so second production can't be used

for option D - after generating a we are left with 6 characters so we use second production

Answer 4

S→aS
S→aA
S→aaAb
S→aabAab
S→aabbAaab
S→aabbaab