PETER LINZ-DFA

Question

The minimum number of states for these 2 languages:
L1={w: (n(a)-n(b)) mod 3=2}

L2={w: (n(a)-n(b)) mod 3=0}
 

I am getting 9 for both of them .Please verify:)

Answer 1

I think the minimum no. of states in both the DFAs that accept the above languages will be 3.


Fig: DFA that accepts strings belonging to the 1st language.


Fig: DFA that accepts strings belonging to the 2nd language.

Comments

what figures are u referring to ?

I can’t see any.

---

Sorry, they didn’t get uploaded the first time. I have edited the answer and uploaded them again.

---

@debargha 
QUERY 1::

even I got these figures.
but see the transition for ‘b’ from state r=0 ,for the first diagram..
If I give string as ‘b’ (it is of length 1) then also it gets accepted which is wrong.
also it accepts ‘bbbaa’ which is worng.

QUERY 2::

Accha are we applying modulus opeartor here?
I mean |b-a|=|a-b|?

QUERY 3::

In the second diagram if we apply bbbaa  where |n(a)-n(b)|=1 it is landing in state r=2,but it should land in r=1,will this be a problem?

---

For the string ‘$b$’, $a – b = 0 – 1 = -1$
$\therefore (a – b) (mod \ 3)  = (-1) \ mod \ 3 = 2 , (\because \color {Blue} {-1} = \color {Blue} {3} \times (-1) + \color {Red} {2})$

Therefore, it belongs to the 1^st language and is consequently accepted by the DFA.

---

okayyy got it!!

remainder can never be negative.

thank you :)