This section will be about Deterministic Finite Automata (DFA) and regular languages, a family of languages that are tightly connected to DFAs. You can find the notes related to this section (also partially transcribed on this page) here.

What's a DFA?

A DFA is the most “primitive” computational machine that we will see in the course. This machine performs a sequence of deterministic operations given an input - a string - which leads to it either outputting “accept” or “reject”. The language recognized or accepted by a DFA is the set of strings that the DFA accepts. A DFA also has a finite amount of memory. We will see that this will prove to be its major limitation in accepting more complex languages. The formal definition of a DFA is as follows

Definition. A deterministic finite automata (DFA) \(M\) is a 5 element tuple \(M = (Q, \Sigma, \delta, q_0, F)\) where

  • \(Q\) is the set of states of \(M\)
  • \(\Sigma\) is the alphabet of the strings inputted into \(M\)
  • \(\delta: Q \times \Sigma \rightarrow Q\) is the transition function of \(M\)
    • This can be represented graphically as we will see shortly or in a table.
  • \(q_0\) is the initial state, where computations begin
  • \(F\) is the set of accept or final states

An example DFA

Example. Here is an example of a DFA \(M_1 = (\{q_0, q_1, q_2\}, \{0,1\}, \delta, q_0, \{q_1\})\) where we represent \(\delta\) graphically as follows

q₀ q₁ q₂ 0 0,1 1 0,1

What happens when this machine receives \(010\) as an input? What about \(101\)?

Regular languages

We know DFAs as language acceptors or recognizers. In fact, languages that can accepted by DFAs belong to the family of regular languages. You can think of this family as containing languages that are “simple enough” to be recognized by a DFA. We have thus already begun creating a hierarchy of computational power with the DFA at the bottom of this hierarchy. In other words, there appears to be a relationship between the “complexity” of a language and the “power” required for a DFA to accept it. This should give you the idea that there are perhaps more complicated languages that cannot be accepted by a DFA. Can you think of any?

Exercises

Exercise. Create DFAs that accept the languages \(\Sigma^*\), \(\{\}\) and \(\{\lambda\}\).

Exercise. Create a DFA that accepts the language \(L = \{w \in \Sigma^* : w \text{ has an even number of 1s} \}\).

Exercise. Create a DFA that accepts the language \(L = \{w \in \Sigma^* : w \text{ does not contain 01} \}\).

Exercise. Create a DFA that accepts the language \(L = \{w \in \{a, b\}^* : n_a(w) \leq 1 \}\). Prove the correctness of your machine.

Exercise. Create a DFA that accepts the language \(L = \{w \in \Sigma^* : w \text{ has an even number of as and an odd number of bs} \}\).

Exercise. Create a DFA that accepts the language \(L = \{w \in \Sigma^* : w \text{ starts with 01 and ends with 10} \}\).

Exercise. Create a DFA that accepts the language \(L = \{w \in \Sigma^* : n_0(w) = 3, n_1(w) \geq 2 \}\).

Exercise. Create a DFA that accepts the language \(L = \{w \in \Sigma^* : n_0(w) + 2n_1(w)\mod 5 < 1 \}\). This one if fun!