441 views
0 votes
0 votes

This is the Gate Question - https://gateoverflow.in/3392/gate2008-it-78?show=155376#c155376

I couldn't help but understand the balanced parenthesis thing, I know, () this is balanced, (( )) is balanced, ((( ))) is balanced, but how's that working in that gate Question, someone kindly explain.

Also, I didn't have any intention to make a duplicate question/thread, I will close this question whenever I get my doubt solved.

Thanks!

1 Answer

0 votes
0 votes
Maybe this will be helpful. This is what I did when solved this question.

Just look at the grammar, you can see from the productions $S \rightarrow aS$ and $S \rightarrow A$, that the grammar will generate some numbers of a and then goto $A$, we will get some sequential form like $S \rightarrow ^{*} a^{*}A$. Now looking at A's production we can see that it generates an equal number of a's and b's, and then goes to epsilon. Giving some string like $a^{*}w | \#_{a}(w) = \#_{b}(w)$. There is one more thing to notice, in $w$ part of the string for every $a$ at the end you need to match a b in front and vice-versa.

From this intuition, look at the options.

In A. $aabbaba$ the last letter is $a$, so there must be a matching $b$ for it which indicates the beginning of $w$ part of the string. This divides the string as $aa - bbaba$. So the first part is $a^{*}$ as we wanted. Now looking at $bbaba$, Here last $a$ can be matched with the first $b$, so good. But second last $b$ needs to be matched up with an $a$ in second position(of $w$). But there is a $b$ in the second position. So, we can conclude that this string cannot be generated by the given grammar.

Now, coming to the option B.  $aabaaba$. Here also we see an $a$ at last, so it should be matched with a $b$, and that $b$ will indicate the start of the string $w$. So we see the string as $aa - baaba$. Matching last $a$ with first $b$, good till now. Matching second last $b$ with the second $a$, this is also fine. Now we only left with a single $a$, which can not be matched with any $b$. This concludes that this string also cannot be generated by the grammar.

With similar reasoning, you can further analyze options C and D.

Hope it helps :)

Related questions

1 votes
1 votes
2 answers
1
mk_007 asked Oct 2, 2021
270 views
14.Show that the grammar S → aSb |SS| e is ambiguous, but that the language denoted by it is not.Can someone share the approach for second part.
1 votes
1 votes
1 answer
3
–1 votes
–1 votes
0 answers
4
MohammedSunasra asked May 23, 2016
168 views