# odd length palindrome's f=language [closed]

Find the language generated by the following grammar over the input alphabet = {a,b}.

S –> aSa | bSb | a | b

The language generated by the above grammar over the alphabet {a,b} is the set of
(A) All palindromes
(B) All odd length palindromes.
(C) Strings that begin and end with the same symbol
(D) All even length palindromes
the ans is b. i want to know the language for the grammar

• What have you tried? What was your approach? Don't dump your homework here without having thought about it by yourself. – A.Schulz Apr 10 '16 at 7:39
• How can the answer be (C)? The string $abaa$ starts and ends with the same character but can't be generated by the given grammar. – Rick Decker Apr 10 '16 at 16:10
• My approach is very simple. The possible palindrome generated by above grammar can be of odd length only as there is no rule for S -> \epsilon For example generated palindromes are aba, aaa, bab, ababa, aaaaa, .. – ARKA PRAVA MUKHERJEE Apr 12 '16 at 15:17

$$S \to aSa \mid bSb \mid a \mid b$$

Hints:

(A) All palindromes

• Can you generate the string $abba$ from the languege?

(B) All odd length palindromes.

(C) Strings that begin and end with the same symbol

• Can you generate the string $ababaa$ from the languege?

(D) All even length palindromes.

• Same hint as in (A)

Just add one more production to this grammar i.e S->^(Epsilon) and this grammar works

• aSa -> abSba [replacing S-> bSb] -> ababa[replacing S->a](string start with symbol a and end with a => same symbol) – ARKA PRAVA MUKHERJEE Apr 12 '16 at 15:28
• Two cases:

1. Both B and C are appropriate, but since B is a more specific answer, B is correct.
2. In case of S->a or S->b, there is only a begin symbol and no end symbol. Correct me if I am wrong.