2 votes 2 votes Suppose L is a regular language of all a's and b's where the number of a's is divisible by m and the number of b's is divisible by n. If M is the minimal DFA accepting language L, then what is the number of states in M ? Is it nm or (n+1)(m+1) ? Theory of Computation theory-of-computation minimal-state-automata finite-automata number-of-states + – humblefool asked Nov 2, 2017 humblefool 1.7k views answer comment Share Follow See 1 comment See all 1 1 comment reply just_bhavana commented Nov 2, 2017 reply Follow Share It is n*m 3 votes 3 votes Please log in or register to add a comment.
5 votes 5 votes .... Hira Thakur answered Nov 5, 2017 Hira Thakur comment Share Follow See all 2 Comments See all 2 2 Comments reply Sumaiya23 commented Jan 24, 2018 reply Follow Share In such questions where we the number of states in minimal DFA are asked, do we have to count the trap state also? 0 votes 0 votes sanju77767 commented Apr 9, 2018 reply Follow Share yes we will count the trap state also it is not NFA it DFA for invalid string there will be a trap state if u remove that ur ans will be wrong 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes Finite automata is capable of performing modular counting. By saying mod2 it means it has seen 2 inputs for the same. Similarly for xmodn, means n states required. So, n*m. aditya rawat answered Nov 10, 2017 aditya rawat comment Share Follow See 1 comment See all 1 1 comment reply Sona Barman commented Jan 13, 2018 reply Follow Share X mod n means n states are required. So, n*m. What is m? Please explain. 0 votes 0 votes Please log in or register to add a comment.