in Theory of Computation
60 views
0 votes
0 votes

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

in Theory of Computation
by
73 points
60 views

1 Answer

2 votes
2 votes
 
Best answer

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.

selected by
by
2.2k points

5 Comments

what figures are u referring to ?

I can’t see any.
0
0
Sorry, they didn’t get uploaded the first time. I have edited the answer and uploaded them again.
0
0
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?

0
0

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.

1
1
okayyy got it!!

remainder can never be negative.

thank you :)
1
1
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.