Given the grammar
$s \to aSb \mid bSb \mid a \mid b$;
what is the language generated by the grammar over the alphabet $\{a,b\}$?
When I was solving this question I was a bit confused about the language generated by this grammar. Would be set of all palindromes? Or would the language generated by the above grammar be that of all odd length palindromes?
Is it possible that a palindrome generated by above grammar be of odd length only as there is no rule for $S \to \varepsilon$?
The language of this grammar is all strings of the form $wb^n$ where $w\in \{a,b\}^*$, and $|w| = n+1$. If I abuse the notation a bit, it is $\Sigma^{n+1}b^n$.
If perchance you mean $S \rightarrow aSa \ | \ bSb \ | \ a\ | \ b$, then the language contains all palindromic strings of odd length.
S→aSa | bSb | a | b
This grammar accepts all palindromic strings of odd length For Ex: aaa is generated by S->aSa and S->a and for string abbba : S->aSa , S->bSb and S->b aSa abSba abbba and hence we get abbba whose palindrome would be abbba itself.
S->aSa S->bSb S->a S->b solution now put any value in "S" in the L,H,S it will give a string of odd palindrome e.g aaa,aba,bbb,bab, abSba=ababa or abbba etc
The strings accepted by language are {a, b, aaa, bbb, aba, bab, ..}.Therefore more specific answer is " All of these strings are odd length palindromes." Yes it is odd length because S doesn't go to epsilon.
