-3
$\begingroup$

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

$\endgroup$
  • 9
    $\begingroup$ What have you tried? What was your approach? Don't dump your homework here without having thought about it by yourself. $\endgroup$ – A.Schulz Apr 10 '16 at 7:39
  • $\begingroup$ 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. $\endgroup$ – Rick Decker Apr 10 '16 at 16:10
  • $\begingroup$ 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, .. $\endgroup$ – ARKA PRAVA MUKHERJEE Apr 12 '16 at 15:17
2
$\begingroup$

$$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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ aSa -> abSba [replacing S-> bSb] -> ababa[replacing S->a](string start with symbol a and end with a => same symbol) $\endgroup$ – ARKA PRAVA MUKHERJEE Apr 12 '16 at 15:28
0
$\begingroup$
  • 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.
| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.