3.1.1. Introduction to the DFA¶

We start with the simplest of our machines: the Deterministic Finite Acceptor (DFA). This machine can process an input string (shown on a tape) from left to right. There is a control unit (with states), which has behavior defined for what to do when the machine sees a given symbol on the current square of the tape while in a given state. But all that the machine can actually “do” is to change state before going to the next symbol to the right. That is, an acceptor cannot modify the contents of the tape, nor decide about where the control unit goes.

Deterministic in this context has a particular meaning: When the DFA is in a given state, there is only one thing that it can do for any given input symbol. This is in contrast to a non-deterministic machine, that might have some range of options on how to proceed when in a given state with a given symbol. We’ll talk about non-deterministic automata later.

At the end of processing the letters of the string, the DFA can “accept” or “reject”. For example, a DFA that tests to see if a string is a valid integer should accept if given 6789 as input, and reject if given 67a89 or 67.89 as input. A DFA that tests to see if a string is a valid C++ variable name should accept if given SUM as input, and reject if given 1SUM as input.

1 / 21 Settings

<<<>>>

Now we'll look into some of the details about the DFA.

q0

q1

0

1

1

0

Saving...
Server Error
Resubmit

3.1.2. Some Examples¶

Here is the algorithm for how a DFA processes a string.

Here is a detailed trace on a simple input.

1 / 6 Settings

<<<>>>

In this example, we see how the machine head moves over the tape when processing input string '100'.

q0

q1

0

1

1

0

1. 1
2. 0
3. 0

q0

q1

Saving...
Server Error
Resubmit

Now let’s see how this machine accepts or rejects some strings.

1 / 29 Settings

<<<>>>

In this slideshow, we will trace the acceptance or rejection of some strings. The given machine can accept any even number (written in binary notation). You can click on any cell to see the process again starting from the clicked cell

q0

q1

0

1

1

0

1. 0
2. 0
3. 1
4. 0
5. 1
6. 0
7. 0
8. 1
9. 0

1. 0
2. 1
3. 1
4. 1

1. 0
2. 1
3. 0
4. 1
5. 0
6. 0
7. 0
8. 1
9. 0

Saving...
Server Error
Resubmit

Next is an exercise to give you practice in building a machine using the DFA machine editor. You should not need to think too hard about what machine you need, since you can simply recreate the machine that we have been using. But doing this exercise will introduce you to the machine editor that you will see a lot of in this book!

3.1.3. Advanced Concepts¶

1 / 17 Settings

<<<>>>

As you were building your first DFA, perhaps this question occurred to you: What happens if I leave out one of the transitions? What happens if the DFA is in a state and sees a symbol that has no transition? That is, what if there is no transition given for this state and this symbol (equivalently, no such edge in the graph)?

q0

q1

q2

b

a

b

q0

q1

q2

trap

b

a

a,b

a,b

a

b

q0

q1

q2

q3

0

0

0

1

1

0

1

1

Saving...
Server Error
Resubmit

3.1.4. Limits to DFAs¶

A given DFA can accept a set of strings, and a set of stings is a language. So a DFA $M$ accepts a language $L$, written $L(M)$.

Let’s now think beyond this level, and consider all possible DFAs. Each DFA accepts a language. So all the DFAs, collectively, can accept some collection of languages. This is called a family of languages. Therefore, all the DFAs together define a family of languages that they accept. We will give a name to this particular family: A language is regular if and only if there exists a DFA $M$ such that $L = L(M)$. We will explain later why we used the name “regular” for this family. For now, this is merely a definition without any other context.

The important question that this leads to is: Are there languages that DFAs cannot accept? That is, are there languages that are not regular? We won’t leave you guessing, the answer is yes. We’ll prove this later, and then introduce more powerful machines that can accept larger families of languages.