3
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

Reset to default
3
$\begingroup$

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\ $

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

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.

$\endgroup$
4
  • $\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, 2018 at 1:55
  • 2
    $\begingroup$ No, you’ll have to work it out on your own. $\endgroup$
    – Yuval Filmus
    Oct 16, 2018 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, 2018 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, 2019 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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