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$

closed as unclear what you're asking by David Richerby, Evil, Discrete lizard, Luke Mathieson, Thomas Klimpel Feb 13 at 0:00

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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.