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.


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.

  • $\begingroup$ Starting symbol will be S0. However I am unable to figure out exact productions of S1,S2. Can you provide a few hints perhaps? $\endgroup$ – hsnsd Oct 16 '18 at 1:55
  • 2
    $\begingroup$ No, you’ll have to work it out on your own. $\endgroup$ – Yuval Filmus Oct 16 '18 at 1:57
  • $\begingroup$ Is this correct? $$ S_1 \to 1\mid 1S_21 \mid S_01S_0 $$ $$ S_2 \to S_1S_0S_1 $$ @Yuval Filmus $\endgroup$ – hsnsd Oct 16 '18 at 4:15
  • $\begingroup$ @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. $\endgroup$ – xskxzr May 2 '19 at 9:01

Here is the ACTUAL answer
$S_0 \rightarrow 0S_00 \ |\ 1S_11\ |\ 0\ |\ \epsilon$
$S_1 \rightarrow 0S_10\ |\ 1S_21\ |\ 1$
$S_2 \rightarrow 0S_20\ |\ 1S_01\ $

  • $\begingroup$ The last 11 is redundant. $\endgroup$ – xskxzr May 2 '19 at 14:06
  • $\begingroup$ True, thank you for pointing that out. I am very tired... $\endgroup$ – redandblacktrees May 2 '19 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.