The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote
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

It is n*m

2 Answers

+5 votes


answered by Boss (13.8k points)
In such questions where we the number of states in minimal DFA are asked, do we have to count the trap state also?
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)
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
66,700 users