CFG for $\{uvw \mid u,v,w \in\{0,1\}^*,|u|=|v|=|w| \wedge u\neq w\}$

$$L=\{uvw \mid u,v,w \in\{0,1\}^*,|u|=|v|=|w| \wedge u\neq w\}$$

Any help would be appreciated.

• Please don't delete your question after you've received a useful response. Part of our mission is to build up an archive of high-quality questions and answers that will be useful not only to you but also to others in the future, so deleting your question after you receive an answer can be considered impolite to those who have answered.
– D.W.
May 17 '21 at 3:47
• We discourage posts that are just the text of an exercise-style task. What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question.
– D.W.
May 17 '21 at 4:19

The idea is that a word $$uvw\in L$$ can be written as $$x\alpha y\beta z$$ with $$x, y, z \in \{0,1\}^*$$, $$\alpha, \beta\in \{0,1\}$$, verifying the following conditions:

• $$\alpha \neq \beta$$
• $$|x\alpha z| = |u| = |v| = |w|$$. This implies $$|x| + |z| + 1 = |u|$$ and then $$|y| = 3|u| - 2 - |x|-|z| = 2|u| - 1 = 2 |x| + 2|z| + 1$$.

That means that if we use a grammar symbol $$X$$ to create $$x$$ and part of $$y$$, centered on the position of $$\alpha$$, informally we will need to push "one symbol on the left and two on the right" of $$X$$. The converse is done for creating part of $$y$$ and $$z$$, centered on $$\beta$$. And for the ending $$+1$$, we will add an additional terminal symbol from the starting rule.

Now we only need to do it for $$\alpha = 0$$ and $$\beta = 1$$, and the other way around.

In details, we can use the following grammar:

$$S \rightarrow X_1AZ_0 \mid X_0AZ_1$$
$$X_0 \rightarrow AX_0AA \mid 0$$
$$X_1 \rightarrow AX_1AA \mid 1$$
$$Z_0 \rightarrow AAZ_0A \mid 0$$
$$Z_1 \rightarrow AAZ_1A \mid 1$$
$$A\rightarrow 0\mid 1$$