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

closed as unclear what you're asking by Yuval Filmus, Juho, David Richerby, Ran G., Gilles 'SO- stop being evil' Apr 19 '16 at 11:29

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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

$\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.
$\endgroup$

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