---
title: "CFG for palindromes with parse trees"
subject: "Theory of Computation"
chapter: 3
key: "semester_3/theory_of_computation:cfg-palindrome-parse-trees"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/cfg-palindrome-parse-trees
site: BCT Engineering
---

# CFG for palindromes with parse trees

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2073 Chaitra
- Video: [CFG for palindrome | CFG for Odd palindrome | CFG for even palindrome |Evenodd palindrome CFL to CFG](https://www.youtube.com/watch?v=AhoAgVQqcPk) — Nitesh Jadhav Vlogs
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/cfg-palindrome-parse-trees
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

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.

## 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.

## Answer

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

```text
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 → ε)
```text
          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)
```text
          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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Which grammar generates all palindromes over {a,b}?
   A. S → aSb | ε
   B. S → aSa | bSb | a | b | ε
   C. S → SS | a | b
   D. S → aS | bS | ε
   Answer: B. Matching end symbols are added in pairs, with base cases ε, a or b. (Key point: Grammar)

2. What do S → ε and S → a | b generate?
   A. ε gives even palindromes, a or b gives odd
   B. ε gives odd, a gives even
   C. Both give even
   D. Both give odd
   Answer: A. Ending with ε yields even length; ending with a single letter yields odd. (Key point: Base cases)

3. Which rules derive ababa?
   A. S → aSa, S → bSb, S → ε
   B. S → aSa, S → bSb, S → a
   C. S → bSb, S → aSa, S → b
   D. S → aSa, S → a
   Answer: B. ababa = a(b(a)b)a, using aSa, bSb, then the base S → a. (Key point: Derivation of ababa)

4. Why is this grammar unambiguous?
   A. It has one rule
   B. The first and last symbols fix the rule used at each step
   C. It has no recursion
   D. It has no terminals
   Answer: B. The outer symbols of the string decide which production applies. (Key point: Unambiguity)

## Related in Theory of Computation

- [CFG for aⁿb^(2n); parse tree](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-an-b2n-parse-tree) — Theory of Computation, chapter 3, asked 2×
- [DFA: even a and odd b](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-even-a-odd-b) — Theory of Computation, chapter 2
- [Role of parse tree in CFG](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aparse-tree-role) — Theory of Computation, chapter 3
- [RE: even a's followed by odd b's](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Are-even-a-odd-b) — Theory of Computation, chapter 2
- [CFG for aᵐbⁿ with m ≥ n](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-am-bn-m-ge-n) — Theory of Computation, chapter 3, asked 2×

## Related in other subjects

- [Handshaking theorem; even number of odd vertices](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ahandshaking-even-odd-degree-proof) — Discrete Structure, chapter 4, asked 3×
- [Even and odd part of a signal](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Aeven-odd-part-piecewise) — Digital Signal Analysis and Processing, chapter 1, asked 2×
- [Odd and even numbers to separate files](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Afile-odd-even-until-no) — Computer Programming, chapter 10, asked 2×
- [Even/odd decomposition of a signal](https://www.bctengineer.com/question.md?key=semester_4%2Fsignals_and_systems%3Aeven-odd-decomposition) — Signals and Systems, chapter 1, asked 2×