Finite Automata

Deterministic machines, language recognition, and closure properties

Two opening problems

Consider these two programming problems:

1. Design a program that takes any input word and outputs 1 when the length of the word is a multiple of four, and 0 otherwise.
2. Design a program that sorts any input sequence of \(n\) words, where \(n\) may be any natural number.

How should we measure the complexity of each program? The second problem naturally leads us to count operations as the input grows. The first invites a different question: how much memory must a machine retain while reading the input?

To determine whether a word’s length is divisible by four, we do not need to remember the entire word or even its exact length. We only need to remember the current remainder modulo four. Four possible situations—and therefore four states—are enough.

This is the central idea behind a finite automaton: computation using a fixed, finite amount of memory.

Models of computation

The purpose of a computational model is to isolate the essential capabilities of computers and programs so that we can reason about them mathematically.

Machine	Memory or capability	Associated languages
Finite automaton	A finite set of states	Regular languages
Pushdown automaton	A finite control plus a stack	Context-free languages
Turing machine	A finite control plus an unbounded tape	Recursive and recursively enumerable languages

Finite automata are our first—and least powerful—model.

Recall: languages as problems

For a language \(L\) and an input string \(s\), language recognition asks:

Is \(s\in L\)?

A machine \(M\) recognizes \(L\) if it can correctly answer this question for every possible string \(s\).

The power of a model of computation can therefore be described by the set of languages its machines can recognize. In this setting:

• a language represents a decision problem;
• a string represents a possible input; and
• language recognition represents computation.

Deterministic finite automata

A deterministic finite automaton (DFA) consists of:

1. a finite set of states;
2. one designated start state;
3. a set of accepting states; and
4. a transition function that specifies exactly one next state for each combination of current state and input symbol.

The first DFA from the lecture. An incoming arrow marks the start state, and a double circle marks an accepting state.

The machine begins in its start state and reads the input from left to right. Each symbol determines which transition it follows. After the final symbol, the machine accepts precisely when its current state is an accepting state.

Tracing a DFA

Consider the following two-state machine and trace the input 101 one symbol at a time.

A two-state DFA tracing exercise.

The language of a machine, written \(L(M)\), is the set of all strings that the machine accepts:

\[ L(M)=\{w\in\Sigma^* : M\text{ accepts }w\}. \]

To describe this machine’s language, ask what must be true about a string for its computation to finish in the accepting state.

Here is a second example:

A three-state DFA language-identification exercise.

Changing only which states are accepting changes the language—even if every transition remains unchanged.

DFAs in practice

Many systems can be modeled as finite-state machines:

• an on/off switch;
• an automatic door controller;
• an elevator controller;
• word search in a text editor;
• basic email-address validation;
• a newspaper vending machine; and
• pattern-based computer-virus detection.

An automatic door is a simple example of a system whose behavior can be represented by a finite number of states.

The physical system itself is not literally a DFA. The DFA is a useful abstraction of the states the system can occupy and the events that move it from one state to another.

DFA design example

Design a DFA that recognizes strings over \(\{0,1\}\) containing an even number of 1s.

The machine only needs to remember one fact about the prefix read so far:

• even: the number of 1s seen so far is even;
• odd: the number of 1s seen so far is odd.

The even state is both the start state and an accepting state because the empty string \(\varepsilon\) contains zero 1s. Reading 0 does not change the parity, while reading 1 switches between the two states.

Design strategy

When designing a DFA:

1. Understand the target language. List strings that belong and strings that do not. Remember to consider \(\varepsilon\).
2. Decide what the machine must remember. Give each distinguishable situation its own state.
3. State the meaning of every state. A state should summarize the relevant property of the input prefix read so far.
4. Define every transition. A DFA must have a transition for every state-symbol pair.
5. Trace examples. Test both accepting and rejecting inputs, including boundary cases.

More DFA design exercises

For strings over \(\{0,1\}\), construct a DFA for each language:

1. strings containing exactly two 1s;
2. strings beginning with 01;
3. strings ending with 01;
4. strings beginning and ending with the same symbol;
5. strings containing the substring 01;
6. strings not containing the substring 00.

For each machine, describe what every state means before drawing its transitions.

Then ask: because a language is a set, how could we modify a DFA for \(L\) to obtain one for its complement \(\overline{L}\)?

Regular languages

A language is regular if some DFA recognizes it.

This is a definition, not yet a characterization of what regular languages “look like.” Examples include:

• strings beginning with 01;
• strings ending with 01;
• strings containing 01;
• all strings of length two; and
• the finite language \(\{0,11\}\).

Finite and infinite languages

Every finite language is regular. Given finitely many strings, we can construct a finite collection of state paths that accepts exactly those strings.

A DFA can also recognize an infinite language. Cycles allow the same finite collection of states to process strings of arbitrarily large length. The number of states is finite; the language need not be.

Formal definition of a DFA

A deterministic finite automaton is a five-tuple

\[ A=(Q,\Sigma,\delta,q_0,F), \]

where:

• \(Q\) is a finite set of states;
• \(\Sigma\) is a finite input alphabet;
• \(\delta:Q\times\Sigma\rightarrow Q\) is the transition function;
• \(q_0\in Q\) is the start state; and
• \(F\subseteq Q\) is the set of accepting states.

Defining a DFA requires specifying all five components. A state diagram communicates them compactly:

• circles represent states;
• the unattached incoming arrow identifies \(q_0\);
• double circles identify the states in \(F\); and
• labeled arrows represent values of \(\delta\).

Extending the transition function to strings

The transition function \(\delta\) consumes one symbol. To describe an entire computation, define the extended transition function

\[ \delta^*:Q\times\Sigma^*\rightarrow Q. \]

It returns the state reached after starting in state \(q\) and reading an entire string \(w\).

Because strings are recursively defined, \(\delta^*\) is also defined recursively.

Base case

Reading the empty string does not change the state:

\[ \delta^*(q,\varepsilon)=q. \]

Recursive case

Every nonempty string can be written as \(wa\), where \(w\in\Sigma^*\) and \(a\in\Sigma\). First process \(w\), then process its final symbol \(a\):

\[ \delta^*(q,wa)=\delta\bigl(\delta^*(q,w),a\bigr). \]

The language recognized by \(A\) is therefore

\[ L(A)=\{w\in\Sigma^*: \delta^*(q_0,w)\in F\}. \]

Equivalently,

\[ w\in L(A) \iff \delta^*(q_0,w)\in F. \]

Closure properties of regular languages

Languages are sets of strings, so familiar set operations can be applied to them. If applying an operation to regular languages always produces another regular language, the regular languages are closed under that operation.

Important operations include:

• union: \(A\cup B\);
• intersection: \(A\cap B\);
• complement: \(\overline{A}\);
• concatenation: \(AB\); and
• Kleene star: \(A^*\).

The Kleene star contains every string formed by concatenating zero or more strings from \(A\). For example, if

\[ A=\{0,11\}, \]

then

\[ A^*=\{\varepsilon,0,11,00,011,110,1111,\ldots\}. \]

Closure under complement

Theorem. The class of regular languages is closed under complement.

Proof by construction. Suppose \(L\) is regular. Then a DFA

\[ M=(Q,\Sigma,\delta,q_0,F) \]

recognizes \(L\). Construct

\[ \overline{M}=(Q,\Sigma,\delta,q_0,Q\setminus F). \]

The new DFA has the same states and transitions but reverses the accepting status of every state. If \(M\) rejects a string, \(\overline{M}\) accepts it, and vice versa. Thus

\[ L(\overline{M})=\overline{L}, \]

so \(\overline{L}\) is regular. \(\square\)

The construction assumes that the DFA’s transition function is total, as required by the formal definition.

Closure under union

Theorem. The class of regular languages is closed under union.

Suppose DFAs

\[ M_1=(Q_1,\Sigma,\delta_1,q_1,F_1) \quad\text{and}\quad M_2=(Q_2,\Sigma,\delta_2,q_2,F_2) \]

recognize \(A_1\) and \(A_2\). Construct a product machine whose states are pairs:

\[ M=(Q_1\times Q_2,\Sigma,\delta,(q_1,q_2),F). \]

The machine simulates both original DFAs simultaneously:

\[ \delta((r_1,r_2),a) = (\delta_1(r_1,a),\delta_2(r_2,a)). \]

It should accept when either component machine accepts, so

\[ F=(F_1\times Q_2)\cup(Q_1\times F_2). \]

Induction on \(|x|\) establishes that

\[ \delta^*((r_1,r_2),x) = (\delta_1^*(r_1,x),\delta_2^*(r_2,x)). \]

Therefore, \(M\) accepts exactly when \(M_1\) accepts or \(M_2\) accepts, and

\[ L(M)=A_1\cup A_2. \]

Why concatenation is trickier

To recognize \(A_1A_2\), a machine must accept an input \(w\) when it can be split as

\[ w=xy, \]

where \(x\in A_1\) and \(y\in A_2\).

The difficulty is that the correct split point may not be known while the input is being read. A straightforward product of two DFAs cannot simply decide when the first machine should stop and the second should begin.

This problem motivates a more flexible model—nondeterministic finite automata—which will make closure under concatenation much easier to demonstrate.

Check your understanding

1. Why does a DFA have a fixed amount of memory even when its input may be arbitrarily long?
2. What property of the input prefix does each state represent in the even-number-of-1s machine?
3. Why does swapping accepting and rejecting states produce the complement language?
4. Why does the union construction require ordered pairs of states?
5. What makes concatenation harder than union for deterministic machines?