60 views

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:)

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.

by
2.2k points

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.
edited by

@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 1st language and is consequently accepted by the DFA.

okayyy got it!!

remainder can never be negative.

thank you :)