0

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)

Kolmin
  • 4,083
Talen Kylon
  • 563

1 Answers1

2

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

BrianO
  • 16,579
  • I don't think that $S_2\to \ldots |\Lambda$ is intended – Hagen von Eitzen Oct 13 '15 at 20:43
  • Thank you for breaking this down in detail. It's a very nice approach to the problem. To test my understanding; Lets say we wanted to recognize strings with count(a,s) - count(b,s) != 0 (mod 3). The accepting state would then be just {q0}, correct? – Talen Kylon Oct 13 '15 at 20:48
  • 1
    Oops no: if you want to recognize strings with count(a,s) - count(b,s) != 0 (mod 3), then you want the difference of counts to be either 1 or 2 (yes?) So the accepting states would be ${q_1, q_2}$. If $q_0$ were the only accepting state, then the language accepted would be: all strings s with count(a,s) = count(b,s) (mod 3). – BrianO Oct 13 '15 at 20:50
  • Ah yes, sorry a miscommunication between my brain and fingers! I appreciate your help. – Talen Kylon Oct 13 '15 at 20:54
  • @ Hagen von Eitzen No? We want to accept strings $s$ with derivations $S_0 \Longrightarrow^* s S_2$ – BrianO Oct 13 '15 at 21:00
  • If we wanted strings where count(a,s) - count(b,s) = odd, the only accepting state would be {q1}, am I correct in this? – Talen Kylon Oct 13 '15 at 21:01
  • @Talen Kylon yep, correct. – BrianO Oct 13 '15 at 21:02