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

Question

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?

Answer 1

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\}$