Write grammar for given language

Question

I'm trying to write a grammar for the language below: $$(a+b)^*−\{ ∶ \in\{a,b\}^*\}$$ could anyone help me?

Answer 1

You want all the words on $\{a,b\}$ that cannot be split in three equal sub-word. There is two possible case either the length of word is a multiple of 3 or it is and there is some index where the letters differ.

The first case is easy you just have to ensure that you don't generate multiple of 3 letters (hence generate all the multiple of 3 possible and finish by generating 1 or 2 more letters).

The second case is a bit more hard (I doubt that there is a context free grammar for it). You have two generate multiple of 3 letters and ensure that there is difference at some point. $$S\rightarrow S_1S_2S_3$$ $$S_1\rightarrow S_1aL~|~S_1bL$$ $$LS_2\rightarrow S_2aL~|~S_2bL$$ $$LS_3\rightarrow S_3a~|~S_3b$$ $$Lc\rightarrow cL\texttt{ for }c\in\{a,b\}$$ This generate the multiple of 3 words. We now ensure that there is a difference at some point: $$S_1\rightarrow S_1'aD_{a}~|~S_1'bD_{b}$$ $$S_1'\rightarrow S_1'aL~|~S_1'bL~|~E$$ $$D_{c}S_2\rightarrow S_2aD_{c,a}~|~S_2bD_{c,b}\texttt{ for }c\in\{a,b\}$$ $$LS_3D_{a,b}\rightarrow S_3a~|~S_3b$$ $$LS_3D_{b,a}\rightarrow S_3a~|~S_3b$$ $$LS_3D_{a,a}\rightarrow S_3b$$ $$LS_3D_{b,b}\rightarrow S_3a$$ $$Dc\rightarrow cD\texttt{ for }c\in\{a,b\}$$ $$Ec\rightarrow cE\texttt{ for }c\in\{a,b\}$$ $$ES_2\rightarrow E$$ $$ES_3\rightarrow \epsilon$$

I hope it helps