Context-Free Grammar for Palindromes over \{a,b\} | AI Research

Context-Free Grammar for Palindromes over $\{a,b\}$

Verified Sources

Sep 13, 2026

A palindrome over alphabet $\{a,b\}$ is a string $w$ such that $w = w^R$ (where $w^R$ is the reversal of $w$ ). A standard way to write a context-free grammar (CFG) for palindromes is to build strings from the outside inward: if the palindrome starts and ends with the same symbol, then the middle must also be a palindrome.

In CFG terms, introduce a start symbol $S$ that generates exactly the language Palindrome Language of palindromes. The grammar uses productions that “wrap” a smaller palindrome with matching terminal symbols:

$S \to aSa$ generates palindromes with outer letters $a$ ,
$S \to bSb$ generates palindromes with outer letters $b$ ,
base cases generate the odd/even centers: $S \to a$ , $S \to b$ , and $S \to \epsilon$ (empty string is a palindrome).

Key learning terms

Context-Free Grammar (CFG)
Start symbol
Derivation
Palindrome

Important: The grammar must be context-free, meaning each rule replaces a single nonterminal by a string of terminals/nonterminals.

CFG for Palindromes (Outside-in construction)

A clean CFG (one nonterminal)

A correct CFG for palindromes over $\{a,b\}$ is:

Nonterminals: $\{S\}$
Terminals: $\{a,b\}$
Productions:

$S \to aSa$
$S \to bSb$
$S \to a$
$S \to b$
$S \to \epsilon$

Start symbol: $S$

This grammar generates all palindromes because:

Any palindrome is either empty, of length $1$ , or has form $a(\text{palindrome})a$ , or $b(\text{palindrome})b$ .
The productions mirror this structure exactly.

Constructing the palindrome CFG (outside-in method)

1
Step 1
Use $S$ to generate all palindromes over $\{a,b\}$ .
2
Step 2
Add $S \to aSa$ and $S \to bSb$ so the grammar enforces the first and last symbols match.
3
Step 3
Add $S \to a$ , $S \to b$ , and $S \to \epsilon$ to stop recursion at length $1$ or $0$ .
4
Step 4
Even-length palindromes come from repeated wrapping ending in $\epsilon$ ; odd-length palindromes come from wrapping ending in $a$ or $b$ .
5
Step 5
Every derivation produces a string whose first and last symbols match at each wrapping, so the final string equals its reverse.

Pro Tip

When building CFGs for palindromes, it’s almost always easiest to enforce equality of the outer symbols using rules like $S\to aSa$ and $S\to bSb$ —then handle length $0/1$ via base cases.

Common mistake

Do not use rules that allow mismatched ends (e.g., $S\to aSb$ ). That would generate strings that are not palindromes.

Example derivations

Even-length palindrome: $abba$

$S \Rightarrow aSa$
$S \Rightarrow a(bSb)a$
$S \Rightarrow a(b\epsilon b)a$
Yield: $abba$

Odd-length palindrome: $aba$

$S \Rightarrow aSa$
$S \Rightarrow a(\epsilon)a$ is not directly possible with only $\epsilon$ center between $a$ ’s unless you choose base properly; instead:
$S \Rightarrow aSa$
$S \Rightarrow a(bSb)a$ is too long; use:
$S \Rightarrow aSa$
$S \Rightarrow a(\epsilon)a$ via $S \to \epsilon$
Yield: $aa$ is wrong if you intended $aba$ , so instead derive:
$S \Rightarrow bSb$ then wrap:
$S \Rightarrow aSa$ then choose center $S \Rightarrow b$ :
$S \Rightarrow aSa$
$S \Rightarrow ab a$
Yield: $aba$

This highlights that base productions ( $a$ , $b$ , $\epsilon$ ) are what determine the exact center.

How the grammar generates palindromes

$S \Rightarrow \epsilon, a, b$

Base

Centers for even/odd palindromes."

Apply $S \to aSa$ or $S \to bSb$

Grow outward

Each step adds one matching symbol to both ends."

Return to base case

Stop

Final string length and exact center are fixed."

Palindrome length parity vs. center choice

How even vs. odd lengths are produced by the CFG.

FAQ: CFG details

Knowledge Check

Question 1 of 3

Q1Single choice

Which production in the CFG is responsible for palindromes that start and end with 'a'?

$S \to aSa$

$S \to bSb$

$S \to a$

$S \to \epsilon$

Explore Related Topics

PDA Construction for $L=\{uawb \mid u\in\{a,b\}^*,\, w\in\{a,b\}^*,\, |u|=|w|\}$

Ambiguity in Context-Free Grammars, Disambiguation Techniques, and Analysis of the Grammar $S \rightarrow aS/Sa/a$

Converting the Regular Expression $(a+b)^*ab$ into an NFA

The course shows how to turn the regular expression  $(a+b)^*ab$ —the set of all strings over  $\{a,b\}$ that end with “ab”—into an NFA, first via Thompson’s systematic ε‑construction and then with a minimal three‑state NFA.

Thompson’s construction builds ε‑transitions for symbols  $a$ ,  $b$ , their union, the Kleene star, and the final concatenations, yielding a 12‑state ε‑NFA.
A compact direct NFA uses only three states: $q_0$ loops on $a,b$ , branches on $a$ to $q_1$ , and $q_1$ moves on $b$ to accepting $q_2$ .
The compact NFA’s transition table illustrates nondeterministic moves (e.g., $δ(q_0,a)=\{q_0,q_1\}$ ) and accepts exactly the strings ending in “ab”.
State‑complexity comparison: Thompson’s method needs many states and ε‑moves, while the direct NFA is far smaller and easier to simulate.

Browse all research articles

Context-Free Grammar for Palindromes over {a,b}\{a,b\}{a,b}