Reading Notes on Introduction to Complexity - Chapter One

Finite State Automata (DFA)

We aim to develop a mathematical model of computers based on the following observations:

1. A computer has internal states.
2. It processes inputs from a finite alphabet.
3. Its state transitions are determined by the current state and input.

When the number of internal states is finite, the computer can be modeled as a finite-state automaton.

Definition. A finite state automaton is a five-tuple $\langle Q, \Sigma , \delta, S, F \rangle$, where

• $Q$ is a finite set called the states,
• $\Sigma$ is a finite set called the alphabet,
• $\delta : Q \times \Sigma \to Q$ is a transition function,
• $S \in Q$ is the start state,
• $F \subseteq Q$ is the set of accpet states.

Computation. Let $M = \langle Q, \Sigma , \delta, S, F \rangle$ be a finite automaton and let $w = w_1 w_2 \ldots w_n$ be a string where each $w_i \in \Sigma$. Then $M$ accepts $w$ if a sequence of states $r_0, r_1, \ldots, r_n \in Q$ exists with three conditions:

1. $r_0 = S$,
2. $\delta(r_i, w_{i + 1}) = r_{i + 1}$, $\forall \, i \in \{ 0, \ldots, n - 1 \}$,
3. $r_n \in F$.

Under these definitions, a finite state automaton is a computer designed for a specific task. The "algorithm" for performing this task is hard-wired into the computer, encoded in its internal states and transition function.

What can be computed by the model?

A fundamental question is: what can this mathematical model compute? We use set operations to explore the computational capabilities of this model.

Language. If $A$ is the set of all strings that machine $M$ accepts, we say that $A$ is the language of machine $M$ and write $L(M) = A$. We say that $M$ recognizes $A$ or that $M$ accepts $A$.

Regular Language. A regular language is the language that can be recognized by some finite state automaton.

Set Operations. Let $A$ and $B$ be languages. We define the regular operations union, concatenation, and star as follows:

• Union: $A \cup B = \{ x \mid x \in A \text{ or } x \in B \}$.
• Concatenation: $A \circ B = \{ x y \mid x \in A \text{ and } y \in B \}$.
• Star: $A^∗ = \{ x_1 x_2 \ldots x_k \mid k \ge 0 \text{ and each } x_i \in A \}$.

A collection of strings is called a regular language if it can be "computed" or "recognized" by an automaton.

The following theorem states that if two collections of strings are regular languages, then there exist automata that can compute their union, intersection, and concatenation. Moreover, if a collection of strings is a regular language, there exists an automaton that can compute its Kleene star.

Theorem. The class of regular language is closed under union, intersection, concatenation and star operations.

The theorem for union and intersection operations can be easily proven based on DFAs. For concatenation and star operations, the proof is simpler under an equivalent model.

Nondeterministic Finite State Automata(NFA)

Definition. A nondeterministic finite state automaton is a five-tuple $\langle Q, \Sigma , \delta, S, F \rangle$, where

• $Q$ is a finite set called the states,
• $\Sigma$ is a finite set called the alphabet,
• $\delta : Q \times \Sigma_{\epsilon} \to P(Q)$ is a transition function, where $P(Q)$ is the power set of $Q$,
• $S \in Q$ is the start state,
• $F \subseteq Q$ is the set of accpet states.

Computation. Let $M = \langle Q, \Sigma , \delta, S, F \rangle$ be a finite automaton and let $w = w_1 w_2 \ldots w_n$ be a string where each $w_i \in \Sigma_\epsilon$. Then $M$ accepts $w$ if a sequence of states $r_0, r_1, \ldots, r_n \in Q$ exists with three conditions:

1. $r_0 = S$,
2. $r_{i + 1} \in \delta(r_i, w_{i + 1})$, $\forall \, i \in \{ 0, \ldots, n - 1 \}$,
3. $r_n \in F$.

Theorem. Every NFA has an equivalent DFA.

What can't be computed by the model?

To understand the power of finite automata, it is essential to also recognize their limitations. The pumping lemma provides a tool for proving that a language cannot be recognized by any finite automaton.

Theorem (Pumping Lemma). For every regular language $L$, there is a number $p$ where, for every $\omega \in L$ of length at least $p$, $\omega$ can be devided into three pieces $\omega = xyz$, such that

• $xy^iz \in L$, for every $i \ge 0$,
• $|xy| \le p$, and
• $|y| > 0$. ​ ​ ​ ​

Regular Expression

Regular expression is a popular application of NFA.

Definition. Say that $R$ is a regular expression of an alphabet $\Sigma$ if $R$ is

1. $\{ a \}$ for some $a \in \Sigma$,
2. $\{ \epsilon \}$,
3. $\varnothing$,
4. $(R_1 \cup R_2)$, where $R_1, R_2$ are regular expressions,
5. $(R_1 \circ R_2)$, where $R_1, R_2$ are regular expressions,
6. $(R_1^*)$, where $R_1$ is a regular expressions.

When we want to distinguish between a regular expression $R$ and the language that it describes, we write $L(R)$ to be the language of $R$.

Theorem. Every regular language has a regular expression that describes it.

Hint: Proving that a DFA can be converted into a regular expression is via a model called generalized nondeterministic finite automaton, GNFA, which is simply nondeterministic finite automaton wherein the transition arrows may have any regular expressions as labels, instead of only members of the alphabet or $\epsilon$. We focus on a special form, where there is one arrow goes from every state to every other state and also from each state to itself, except that

• The start state has no arrows coming in from any other state.

• There is only a single accept state which is not the same as the start state, and it has no arrows going to any other state.

The formal definitions are given below.

Definition. A generalized nondeterministic finite state automaton is a five-tuple $\langle Q, \Sigma , \delta, S, F \rangle$, where

• $Q$ is a finite set called the states,
• $\Sigma$ is a finite set called the alphabet,
• $S \in Q$ is the start state,
• $A \in Q$ is the set of accpet states,
• $\delta : (Q - F) \times (Q - A) \to \mathcal{R}$ is a transition function, where $\mathcal{R}$ is the collection of all regular expressions over $\Sigma$.

Computation. Let $M = \langle Q, \Sigma , \delta, S, F \rangle$ be a GNFA and let $w = w_1 w_2 \ldots w_m$ be a string where each $w_i \in \Sigma_\epsilon$. Then $M$ accepts $w$ if it can be rewritten as $w = s_1 s_2 \ldots, s_n$, where each $s_i \in \Sigma^*$, such that there exists a sequence of states $r_0, r_1, \ldots, r_n \in Q$ with three conditions:

1. $r_0 = S$,
2. each $s_i \in L(R_i)$, where $R_i = \delta(r_i, r_{i + 1})$ is the regular expression on the arrow from $r_i$ to $r_{i + 1}$,
3. $r_n = A$.

Every DFA can be transformed into a GNFA. Then, we iteratively remove states from the GNFA, updating the regular expressions on the arrows at each step while preserving the accepted language. This process continues until only two states remain, and the regular expression on the final arrow represents the desired result.

Reference

[1] M. Sipser, Introduction to the theory of computation, Third edition, Cengage Learning, 2013.