1
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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? $\endgroup$ – David Richerby Feb 4 at 15:38
  • $\begingroup$ 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? $\endgroup$ – Jo Liss Feb 5 at 14:58
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Apass.Jack Feb 4 at 20:54
  • $\begingroup$ 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". $\endgroup$ – Jo Liss Feb 5 at 14:56

Not the answer you're looking for? Browse other questions tagged or ask your own question.