1,670 views
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) ?

2 Answers

5 votes
5 votes

....

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.

Related questions

1 votes
1 votes
1 answer
2
kislaya Pant asked May 8, 2018
1,063 views
Ques:- What are the number of final states in minimal DFA, where ∑= {a, b}, if every string starts with “aa” and length of the string is not congruent to 0 (mod 4)....
3 votes
3 votes
1 answer
3
2 votes
2 votes
1 answer
4
rahul sharma 5 asked Nov 9, 2017
936 views
Minimum number of states in DFA where:, Number of a's and Number of b's are even and epsilon is not accepted.Langugae is defined over {a,b}