The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
195 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 Junior (947 points) | 195 views
+3

It is n*m

2 Answers

+4 votes

....

answered by Boss (12.7k 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.


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

38,115 questions
45,622 answers
132,338 comments
49,308 users