The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
228 views
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) ?
asked in Theory of Computation by Active (1k points) | 228 views
+3

It is n*m

2 Answers

+5 votes

....

answered by Boss (13.8k points)
0
In such questions where we the number of states in minimal DFA are asked, do we have to count the trap state also?
0
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
+1 vote
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.
answered by (65 points)
0
X mod n means n states are required.

So, n*m. What is m? Please explain.

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

47,139 questions
51,388 answers
178,064 comments
66,700 users