I am trying to construct a regular grammar for the following language:
$$L = \{ w \ | \ (na(w) - nb(w))\mod3!= 1 \}.$$
I'm struggling to understand what it is this language produces, and thus struggling to create a grammar for it.
We want a combination of $a$'s and $b$'s such that the difference of the two, $\mod 3$ is not equal to $1$. We know that $1, 4, 7, 10, 13,\dots, \mod 3 = 1$. With that being said, some valid strings would consist of:
- the same amount of $a$'s and $b$'s // $0 \mod 3 = 0$,
- three $a$'s for every 1 $b$ // $3-1 = 2 \mod 3 = 2$.
So I've started with this, but I'm lost on how to include the same amount of $a$'s and $b$'s.
$S \rightarrow aaabS \ | \ \lambda \hspace{1cm}$ (this takes care of the empty string)
First, a DFA accepting the language. Let the states be $Q = \{q_0, q_1, q_2\}$. I assume the alphabet is $\Sigma = \{a, b\}$ The idea is: after processing a string $s \in \Sigma^{*}$, the machine will be in state $q_i$ if $count(a, s) - count(b, s) = i$, where $count(x, s)$ is the number of $x$s in $s$. Clearly the starting state has to be $q_0$: the empty string has the same number of $a$s and $b$s.
Then it's easy to see what the transition function $\delta \colon Q \times \Sigma \to Q$ has to be: $$ (q_0, a) \mapsto q_1 \\ (q_0, b) \mapsto q_2 \\ (q_1, a) \mapsto q_2 \\ (q_1, b) \mapsto q_0 \\ (q_2, a) \mapsto q_1 \\ (q_2, b) \mapsto q_0 \\ $$
Because you want to recognize strings with $count(a, s) - count(b,s) \neq 1$ (mod 3), the accepting states are $A = \{q_0, q_2\}$.
So the DFA is $(\Sigma, Q, \delta, A, q_0)$.
Grammar
Here's a right regular grammar whose three nonterminals $S_0, S_1, S_2$ mimic the states $q_0, q_1, q_2$ of the DFA above (starting symbol is $S_0$):
$$ \begin{align} S_0 &\to a S_1 \mid b S_2 \mid \Lambda \\ S_1 &\to a S_2 \mid b S_0 \\ S_2 &\to a S_1 \mid b S_0 \mid \Lambda \\ \end{align} $$