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 916 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 Show 5 previous comments 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.