2
$\begingroup$

In computational theory for deterministic finite automata, there is a 5-tuple representation containing $Q$, $\Sigma$, $\Delta$, $Q_0$ and $F$. I am wondering how one understands thinking about the number of states to construct such a DFA.

Example:

$$\{w \in\{0,1\}^*\mid w\text{ contains at least two $0$s but does not contain }000\}\,.$$

In the solution, there are 7 states required, $(q_0, q_1, ..., q_7)$.

How should one typically begin understanding the sequence in which they write their states to then cross $\Sigma$ and $Q$ to find the transitions?

$\endgroup$
4
$\begingroup$

Here is one way of thinking about it. You are receiving a sequence of zeros and ones. At each moment the sequence might stop and you need to decide to accept or reject the resulting word. At each point in time, think about what properties of the sequence you need to remember to decide whether to accept a word or reject it. The number of these properties is a proxy for the number of states. The properties also suggest descriptive names of states.

For this problem, you need to know if you have seen exactly one zero, at least two zeros, and if you have seen three consecutive zeros. In case you have seen exactly one zero, you need to know if it is the last character (this gives 2 states). In case you have seen at least two zeros you need to remember the last two characters of the string (this gives 4 states, in principle, but in this case two can be combined for a total of 3). You need to remember if you have seen 3 consecutive zeros (1 more state). You also need a start state for a total of 1 (start) + 2 + 3 + 1 = 7 states.

So you can describe a state by a tuple (a,b), where a is 1 if you've seen exactly one zero so far, and 2 if you have seen at least two zeros, and b indicates the last bits you've seen. You can have the following states:

(0,*) - haven't seen any zeros yet, aka start state

(1,0) - have seen one zero and it is the last character of the string

(1,1) - have seen one zero, but it was some time before, it is no longer the last character

(2,00) - have seen at least 2 zeros, and the last two characters are zeros - DANGER - one more zero and I need to reject

(2,10) - have seen at least 2 zeros, and the last two characters are 10 - we are relatively safe, because we need to see 2 zeros before we decide to reject

(2,*1) - have seen at least 2 zeros, and the very last character is 1 - we are quite safe, we'll have to see 3 zeros before we decide to reject.

All the above states are assuming you have not seen three consecutive zeros. Of course, once you decide to reject due to three consecutive zeros, you always reject - this gives one more state.

$\endgroup$
2
$\begingroup$

The simplest way to solve this, perhaps with more than the minimum number of states, is to use the product construction:

  1. Come up with an automaton that accepts all words containing at least two 0s. You can do this with 3 states.

  2. Come up with an automaton that accepts all words not containing the substring 000. You can do this with 4 states. (If you find this difficult, first construct an automaton that accepts all words containing the substring 000.)

(All automata are deterministic.)

Applying the product construction, we get an automaton with 12 states. Some of its states will be unreachable, however, and some of them will be clearly equivalent. This way you can reduce the number of states, perhaps all the way to the 7 states in the solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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