1
$\begingroup$

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.

$\endgroup$
1

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

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

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