CFG for the language {w ∈ {0, 1}∗ : w is a palindrome and |w| is divisible by 3}

Question

The question is the following:

Construct CFG for the L = {w ∈ {0, 1}∗ : w is a palindrome and |w| is divisible by 3}.

I am able to construct CFG for the set of all palindromes as below:

S --> aSa | bSb | a | b | ϵ

I am not able to figure out how to make |w| divisible by 3 in my CFG.

Answer 1

Use additonal "state" information to the variable $S$ that specifies the number of terminal symbols generated, mod 3.

So we have three variables $S_i$, $i=0,1,2$, each keeping track of derivations for a string of length that remainder after division by three.

One example of a new production would be $S_1 \to aS_2 a$.

Thus, if $S_2 \Rightarrow^* w$ with $w\in\{0,1\}^*$ and $|w| = 3k +2$, then $S_1 \Rightarrow^* w'$ with $|w'| = (3k + 2) + 2 = 3(k{+}1)+1$.

Background information: The derivation trees in the new grammar are basically the same in those from the old grammar. Just relabel the variables in a bottom-up way depending on the length of the terminal string below. This approach can be adapted for any context-free grammar if we want to restrict the length of derived words modulo a number. Even more general this is how we can show that context-free languages are closed under intersection with regular languages, via grammars and not via push-down automata as one often sees.