3 votes 3 votes Number of final states in minimal DFA where $\sum = \{ a,b \}$ $L = \{ w| n_a(w)mod\ 3 \geq n_b(w)mod\ 2\}$ Theory of Computation theory-of-computation minimal-state-automata finite-automata + – Lokesh . asked Jan 10, 2017 Lokesh . 1.6k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 8 votes 8 votes Let every state be represented as $(n_a(w)mod\;3,n_b(w)mod\;2)$, then the DFA will look like : And clearly it contains $5$ final states. Drawing DFA is not necessary as we could form all $6$ possibilities of $\left ( \bf{\color{blue}{n_a(w)mod\;3}},\bf{\color{red}{n_b(w)mod\;2}} \right )$ which are $\big \{\bf {\color{blue}{0}}{\color{red}{0}},{\color{blue}{0}}{\color{red}{1}},{\color{blue}{1}}{\color{red}{0}},{\color{blue}{1}}{\color{red}{1}},{\color{blue}{2}}{\color{red}{0}},{\color{blue}{2}}{\color{red}{1}} \big\}$ and each of these is a state in the DFA and look among these $6$ states that how many states satisfy constraint $n_a(w) mod\;3 \ge n_b(w) mod\;2$. mcjoshi answered Jan 10, 2017 edited Jan 10, 2017 by dd mcjoshi comment Share Follow See 1 comment See all 1 1 comment reply dd commented Jan 10, 2017 reply Follow Share minimal..precise..quick !! nice answer ! 1 votes 1 votes Please log in or register to add a comment.
3 votes 3 votes If we draw DFA of L = {na(w)mod 3 && nb(w) mod 2 }. minimum number of states = 6 = {00,01,10,11,20,21}; these are residue of a,3 and b,2 respectively So only one state where we will get na(w)mod 3 < nb(w) mod 2, So Answer should be 6-1= 5. target2017 answered Jan 10, 2017 target2017 comment Share Follow See all 0 reply Please log in or register to add a comment.