Determinisic Finite-State Automata

Last time, we discussed a systematic way to describe and build certain sets of strings called the regular languages. Now, we’re going to turn the problem on its head; given a string, how might we decide if it belongs to a particular language (that is not necessarily regular?) For example, suppose we want to process a binary string w \in \{0, 1\}^* to decide if the number of 1s is not divisible by 3, i.e. \#(1, w) \equiv 0 \pmod 3? Let’s keep our “model of computation” as simple possible. Maybe we can get away with reading each character, one by one, like in this simple little program:

Num1sDivisbleBy3(w[1..n])
  rem <- 0
    for i <- 1 to n
      if w[i] = 1
        rem <- rem + 1 (mod 3)
  return (rem ≠ 0)

Worries about syntax aside, there’s some interesting things going on here with our single variable: First, it takes on only three possible values or states, \{0, 1, 2\}. Second, the next state we transition to is completely determined by the current state and the next character we read from w.

Therefore, there are a couple more concise ways we can model the program state and its transitions. We could use a table:

state/character	0	1	return true if final state?
0 (start here)	0	1	no
1	1	2	yes
2	2	0	yes

Or, even better, in my opinion, draw a little transition graph:

However we describe it, if we stop on the 0 state, then we should accept that w has the property we want.

The object we just described, both as a table and as a transition graph, is an example of a finite-state machine or a deterministic finite-state automata (DFA). It’s finite, because it has a finite number of states/configurations it can be in. It’s deterministic, because its behavior/state transitions are completely determined by the input string. We’ll discuss non-determinism later.

(Finite-state) automata are not a new concept, and they appear as many objects you encounter day-to-day such as:

• A clock with no minute hand. It has 720 states, one for each hour-minute pair.
• A Rubik’s cube, which has approximately 519 quintillion states and exactly 12 different “inputs” that take you between them.
• Traffic lights and other simple computery looking things.

And here we’re using them as a model of computation for making decisions about strings.

Formal definitions

We’ve seen three representations of a DSA, but I’ve yet to precisely say what a DSA really is from a mathematical perspective. And me not doing so would be very bad if we actually wanted to formally say what these things are capable of. It will also help you in describing them without having to draw too much.

A DFA consists of five components:

• An arbitrary finite set \Sigma, the input alphabet.
• Another arbitrary finite set Q whose elements are the states.
• An arbitrary transition function \delta: Q \times \Sigma \to Q.
• A start state s \in Q.
• A subset A \subseteq Q of accepting states.

We often denote the components of a DFA M by equating it with a tuple, i.e., M = (\Sigma, Q, \delta, s, A). When the alphabet is understood in context, we may drop the first component, i.e., M = (Q, \delta, s, A).

The behavior of the machine is determined by the input string w. It reads the symbols in w one at a time in order (beginning to end/left to right). At all times, it has a current state q which is initially the start state s. When it reads a symbol a from w, its current state transitions from q to \delta(q, a). After all symbols have been read, the machine accepts w if the current state is in A, and it rejects w otherwise.

The transition function \delta describes how to move away from a state while reading a single character. We can extend the transition function to describe how to move away from a state while reading in a whole string. Doing so will help us both formally define what it means for a machine to accept and also to use notation to describe machines based on the behavior of other machines. The extended transition function \delta^*: Q \times \Sigma^* \to Q is defined as follows: \delta^*(q, w) := \begin{cases} q & \text{if $w = \varepsilon$}\\ \delta^*(\delta(q, a), x) & \text{if $w = ax$}. \end{cases} In other words, if w = ax, go from state q to \delta(q, a) and then follow the suffix x out of \delta(q, a). Formally, the DFA M = (Q, \delta, s, A) accepts w if and only if \delta^*(s, w) \in A, and it rejects w otherwise. The notation literally says, “the string w takes the machine from the start state s to an accept state in A.”

Whew! Going back to our original example, we had

• \Sigma = \{0, 1\} (these are the symbols 0 and 1),
• Q = \{0, 1, 2\} (this is the set of actual natural numbers below 3),
• \delta(q, a) = \begin{cases} q & \text{if $a = 0$}\\ (q + 1) \mod 3 & \text{if $a = 1$}, \end{cases}
• s = 0,
• and A = \{1, 2\}.

Note that 1 and 2 are exactly the states we used a double circle for in the transition graph shown earlier. Also note how using the formal notation allowed me to more concisely explain the transitions. I only needed two lines instead of six table entries or arrows!

And now for example’s example, if we want to know about, say, w = 01010110101… \begin{aligned} \delta^*(s, w) &= \delta^*(0, 01010110101)\\ &= \delta^*(\delta(0, 0), 1010110101)\\ &= \delta^*(0, 1010110101)\\ &= \delta^*(\delta(0, 1), 010110101)\\ &= \delta^*(1, 010110101)\\ &= \delta^*(\delta(1, 0), 10110101)\\ &= \delta^*(1, 10110101)\\ &\quad\vdots\\ &= \delta^*(0, \varepsilon)\\ &= 0. \end{aligned} And 0 \notin A, so the DFA rejects w. In other words, the machine has determined that \#(1, w) is a multiple of 3.

Descriptions in detail

In general, you do not need to write out line by line definitions of each part of the DFA like we just did to fully describe one, but it is often helpful, especially for DFAs where you can concisely explain transitions between states using a bit of math. If you want to be explicit about every individual transition, though, you can make table with a row for each state, a column for each possible transition, and one additional column saying if a state is accepting. In addition to drawing the table, be sure to indicate the start state! With our new formalisms, our example would be:

q	\delta(q,0)	\delta(q, 1)	q \in A?
0	0	1	False
1	1	2	True
2	2	0	True

starting at state 0.

Alternatively, you can draw a transition graph with one node per state labeled by its state, one edge per transition labeled by the input character causing the transition. We draw a second circle inside the node for each accepting state and a little arrow coming in from nowhere for the state state. Do not assume we can guess your start state. Draw that incoming arrow.

Again, if you have a lot of states (hint hint), it may be better to describe many of them and their transitions all at once using mathematical notation like we did earlier.

If you want to actually formally prove that a DSA accepts exactly the strings you’d like it to, then you have to do induction. The general pattern is to make a broader claim about where the extended transition function \delta^* takes each state q based on the properties of an input string w. Then, you prove the broader claim using induction on w. It’s the same pattern as every other proof about strings so far, except you’re likely to have more cases, maybe one per state. That said, formally proving things about individual DFAs doesn’t tend to come up in this class, if only because there are more important things to do, such as…

Designing and describing DFAs

Example

Can we make a DFA accepting the language of binary strings that contain a 1?

We only need to remember if we’ve seen a 1 yet, so we can go with two states. It’s very helpful for both us and you if you give the states nice names like “yes” and “no”. We stay in the “no” state until we’ve seen a 1. Afterward, we stay in the “yes” state forever. We should accept if we’re in the “yes” state, and we start in the “no” state.

There are a couple things to notice about how the drawing of the transition graph. First, I explicitely indicated the start state by drawing an extra arrow into it, and I explicitely indicated the accepting state by adding a second circle inside of its node. Again, I gave descriptive names to the states to explain what they’re for. Did we see the 1 yet? Yes or no. For the homework (TODO: maybe the exams also, check the standard rubrics), you must give your states informative names and say more about their purpose if it isn’t already completely obvious from the name alone.

Example

Now lets try designing a DFA for all binary strings with 11 as a substring. Erickson describes one method of doing so: Write a little program that reads one symbol at a time, and translate every possible combination of variable values into a state. However, in the interest of time, and because that approach generates a ridiculous number of states if you’re not careful about how many variables you use, we’ll be a little more direct.

We need to track two things for this example. First, we should track “yes” or “no” whether we’ve ever seen the substring like before. Second, we need to remember at least the one previous symbol read so we know if we’re possibly about to see the second 1 in a row. Unfortunately, there are three possibilities for “previous symbol”. They are 0, 1, and, “we haven’t seen one yet!”. So to track both variables, we have 2 \cdot 3 = 6 states. Fortunately, once you nail down what you want the states to mean, the transitions aren’t too hard to work out. Also, it looks like all those “yes” states should be accepting, and we should start by saying “no” and that we haven’t read anything yet.

This solution doesn’t feel great, though. First, there’s one state that is impossible to reach from the start state. That’s technically fine, but a waste of ink. In fact, there’s no need to keep around the “what did we see last” data at all once we can accept, so all three of those states on the right could have been one state. Finally, there’s no functional difference between not having seen anything and having last seen 0; all that really matters before we reach an accept state is whether we last saw 1. So let’s try again with three states total representing not seeing a 1 last, seeing a 1 last, and having seen the 11 at some point in the past.

Example

How about all binary numerals w that are a multiple of 5. In other words, we want sequences of binary digits that when interpreted as a number in binary give us a multiple of 5 (here written in decimal, I know.)

Let’s try again with remembering the remainder like we did at the beginning. That strategy suggests using five states named 0, 1, 2, 3, and 4. In this case, figuring out the transition function is a little bit more tricky. Suppose we’ve read in the binary number x. The next bit we read a is to the right of everything in x. So, in the new number xa, every bit of x is now worth twice what it used to be, and then we add a to get the total. Fortunately, all of this can happen mod 5, because all we care about is whether we’re 0 \mod 5 or not.

The specifics of what state go to one stare are a bit hairy here, so I might recommend describing this DFA using mathematical notation:

• Q = \{0, 1, 2, 3, 4\}
• \delta(q, a) = (2q + a) \mod 5
• s = 0
• A = \{0\}

We could also write out all the states and transitions explicitly using a table:

q	\delta(q,0)	\delta(q, 1)	q \in A?
0	0	1	True
1	2	3	False
2	4	0	False
3	1	2	False
4	2	0	True

Start at 0.

Or, if we really wanted to, we could describe the DFA using another transition graph:

Eww.

Example

Let’s end with all binary strings beginning with 001: Similar to earlier, we want to track which characters of the substring we’ve seen and accept forever once we’ve seen 001. However, if we see an undesired character before fully reading 001, we reject forever.

We can draw the above DFA a bit more simply by adapting the convention that a missing outgoing edge from a state means you go into a permanent fail state. You need to write you’re using that convention, though, so we know you didn’t just forget something.