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, "yes" if 6789 is a valid integer, or if SUM is a valid variable name in C++.
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
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¶
DFA that accepts even binary numbers.
Figure 2: DFA Example: Odd numbers
We can assign meaning to the states: \(q_0\) for odd numbers, \(q_1\) for even numbers,
Note
At this point, you should try building this machine in JFLAP.
Formal definition:
\(M = (Q, \Sigma, \delta, q0, F) =\)
\((\{q0,q1\}, \{0,1\}, \delta, q0, \{q1\})\)
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:¶
Example of a trace: 11010
Pictorial Example of a trace for 100:
Figure 3: DFA Example: Odd numbers trace
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:
Todo
| type: | Drawing |
|---|
Show the minimal form of the next drawing without trap state, etc.
Note that this is technically incomplete, in that there are transitions not being show here. The idea is that if we CAN reach and 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)\).
