# CFG for language of all palindromes whose number of 1s is divisible by 3

The question is the following:

Construct a CFG for $$L_2 = \{w \in \{0, 1\}^* \mid w = w^R\text{ and the number of 1’s in w is divisible by 3}\}$$.

I can construct a CFG for $$\{w \in \{0,1\}^* \mid w = w^R\}$$ as follows

$$S → 1S1\mid 0S0\mid 0\mid 1\mid \epsilon$$

I don't understand how to make $$w$$ divisible by 3 in my CFG.

$$S_0 \rightarrow 0S_00 \ |\ 1S_11\ |\ 0\ |\ \epsilon$$
$$S_1 \rightarrow 0S_10\ |\ 1S_21\ |\ 1$$
$$S_2 \rightarrow 0S_20\ |\ 1S_01\$$

• The last 11 is redundant. May 2, 2019 at 14:06
• True, thank you for pointing that out. I am very tired... May 2, 2019 at 15:18

One way is to use the closure of context-free languages to intersection with a regular language.

In this case, though, it is simple enough to construct the grammar explicitly. The idea is to have three different symbols, $$S_0,S_1,S_2$$, where $$S_b$$ generates all palindromes in which the number of 1s is equivalent to $$b$$ mod 3. The productions for $$S_0$$ are $$S_0 \to 0S_00 \mid 1S_11 \mid 0 \mid \epsilon.$$ I'll let you figure out the productions for $$S_1,S_2$$, as well as which symbol is the starting symbol.

• Starting symbol will be S0. However I am unable to figure out exact productions of S1,S2. Can you provide a few hints perhaps? Oct 16, 2018 at 1:55
• No, you’ll have to work it out on your own. Oct 16, 2018 at 1:57
• Is this correct? $$S_1 \to 1\mid 1S_21 \mid S_01S_0$$ $$S_2 \to S_1S_0S_1$$ @Yuval Filmus Oct 16, 2018 at 4:15
• @hsnsd No, note the two $S_0$s in $S_01S_0$ may produce different strings. The productions for $S_1$ and $S_2$ are very similar to that for $S_0$. The idea is to consider separately the cases based on the first and the last characters. May 2, 2019 at 9:01