1 votes 1 votes 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 Theory of Computation theory-of-computation finite-automata minimal-state-automata + – Shivani gaikawad asked Jun 5, 2018 • retagged Jun 5, 2018 by Subarna Das Shivani gaikawad 960 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 4 votes 4 votes 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 : Deepak Poonia answered Jun 5, 2018 • selected Jun 6, 2018 by Shivani gaikawad Deepak Poonia comment Share Follow See all 8 Comments See all 8 8 Comments reply Shivani gaikawad commented Jun 6, 2018 reply Follow Share @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 votes 0 votes Deepak Poonia commented Jun 6, 2018 reply Follow Share {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 votes 0 votes Prateek Raghuvanshi commented Jun 12, 2018 reply Follow Share @Deepak Poonia (Dee) ,abb also in the language but this dfa is not accepting .right?? 0 votes 0 votes Shaik Masthan commented Jun 12, 2018 reply Follow Share 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 votes 0 votes Prateek Raghuvanshi commented Jun 12, 2018 reply Follow Share 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 votes 0 votes surbhijain93 commented Jun 21, 2018 reply Follow Share Hi, Shouldn't aa also be accepted? 0 votes 0 votes Shubhgupta commented Jun 21, 2018 reply Follow Share @surbhijain93, becuase (2+2*0)mod3 = 2 <2 (is not less than), so not accepted. 0 votes 0 votes surbhijain93 commented Jun 22, 2018 reply Follow Share Oh yes, Thank you. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes 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 (na + 2nb) mod 3 < 2 !KARAN answered Jun 5, 2018 !KARAN comment Share Follow See all 2 Comments See all 2 2 Comments reply Shivani gaikawad commented Jun 5, 2018 reply Follow Share @karan thnxx for solution 0 votes 0 votes Deepak Poonia commented Jun 5, 2018 reply Follow Share What are the final states again ? Is $20$ a final state or not ? 0 votes 0 votes Please log in or register to add a comment.