0
$\begingroup$

The question is simple and given as, alphabet $A$ is $\{a, b\}$, and language $L$ over $A$:

$L = \{w: w \in \{a, b\}^*, n(a) - n(b) = 1 \mod 3\}$. Here $n(a)$ = number of $a$ and $n(b)$ is number of $b$.

My answer is that it's not a regular language because the modular expression can be simplified as. $n(a) =n(b) +3k+1$ and hence there is a comparison in between the two alphabets. Further comparison are infinite but a finite automaton has only finite memory which are associated with states.

So we can say the above language is not regular hence no finite automaton for it. But there is a problem, I have read a book by Linz in which the above question was given stating that find the regular expression for it. I am a bit confused so any help will be appreciated. I would also be interested in a general approach to answer this type of question.

Improve this question
$\endgroup$
4
  • $\begingroup$ "because the modular expression can be simplified as [something] and hence there is a comparison in between the two alphabets" -- that sentence doesn't make any sense to me. Which to alphabets? What kind of "comparison"? $\endgroup$
    – Raphael ♦
    Sep 28 '18 at 9:22
  • $\begingroup$ @Raphael "alphabet" should be "symbol" and I think it's trying to convey the intuition that the language can't be regular for basically the same reason that $\{a^nb^n\mid n\geq 0\}$ isn't: you have to remember how many $a$s and $b$s you've seen and you'd need infinitely many different states to cover the infinite number of possibilities. (In this case, the intuition is incorrect, but I that's what it's getting at.) $\endgroup$
    – David Richerby
    Sep 28 '18 at 11:34
  • $\begingroup$ @DavidRicherby Ah, gotcha. The "because" threw me since there is no kind of reasonable reasoning (be-dum-dum-tss) here. $\endgroup$
    – Raphael ♦
    Sep 28 '18 at 11:36
  • $\begingroup$ Very similar: cs.stackexchange.com/questions/74741/… (since $a+2b$ and $a-b$ are identical mod 3) $\endgroup$
    – rici
    Sep 28 '18 at 17:40
1
$\begingroup$

Your reasoning about comparisons would be correct, if there were infinitely many numbers. But there's only three of them modulo $3$.

The automaton can be constructed directly. You need three states, one for each of the residues: $0$, $1$ and $2$. Then every $a$-transition should correspond to an increment and $b$-transition to a decrement.

Improve this answer
$\endgroup$
3
  • $\begingroup$ i have tried that way but i was unable to form dfa since in last state(remainder =2 ) where addition of a leads to first state of remainder 0 and b leads to one decreament. but what about addition of b at state having remainder 0 and if we do so then the equation is unstatisfied $\endgroup$
    – rballiwal
    Sep 28 '18 at 8:16
  • $\begingroup$ @low_burning $2$ and $-1$ are the same modulo $3$. $\endgroup$
    – Dmitri Urbanowicz
    Sep 28 '18 at 8:41
  • $\begingroup$ thanks and i really appreciate its been a while since i get rid of this stuff , thanks $\endgroup$
    – rballiwal
    Sep 28 '18 at 8:56
1
$\begingroup$

As Dimitri has already said, the number of comparisons will only be 3. Consider the three states: q0 - where the n(a) - n(b) mod 3 = 0

q1 - where n(a) - n(b) mod 3 = 1

q2 - where n(a) -n(b) mode 3 = 2

Out of these q1 will be final state.

The DFA will be: DFA

Note: If we get n(b) more than n(a). say n(a) is 0 and n(b) is 2, the automaton still works as -2 mod 3 is 1.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.