1
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

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$
1
  • 1
    $\begingroup$ This answer treats DFA as incomplete DFA, since there is no transition from $s_4$ to another state. $\endgroup$
    – John L.
    Jun 10, 2022 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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