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), 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. All that the machine can “do” is change state before going to the next symbol to the right. That is, an acceptor cannot modify the contents of the tape.

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 answer “yes” or “no”. For example, a DFA that tests to see if a string is a valid integer should output “yes” if given 6789 as input, and “no” if given 67a89 or 67.89 as input. A DFA that tests to see if a string is a valid C++ variable name should output “yes” if given SUM as input, and “no” 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¶

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 / 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)$.

But go beyond this. Think about all possible DFAs. And each DFA accepts a language. So all the DFAs, collectively, can accept some collection of languages. This is called a family. Therefore, the DFAs define a family of languages that they accept. A language is regular if and only iff there exists a DFA $M$ such that $L = L(M)$.

The important question now 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.