Construct a grammar that generates this language

1,029

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$$

Share:
1,029

Related videos on Youtube

Victor Brunell
Author by

Victor Brunell

Updated on August 01, 2022

Comments

  • Victor Brunell
    Victor Brunell over 1 year

    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!