# Maximum number of words in deterministic finished automata with k-states [closed]

I have exercise:

We have a given finished deterministic automata. It has 5 states and is based on the alphabet {a, b, c}. It can create n different words (we assume that n < inf). 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 in DFA with {a,b,c} alphabet and 5 states.

Its okay?

• I don't understand your question. What's a "finished" automaton? (Do you mean finite?) What do you mean by an automaton "creating" words? And you've already answered your own question, so what's left for us to do? – David Richerby Feb 4 '19 at 15:38
• Hey Bernie, I've left an answer assuming that you meant finite automata. If that's what you meant, may I suggest editing your question and title, so that it's easy to find for future readers googling for it? – Jo Liss Feb 5 '19 at 14:58

## 1 Answer

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

• Nice answer. However, if all states are accepting states, a DFA should accept all words. You missed the non-accepting state. Also, please point out the incorrect usage of terms in the question lest the question asker believe you agree to the usage. – John L. Feb 4 '19 at 20:54
• We do accept all states here—that's intentional. Regarding terminology, I've left a comment on the original question. Maybe we can edit it if he indeed meant "finite". – Jo Liss Feb 5 '19 at 14:56