GATE IT 2006 | Question: 4

Question

In the context-free grammar below, $S$ is the start symbol, $a$ and $b$ are terminals, and $\epsilon$ denotes the empty string.

$S \rightarrow aSa \mid bSb \mid a \mid b \mid \epsilon$

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

• A. $aaaa$
• B. $baba$
• C. $abba$
• D. $babaaabab$

Comments

Even if someone don't observe the given grammar as palindromes.

Go with options.

$\\ A:S\rightarrow aSa\rightarrow aaSaa\rightarrow aaaa\\ C:S\rightarrow aSa\rightarrow abSba\rightarrow abba\\ D:S\rightarrow bSb\rightarrow baSab\rightarrow babSbab\rightarrow babaSabab\rightarrow babaaabab$

Ans:B

---

Even if someone didn't observe palindrome they can atleast observe that starting and ending symbol will be same and only 1 option lacks that which is option B

---

With last two symbols we can check and compare whether string can be generated or not..

Answer 1

$L(G) = PALINDROME  $

$baba$  does not belong to palindrome , so B is the answer.

Comments

ya baab belong to the string baba not .

---

$L\left ( G \right ) =$ Start and end with same symbol

Edit:- My Bad. It is Palindrome.

Answer 2

S → aSa | bSb | a | b | ϵ
Given string accepts all palindromes.
Option B → baba is not palindrome.
So, this is not accepted by S.

Answer 3

Grammar is generating strings like

 

L = {$(ab)^{n}.(ba)^{n}$ | $(ba)^{n}.(ab)^{n}$ | $(a)^{n}.(a)^{n}$ | $(b)^{n}.(b)^{n}$ } 

so $baba$ is not accepted.

B

Comments

Your language is not generating “abbbbba” which is a palindrome and should be there inside the language.