150 views
The minimum number of state in the DFA for the language $L = \{ w \mid (n_a(w)+2n_b(w))mod \hspace{0.1cm} 3<2 \}$ is
retagged | 150 views

+1 vote

This is "mod n" language..and the idea behind construction of DFA for "mod n" language is that Make States corresponding to each possible remainder of $n$ and then make transitions accordingly. Such machines are simplest to construct.

The DFA for the given language will look like the following :

answered by Boss (21.8k points)
selected
0
@deepak sir in all this type of question

{Mod n}  I have to follow the same procedure like taking remainder and appropriately chose the state or there is some trick or easy way to do fast ?
0

{Mod n}  I have to follow the same procedure like taking remainder and appropriately chose the state

Remember that this is a guideline only, Not some concrete theorem or algorithm. With more and more Practice, you will get to know when and where we can use it and where we can not. For $modN$ languages, Most probably we can apply this idea of construction.

there is some trick or easy way to do fast ?

Tricks might be there...But then those tricks will be applicable for specific type of problems only. And This way is itself fast way.  Just do lots of practice and be comfortable with all the types of problems and become P.T. Usha of constructing DFA.

0
@Deepak Poonia (Dee) ,abb also in the language but this dfa is not accepting .right??
0

no, abb is not in the language...

w=abb

na(w) = 1

nb(w) = 2

( na(w) + 2* nb(w) ) mod 3 < 2

= ( 1 + 2*2 ) mod 3 < 2

= (5) mod 3 < 2

= 2 < 2 ---- false ===> abb not in the language.

0
Okkk got it now , actually I was thinking that {$n_a(w)+2n_b(w)$}=abb ,but now got it when iItake bb then in the lang it will become bbbb .thanks
0
Hi,

Shouldn't aa also be accepted?
0

@surbhijain93, becuase (2+2*0)mod3 = 2 <2 (is not less than), so not accepted.

0
Oh yes, Thank you.
+1 vote

I couldn't draw the diagram properly thats why i am giving one of the image drawn in book.

Here the states 00, 02, 10, 11, 21, 22 will be the final states as the condition is sum of (n+ 2nb) mod 3 < 2

answered by Active (1.1k points)
0
@karan thnxx for solution
0
What are the final states again ?

Is $20$ a final state or not ?

1
2