Skip to main content

CFG for palindromes with parse trees

Short answer

Grammar: S → aSa | bSb | a | b | ε. Even palindrome abba: S ⇒ aSa ⇒ abSba ⇒ abba (S→ε). Odd palindrome ababa: S ⇒ aSa ⇒ abSba ⇒ ababa (S→a). Parse trees show matching pairs added symmetrically.

Write a CFG for L = {w ∈ {a,b}* : w is a palindrome} and also draw parse trees for the derivations of any two strings of length even or odd.

Grammar

Palindromes over {a, b} are built from the outside in by adding the same symbol at both ends, with base case ε (even length) or a single symbol (odd length).

G = ({S}, {a, b}, P, S) with

S → aSa | bSb | a | b | ε
  • S → aSa and S → bSb add matching end symbols.
  • S → ε ends an even-length palindrome; S → a or S → b ends an odd-length palindrome.

Parse tree 1: abba (even length)

Derivation: S ⇒ aSa ⇒ abSba ⇒ abba (rules S → aSa, S → bSb, S → ε)

          S
        / | \
       a  S  a
        / | \
       b  S  b
          |
          ε

Yield: a b ε b a = abba.

Parse tree 2: ababa (odd length)

Derivation: S ⇒ aSa ⇒ abSba ⇒ ababa (rules S → aSa, S → bSb, S → a)

          S
        / | \
       a  S  a
        / | \
       b  S  b
          |
          a

Yield: a b a b a = ababa.

In both trees each S node produces a matching pair of end symbols, and the bottom S gives ε (even) or one letter (odd). The grammar is unambiguous, since the first and last symbols fix the rule at each step.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 3 questions →