This is a homework problem. The problem is:
Find a grammar that generates this language:
L = {w: |w| mod 3 ≠ |w| mod 2} over alphabet Σ = {a}.
The transitions I came up with are:
S -> Baa
B -> aaa | Baaa | lambda
But this doesn't take into account 4. I've been playing with it for awhile and can't seem to figure out in what direction to go to make this happen. Any help would be much appreciated!
Best Answer
An other way (than the nice comment of @Henning Makholm) is to simply remember the rest in the modulo operation.
Formally let $\{R_{i,j}\mid i\in\{0,1\}, j\in\{0,1,2\}\}$ be the set of non terminals. $R_{i,j}$ represent that so far the word produced is such that $|w|\ mod\ 2=i$ and $|w|\ mod\ 3 =j$.
The starting non terminal is $R_{0,0}$ and we have the folowing rules in G: forall $i\in\{0,1\}, j\in\{0,1,2\}$ there is the rule:
$$R_{i,j}\to a R_{i',j'}$$ with $i'=(i+1)\ mod\ 3$ and $j'=(j+1)\ mod\ 3$.
And for all $i\neq j$ there is the rule $$R_{i,j}\to \epsilon$$