I'm pretty lost, and would appreciate help or solutions to the following two exercises. I don't really know where to begin or even how to correctly denote a context-free grammar. I have to design CFGs for the following two sets:
1) $\{a^ib^jc^k \mid i \neq j \;or\; j \neq k \}$; i.e. the set of strings containing $a$s followed by $b$s followed by $c$s, s.t. there is a different number of $a$s and $b$s or a different number of $c$s and $b$s, or both.
I think I should have something like $S \rightarrow aAbBcC$, where thereafter $A \rightarrow a | A | \epsilon$, and similar for $b,c$, etc. But I don't know how to ensure different numbers of letters in the string, and more generally, I don't know what I'm doing.
2) The set of all strings of $a$s and $b$s that are not of the form $ww$, that is, not equal to any string repeated.
Best Answer
That or in the first problem should suggest writing the grammar in two parts, one that generates $L_1=\{a^ib^jc^k:i\ne j\}$ and one that generates $L_2=\{a^ib^jc^k:j\ne k\}$. If $S_1$ is the initial symbol for the first grammar, $S_2$ is the initial symbol for the second grammar, and the two grammars have no non-terminal symbols in common, they can be combined to give a grammar for the desired language simply by adding the production $S\to S_1\mid S_2$.
In generating $L_1$ you can generate any number of $c$’s, but you have to make sure that you don’t generate equal numbers of $a$’s and $b$’s. The $c$’s are no problem: we can have a production $S_1\to XC$, where $C$ will generate any number of $c$’s, and $X$ will deal with that $a$’s and $b$’s. We can let $X$ generate any number of matched pairs of $a$’s and $b$’s with the production $X\to aXb$, and then we can switch either to something that generates any positive number of $a$’s or to something that generates any positive number of $b$’s. For instance, the production $X\to Y$ together with $Y\to aY\mid a$ will take care of the words with more $a$’s than $b$’s.
That’s all of the pieces needed for the first problem; all you have to do is finish putting them together.
Added: The second problem is solved in this PDF: a context-free grammar is given along with a proof that it generates the desired language.