# Deterministic Finite Automata (DFA)

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

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!