Question

Suppose that \(S\) and \(I\) are finite sets such that \(\left| S \right| = n\) and \(\left| I \right| = k\). How many different finite-state automata \(M = \left( {S,I,f,{s_0},F} \right)\) are there where the starting state \({s_0}\) and the subset \(F\) of \(S\) consisting of final states can be chosen arbitrarily

\(a)\)if the automata are deterministic\(?\)

\({\bf{b)}}\)if the automata may be nondeterministic\(?\) (Note: This includes deterministic automata.)

Short answer

a) There are \({2^n}{n^{nk + 1}}\) finite-state automata are deterministic

b) There are \(n{2^{{n^2}k + n}}\) finite-state automata are nondeterministic

Step-by-step solution

Definition

Product rule If one event can occur in m ways and a second event can occur in n ways, then the number of ways that the two events can occur in sequence is then \(m \cdot n\).

\(M = \left( {S,I,f,{s_0},F} \right)\)is a finite-state automaton

\({s_0}\)is the starting state

S and I are finite sets

\(\left| S \right| = n\)

\(\left| I \right| = k\)

(a)The automata are deterministic

A deterministic finite state automaton is a five-tuple \(\left( {S,I,f,{s_0},F} \right)\) where S is the set of states, I is the input alphabet, f is the transition function that assigns the next state to a pair of a state and input, \({s_0}\) is the starting state and F is the set of final states.

There are \(\left| S \right| = n\) possible choices for the starting state \({s_0}\).

The function f has a state and input symbol as input (while there are \(nk\) such possible inputs), while the output of the function is a single state \({s_i}\). Since there are \(\left| S \right| = n\) states, the number of possible functions f is then \((\underbrace {n \times n \times \ldots \times n}_{nk repetitions } = {n^{nk}}\) by the product rule.

Finally, you need to determine the number of possible choices for the set F. For each of the \(\left| S \right| = n\) states, you have 2 options: the state is in F or the state is not in F. The number of possible sets F is then \((\underbrace {2 \times 2 \times \ldots \times 2}_{n repetitions } = {2^n}\) by the product rule.

By the product rule, there are then \(n \times {n^{nk}} \times {2^n} = {2^n}{n^{nk + 1}}\) possible deterministic automata.

Therefore, there are \({2^n}{n^{nk + 1}}\) finite-state automata are deterministic

(b) The automata are nondeterministic

A nondeterministic finite state automaton is a five-tuple \(\left( {S,I,f,{s_0},F} \right)\) where S is the set of states, I is the input alphabet, f is the transition function that assigns a set of possible states to a pair of a state and input, \({s_0}\) is the starting state and F is the set of final states.

There are \(\left| S \right| = n\) possible choices for the starting state \({s_0}\).

The set F needs to be a subset of S. For each of the \(\left| S \right| = n\) states, you have 2 options: the state is in F or the state is not in F. The number of possible sets F is then \((\underbrace {2 \times 2 \times \ldots \times 2}_{n repetitions } = {2^n}\) by the product rule.

The function f has a state and input symbol as input (while there are \(nk\) such possible inputs), while the output of the function is a subset of S. Since there are \({2^n}\) subsets of S, the number of possible functions f is then \(\underbrace {{2^n} \times {2^n} \times \ldots \times {2^n}}_{nk repetitions } = {\left( {{2^n}} \right)^{nk}} = {2^{n(nk)}} = {2^{{n^2}k}}\) by the product rule.

By the product rule, there are then \(n \times {2^n} \times {2^{{n^2}k}} = n{2^{{n^2}k + n}}\) possible nondeterministic automata.

Therefore, there are \(n{2^{{n^2}k + n}}\) finite-state automata are nondeterministic