Chapter 3 - Finite Automata

Finite Automata (FAs) are the simplest model of computation we will study. They are essentially programs that solve certain decision problems without using any variables or complex memory. They process input in a single pass, from left to right, and the result is known immediately after reading the last symbol.

3.1 Aims

Our goal here is not to provide a comprehensive course on Automata Theory. Instead, we use FAs as a didactic tool, a laboratory for introducing and understanding fundamental concepts of computation in a simple, visual way. We will explore:

• Modeling Computation: How to formally describe a computation.
• Core Concepts: We will define and build intuition for key ideas like Configuration, Computation Step, Simulation, Determinism, and Nondeterminism.
• Proofs of Limitation: We will learn how to prove that a specific task is unsolvable by a given class of algorithms.

Grasping these concepts with FAs will make it much easier to understand them later in the more general and powerful context of Turing machines.

3.2 Representations of Finite Automata

To define a model of computation, we must answer a few basic questions:

1. What elementary operations are available?
2. How much memory is available, and how is it used?
3. How is input provided and output determined?

For FAs, the answer is stark: there is no memory besides the program itself and a pointer to the current instruction. This means no variables. The only changing piece of information is the program counter, which we will come to know as the automaton’s state.

A Program-like Representation

Let’s imagine an FA as a simple program. If the input alphabet is $\Sigma =\{a_1,\dots ,a_k\}$, the only allowed operation is a multi-way branch based on the next input symbol. Each line of the program corresponds to a state.

Consider a program A over ${\Sigma }_{bool}=\{0,1\}$ with four lines (states 0, 1, 2, 3). The program starts at line 0. A set of lines $F$ are designated as “accepting” lines. If the program finishes on a line in $F$, the input is accepted.

Example Program A:

• States: $\{0,1,2,3\}$
• Accepting States: $F=\{0,3\}$
• Program Logic:

  0: if input = 1 then goto 1 else goto 2
  1: if input = 1 then goto 0 else goto 3
  2: if input = 0 then goto 0 else goto 3
  3: if input = 0 then goto 1 else goto 2
  

On input 1011, the execution trace is: Start at 0 → read 1 → goto 1 → read 0 → goto 3 → read 1 → goto 2 → read 1 → goto 3. The program ends at line 3. Since $3\in F$, the word 1011 is accepted.

Graphical Representation

This program-like structure can be visualized as a state transition diagram. Each state (line number) is a node. A directed edge from state i to j labeled with symbol a means if input = a then goto j when in state i.

• The start state is marked with an incoming arrow.
• Accepting states are marked with a double circle.

The diagram for Program A is:

Formal Definition

While intuitive, diagrams and programs are not ideal for formal proofs. The standard, rigorous way to define an FA is as a mathematical object.

Definition 3.1: Deterministic Finite Automaton (DFA)

A Deterministic Finite Automaton (DFA) is a 5-tuple $M=(Q,\Sigma ,\delta ,q_0,F)$, where:

1. $Q$ is a finite set of states.
2. $\Sigma$ is a finite set called the input alphabet.
3. $\delta :Q\times \Sigma \to Q$ is the transition function.
4. $q_0\in Q$ is the start state.
5. $F\subseteq Q$ is the set of accepting states (or final states).

To describe the dynamics of a DFA, we define:

• Configuration: A pair $(q,w)\in Q\times {\Sigma }^{\ast }$, representing that the DFA is in state $q$ with the remaining input $w$ to be read.
• Step: We write $(q,aw){⊢}_M(p,w)$ if the DFA takes a single step from configuration $(q,aw)$ to $(p,w)$. This happens if and only if $\delta (q,a)=p$.
• Computation: A sequence of configurations $C_0,C_1,\dots ,C_n$ where $C_i{⊢}_M{C}_{i+1}$ for all $i$. The computation on input $x$ is the sequence starting from the start configuration $(q_0,x)$ and ending in an end configuration $(q_n,\lambda )$.
• Acceptance: A DFA $M$ accepts a word $x$ if the computation on $x$ ends in a configuration $(q,\lambda )$ where $q\in F$.
• Language of a DFA: The language accepted by $M$, denoted $L(M)$, is the set of all words that $M$ accepts.
• Regular Languages: The class of all languages accepted by some DFA is called the class of regular languages, denoted ${\mathcal{L}}_{EA}$.

For our example automaton $M$, the computation on 1011 is: $(q_0,1011){⊢}_M(q_1,011){⊢}_M(q_3,11){⊢}_M(q_2,1){⊢}_M(q_3,\lambda )$. Since $q_3\in F$, the word is accepted.

The Meaning of States

The key to designing and understanding DFAs is to realize that each state represents a property of the prefix of the input read so far. The automaton has finite memory, embodied by its states. It partitions the infinite set of all possible strings ${\Sigma }^{\ast }$ into a finite number of equivalence classes, where all strings in a class drive the automaton to the same state.

For our example automaton, the states represent the parity of 0s and 1s seen so far:

• $q_0$: even0s, even1s
• $q_1$: even0s, odd1s
• $q_2$: odd0s, even1s
• $q_3$: odd0s, odd1s

The accepted language is $L(M)=\{w\in \{0,1{\}}^{\ast }\mid |w{|}_0\text{ is even and }|w{|}_1\text{ is even, OR }|w{|}_0\text{ is odd and }|w{|}_1\text{ is odd}\}$. This is equivalent to $\{w\in \{0,1{\}}^{\ast }\mid |w{|}_0+|w{|}_1\text{ is even}\}$, i.e., all words of even length.

3.3 Simulations

A powerful technique in automata theory is to simulate multiple automata at once. This allows us to prove that the class of regular languages is closed under certain operations (union, intersection, complement).

Lemma 3.2: Closure Properties

If $L_1$ and $L_2$ are regular languages, then so are $L_1\cup L_2$, $L_1\cap L_2$, and ${\Sigma }^{\ast }\setminus L_1$.

Proof Idea (Product Construction)

Let $M_1=(Q_1,\Sigma ,{\delta }_1,q_{01},F_1)$ and $M_2=(Q_2,\Sigma ,{\delta }_2,q_{02},F_2)$ be DFAs for $L_1$ and $L_2$. We can construct a new DFA $M$ that runs $M_1$ and $M_2$ in parallel.

• The states of $M$ are pairs $(q,p)$ where $q\in Q_1$ and $p\in Q_2$.
• The start state of $M$ is $(q_{01},q_{02})$.
• The transition function is $\delta ((q,p),a)=({\delta }_1(q,a),{\delta }_2(p,a))$.

The only difference for the various operations is the choice of accepting states $F$:

• For Intersection ($L_1\cap L_2$): $F=F_1\times F_2$. We accept if both $M_1$ and $M_2$ are in an accepting state.
• For Union ($L_1\cup L_2$): $F=(F_1\times Q_2)\cup (Q_1\times F_2)$. We accept if at least one of $M_1$ or $M_2$ is in an accepting state.
• For Complement (${\Sigma }^{\ast }\setminus L_1$): We just flip the accepting and non-accepting states of $M_1$. $F=Q_1\setminus F_1$.

3.4 Proofs of Non-existence

How can we prove that a language is not regular? We must show that no DFA can accept it. The key is to exploit the DFA’s main weakness: its finite memory.

A DFA can only remember a finite amount of information about the input it has seen, because this information must be encoded in its current state, and there are only a finite number of states.

This leads to a crucial insight (the Pigeonhole Principle): if we feed a DFA an infinite number of different prefixes, it must eventually revisit a state.

Lemma 3.4: The Pumping Lemma for Regular Languages

For every regular language $L$, there exists a constant $n_L$ (the pumping length) such that for any word $z\in L$ with $|z|\ge n_L$, $z$ can be decomposed into three parts, $z=uvw$, satisfying:

1. $|uv|\le n_L$
2. $|v|\ge 1$
3. For all $i\ge 0$, the word $u{v}^{i}w$ is also in $L$.

Intuition: Any sufficiently long word $z$ must cause the DFA to visit some state twice while reading the first $n_L$ symbols. The part of the string between these two visits is $v$. Since we can traverse this loop ($v$) any number of times (including zero) and still end up in the same state, the resulting string must also be accepted.

How to use it: To prove a language $L$ is not regular, we use a proof by contradiction.

1. Assume $L$ is regular. The Pumping Lemma gives us a pumping length $n_L$.
2. Choose a clever word $z\in L$ such that $|z|\ge n_L$.
3. Show that for any possible decomposition $z=uvw$ that satisfies conditions (1) and (2), there is some $i$ for which $u{v}^{i}w\notin L$.
4. This contradicts condition (3) of the lemma, so our initial assumption must be false. $L$ is not regular.

Example: Prove $L=\{a^n{b}^n{c}^n\mid n\in \mathbb{N}\}$ is not regular.

1. Assume $L$ is regular with pumping length $n_L$.
2. Choose $z=a^{n_L}{b}^{n_L}{c}^{n_L}$. Clearly, $z\in L$ and $|z|\ge n_L$.
3. By the lemma, $z=uvw$ with $|uv|\le n_L$ and $|v|\ge 1$. Because of the length constraint, $v$ must consist entirely of $a$‘s.
4. Let’s “pump” with $i=2$. The new word is $u{v}^{2}w=a^{n_L+|v|}{b}^{n_L}{c}^{n_L}$.
5. Since $|v|\ge 1$, this new word has more $a$‘s than $b$‘s or $c$‘s, so it is not in $L$. This is a contradiction.
6. Therefore, $L$ is not regular.

3.5 Nondeterminism

What if we relax the rules of our automata? A Nondeterministic Finite Automaton (NFA) can have multiple possible moves from a given state on a given input symbol.

Definition 3.3: Nondeterministic Finite Automaton (NFA)

An NFA is a 5-tuple $M=(Q,\Sigma ,\delta ,q_0,F)$, where everything is the same as a DFA except the transition function:

• $\delta :Q\times (\Sigma \cup \{\lambda \})\to \mathcal{P}(Q)$

Here, $\mathcal{P}(Q)$ is the power set of $Q$. The function maps a state and an input symbol (or $\lambda$) to a set of possible next states.

How an NFA computes

An NFA accepts an input word $w$ if there exists at least one path of transitions from the start state to an accepting state that consumes the word $w$. The computation can be seen as a tree of possibilities. If any branch of the tree leads to an accepting state, the word is accepted.

The Power of Nondeterminism

It might seem that NFAs are more powerful than DFAs. Surprisingly, they are not.

Satz 3.2: Equivalence of NFAs and DFAs

For every NFA, there exists an equivalent DFA (that accepts the same language).

Proof Idea (Subset Construction)

We can construct a DFA that simulates the NFA. The key idea is that the state of the DFA will correspond to the set of all possible states the NFA could be in at that moment.

• States of DFA: The power set of the NFA’s states, $\mathcal{P}(Q)$.
• Start State of DFA: The set containing the NFA’s start state, $\{q_0\}$ (and all states reachable from it via $\lambda$-transitions).
• Transition of DFA: If the NFA is in a set of states $P$ and reads symbol $a$, the DFA transitions to the state corresponding to the set of all states reachable from any state in $P$ by reading $a$.
• Accepting States of DFA: Any state (which is a set of NFA states) that contains at least one of the NFA’s original accepting states.

The Cost of Determinism

While NFAs and DFAs are equivalent in power, converting an NFA with $n$ states to a DFA can, in the worst case, result in a DFA with $2^n$ states. This exponential blow-up is a fundamental theme in complexity theory. Nondeterminism can sometimes offer a much more concise way to describe a language, even if it doesn’t increase the ultimate computational power.

3.6 Summary

• Finite Automata are a simple model of computation with finite memory, represented by their states.
• They are used to recognize regular languages.
• We can prove a language is not regular using the Pumping Lemma, which exploits the finite memory limitation.
• Nondeterministic Finite Automata (NFAs) allow for multiple computation paths.
• NFAs are computationally equivalent to DFAs, but converting an NFA to a DFA can lead to an exponential increase in the number of states. This highlights a fundamental trade-off between conciseness and determinism.