Write grammar for given language I'm trying to write a grammar for the language below:
$$(a+b)^*−\{ ∶ \in\{a,b\}^*\}$$
could anyone help me?
 A: 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
