# Maximum number of words accepted by a deterministic finite automaton with 5-states

I have an exercise:

We are given a finite deterministic automaton. It has 5 states and is based on the alphabet $$\{a, b, c\}$$. It can accept $$n$$ different words, $$n <\infty$$. What maximum value can $$n$$ be?

W have 5 states so it should be something like this:

$$\varepsilon \ | \ (a|b|c) \ | \ (a|b|c)(a|b|c) \ | \ (a|b|c)(a|b|c)(a|b|c) | \ (a|b|c)(a|b|c)(a|b|c)(a|b|c)$$

$$1 + 3 + 9 + 27 + 81 = 121$$, so $$n = 121$$ - maximum number of words accepted by a DFA with alphabet $${a,b,c}$$ and 5 states.

Is it correct?

You are correct. I will try to give an informal justification:

The key is to observe that any 5-state DFA that produces a finite number of words can only produce words up to length 4, assuming the start state is included in the 5 states.

To see why this is, observe by contradiction that if it produced a word of length 5, it would have to go through 5 transitions $$s_0 \rightarrow s_1 \rightarrow s_2 \rightarrow s_3 \rightarrow s_4 \rightarrow s_5$$ for some set of states $$s_i$$. Since the DFA only has 5 states, the 6 states $$s_0, \ldots, s_5$$ cannot all be distinct. Thus this path contains a loop, and we can produce an infinite number of ever-longer words by looping repeatedly.

Thus the DFA can at most produce the words of length up to 4, which as you've observed is 121 words:

$$\varepsilon \ | \ (a|b|c) \ | \ (a|b|c)(a|b|c) \ | \ (a|b|c)(a|b|c)(a|b|c)\ | \ (a|b|c)(a|b|c)(a|b|c)(a|b|c)$$

To show that 121 is the least upper bound of possible words (in other words, that we cannot find a lower maximum), it suffices to construct a 5-state DFA that produces all 121 words. The following will do:

$$C = \{a,b,c\}$$

$$S = \{s_0, s_1, s_2, s_3, s_4\}$$, $$s_0$$ is the start state

$$F = \{s_0, s_1, s_2, s_3, s_4\}$$ (all states are accepting states)

$$T = \{(s_i,s_{i+1},a), (s_i,s_{i+1},b), (s_i,s_{i+1},c)|0\le i\le 3\}$$

• This answer treats DFA as incomplete DFA, since there is no transition from $s_4$ to another state. Jun 10, 2022 at 20:34