4
$\begingroup$

I was asked to define a CFG for the complement of $\{w\#w \mid w \in \{0,1\}^*\}$ and I'm struggling to define it. I think it is quite similar to defining a CFG for the complement of $\{ww \mid w \in \{0,1\}^*\}$, but I'm finding that the '#' really messes things up. Is the language even context-free?

$\endgroup$
3

1 Answer 1

3
$\begingroup$

If a word is not of the form $w\#w$ then one of the following must happen:

  • It contains no $\#$.
  • It contains more than one $\#$.
  • It is of the form $x\#y$, where $x,y \in \{0,1\}^*$ and $x \neq y$, in which case one of the following must happen:
    • $|x| > |y|$ or $|x| < |y|$.
    • $x_i = 0$ and $y_i = 1$ for some $i$, or vice versa.

The only case which is non-trivial to handle is the last one, in which case we have a word of the form $$ x_1 0 x_2 \# y_1 1 y_2, $$ where $|x_1| = |y_1|$. We can split this into $$ x_1 \;\; 0x_2\# \;\; y_1 \;\; 1y_2, $$ where $|x_1| = |y_1|$. This should make it clear how to construct a CFG for such words.


Altogether, we obtain the following grammar: \begin{align} &S \to A \mid B \mid C \mid D \mid E \mid F \\ &A \to 0A \mid 1A \mid \epsilon \\ &B \to A\#B \mid A\#A\#A \\ &C \to A0G \mid A1G \\ &D \to G0A \mid G1A \\ &G \to 0G0 \mid 0G1 \mid 1G0 \mid 1G1 \mid \# \\ &E \to E_11A \\ &E_1 \to 0E_10 \mid 0E_11 \mid 1E_10 \mid 1E_11 \mid 0A\# \\ &F \to F_10A \\ &F_1 \to 0F_10 \mid 0F_11 \mid 1F_10 \mid 1F_11 \mid 1A\# \\ \end{align}

In this grammar:

  • $A$ generates words without $\#$
  • $B$ generates words with more than one $\#$
  • $C$ generates words of the form $x\#y$ with $|x| > |y|$
  • $D$ generates words of the form $x\#y$ with $|x| < |y|$
  • $E$ generates words of the form $x_10x_2\#y_11y_2$ with $|x_1|=|y_1|$
  • $F$ generates words of the form $x_11x_2\#y_10y_2$ with $|x_1|=|y_1|$
  • $G$ generates words of the form $x\#y$ with $|x| = |y|$
$\endgroup$
1
  • $\begingroup$ I've been trying to test it and it seems correct, thank you very much! I was having a hard time with this one! $\endgroup$
    – Nuno Costa
    Dec 21, 2020 at 14:50

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.