751 views
0 votes
0 votes
How many ‘n’ state FA are possible with ‘m’ symbols with –

(i) Designated initial state

(ii) With designated initial and final state

(iii) With no designated initial and final state

How can I approach this?

1 Answer

Best answer
7 votes
7 votes
i. $2^{n}*n^{mn}$

ii.$n^{mn}$

iii.$2^{n}*n^{mn}*n$

$2^{n}$ → No designated final state.For each state we have two choice either final or non final.

n → No designated initial state.We have n choice for initial state.Any of the n states can           be initial state.
selected by

Related questions

0 votes
0 votes
2 answers
1
gateexplore asked Jun 11, 2023
197 views
Construct finite automaton corresponding to regular expression (a + b)*cd*e
0 votes
0 votes
2 answers
2
gateexplore asked Jun 11, 2023
221 views
Construct NFA for the set of strings Σ={0, 1} of alternate 0's and 1's
0 votes
0 votes
1 answer
3
gateexplore asked Jun 11, 2023
411 views
Construct an NFA that will accept string of 0's, 1's and 2's beginning with a 0's followed by an odd number of 1's and ending with any number of 2's. Please give the answ...
0 votes
0 votes
0 answers
4
Overflow04 asked Oct 31, 2022
297 views
Can finite automata do multiplication.