The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
102 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
asked in Theory of Computation by (181 points)
retagged by | 102 views

2 Answers

0 votes
Best answer

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 (13.2k points)
selected by
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 (329 points)
0
@karan thnxx for solution
0
What are the final states again ?

Is $20$ a final state or not ?


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

36,157 questions
43,608 answers
123,961 comments
42,860 users