0

I came across a question with a solution that says this:

The context-free grammar (CFG) for palindromes of even length was given: Σ = {a, b}, P → a P a | b P b | ε

Give a context-free grammar (CFG) for palindromes that allows odd-length palindromes.

Solution: P → a a | bPb | a | b | ε

But I don't understand how "aa" is an odd-length palindrome? It's length is definitely two, unless I'm seeing it wrong. They say it's the right answer, and if it is, I need to know the reason why since I don't understand it.

just coding
  • 1
  • 3
    Obviously it is a misprint. Should have been $aPa$. Doesn't make sense otherwise. Also, the new grammar allows for both odd and even length palindromes. It is not just odd. – Michal Adamaszek Nov 24 '23 at 11:27
  • Oh, thank you! I have a question. By new grammar do you mean this one - P → a a | bPb | a | b | ε? If yes, could you explain how it works for even length palindromes as well? – just coding Nov 24 '23 at 11:34
  • 1
    The grammar is $P\to aPa|bPb|a|b|\varepsilon$. It gives palindromes of all lengths because it allows you to have either of $a,b,\varepsilon$ in "the middle" when you finish developing the first two rules. – Michal Adamaszek Nov 24 '23 at 11:37
  • Oh, I see! Thank you very much! :) – just coding Nov 24 '23 at 11:49

0 Answers0