this is a homework problem. The problem is:
Find a CFG that generates this language:
$ L = \{a^i b^j c^{i+j} \mid |i-j| \bmod 2 = 0\,\land\, i,j > 0\}$
Right now I have
$S \to S_1 | S_2$
$S_1 \to aS_1b | ab$ (on each 'a', one 'b')
$S_2 \to aaaS_1b | aaab$ (on each 'aaa' one 'b')
$S_3 \to bbbS_1a | bbba$ (on each 'bbb' one 'a')
I think thats the way to get success with $|i-j| \bmod 2 = 0$, since we need to have $i + j$ = PAIR.
Could you guys, tell me if i'm wrong?
Thank you.
Best Answer
First, $S_3$ is unreachable. But even if you include it, its production rule messes up with the order of $a$'s and $b$'s.
Second, once the production has reached $S_1$, it can't escape $S_1$, so this would allow only strings where $i=j$. Also, the production rule from $S_2$ can be used only once because it sends you directly back to $S_1$. And the same happens with $S_3.$ These rules are more restrictive than the property that you want $(|i-j|\bmod 2 = 0)$. For example, they don't generate the string $a^6b^2$.
Of course, it still remains to take into account character $c$.