3.1. DFA: Deterministic Finite Acceptor¶
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.
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.
Figure 3.1.1: Schematic diagram for a DFA
Definition
Define a DFA as \((Q, \Sigma, \delta, q_0, F)\) where
\(Q\) is a finite set of states
\(\Sigma\) is the input alphabet (a finite set)
\(\delta: Q \times\Sigma \rightarrow Q\). A set of transitions like \((q_i, a) \rightarrow q_j\) meaning that when in state \(q_i\), if you see letter \(a\), consume it and go to state \(q_j\).
\(q_0\) is the initial state (\(q_0 \in Q\))
\(F \subseteq Q\) is a set of final states
3.1.2. Some Examples¶
The algorithm for how a DFA processes a string:
Here is a detailed trace on a simple input.
Now let’s see how this machine accepts / rejects some strings.
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.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 of languages. Therefore, the DFAs 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.
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.
