Deterministic Finite Acceptors¶
1. DFA: Deterministic Finite Acceptor¶
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 in a given state and with a given symbol on the current square of the tape. All that we can “do” is change state before going to the next letter to the right. That is, an acceptor does not 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. A DFA that tests to see if a string is a valid C++ variable name should output “yes” if given SUM input.
Figure 1: Example of DFA
Note
Think about this before you read on: What information do we need to characterize/describe/define a given DFA? We want enough information so that we can “build” the machine. But no more.
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
We interpret the DFA as outputting a value of “yes” on a given input string if the DFA ends processing of that string in a final state, and we say that the DFA outputs “no” if it is not in a final state at the end of processing that string.
A DFA is a simple machine with not a lot of power. We will see that there are many questions that it cannot answer about strings. For example, it cannot tell whether \(((9+5)+a)\) is a valid arithmetic expression or not.
1.1. Example¶
Here is a graphical presentation for a DFA that accepts even binary numbers.
Figure 2: DFA Example: Even numbers. The start state is \(q_0\). State \(q_1\) is a final state.
We can assign semantic meaning to the states: the machine is in state \(q_0\) when the digits proccessed so far make an odd number, and the machine is in state \(q_1\) when the digits processed so far make an even number. Of course, our thinking about them in this way is just to help with our understanding of what is going on. Saying that this is what the states “mean” does not change the actual behavior of the machine.
Note
At this point, you should try building this machine in OpenFLAP.
Formal definition:
\(M = (Q, \Sigma, \delta, q0, F) =\)
\((\{q0,q1\}, \{0,1\}, \delta, q0, \{q1\})\)
Here is a tabular format for \(\delta\):
Note
See if you can write this table without looking at the answer.
Example of a move: \(\delta(q0, 1) = q0\)
1.2. Algorithm for DFA:¶
Now let’s see how this machine accepts / rejects some strings.
1.3. Definitions¶
\({\delta}^{*}(q,\lambda)=q\)
You didn’t go anywhere, you are still in state \(q\)
\({\delta}^{*}(q,wa)={\delta}({\delta}^{*}(q,w),a)\)
Apply \(\delta\) to all of \(w\) first (some string) and then to \(a\)
The language accepted by a DFA \(M = (Q, \Sigma, \delta, q_0, F)\) is set of all strings on \(\Sigma\) accepted by \(M\). Formally,
\[L(M) = \{w\in{\Sigma}^{*}\mid {\delta}^{*}(q_0,w)\in F\}\]Note
Draw a picture: q0 arc … some final state, any path to a final state is a string that is accepted.
This is the language accepted by DFA M. All strings formed of the alphabet such that if you start in q0 and process all the symbols in w, then you end up in a final (or accepting) state
Set of strings not accepted:
\[\overline{L(M)} = \{w\in{\Sigma}^{*}\mid {\delta}^{*}(q_0,w)\not\in F\}\]
1.4. Trap State¶
Example: Consider the language \(L(M) = \{b^na | n > 0\}\)
Note
What language is this? Answer: One or more “b” followed by one “a”.
So, here is one way to make a drawing:
Figure 3: DFA Example: Incomplete
Note
Question: Did we need state \(q_0\)?
Answer: Yes, to force at least one “b”.
Note that this is technically incomplete, in that there are transitions not being show here. The idea is that if we CAN reach an accepting state, then the string is accepted. But if we make a transition not shown in the diagram (or end up somewhere other than accepting state), then the string is not accepted.
To be complete, we can add one or more “trap” states, and put in all of the “extra” transitions. As follows.
Figure 4: DFA Example: Complete
Note that there is nothing “special” about the trap state.
Its a good idea to have states with meaningful names!
Example: \(L = \{ w \in \Sigma^* | w\) has an even number of a’s and an even number of b’s }.
Note
Other examples to consider: Can create a DFA for real numbers, integers, variable names (depending on the rules), etc.
Example: Create a DFA that accepts even binary numbers that have an even number of 1’s.
Figure 5: More complicated DFA Example
Determinism means that there is only one choice about what to do when in a given state and the machine sees a given character.
1.5. Concept: Power of DFAs¶
A given DFA can accept a set of strings (which is all that a language is). All of the possible DFAs form a class of machines. Given some class or type of Finite Automata, the set of languages accepted by that class of Finite Automata 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)\).
