Browser Advisory: The HTML version of this textbook requires a browser that supports the display of MathML. A good choice as of April 2022 is a recent version of Firefox from Mozilla.

1 Introduction to the Theory of Computation

Why study theory?

1. To understand the concepts and principles underlying the fundamental nature of computing
   • by constructing abstract models of computers and computation
2. To learn to apply the theory to practical areas of computing
   • in programming languages, compilers, operating systems, networks, etc.
3. To have fun!
   • from tackling challenging “puzzles” and problems

In this course, we study the following models:

1. automaton (automata)
   • an abstraction of the computing mechanism
   • takes input, uses temporary storage, makes decisions, and produces output
2. formal language
   • an abstraction of a programming language
   • syntax = symbols + grammar rules
3. algorithm
   • an abstraction of a mechanical computation
   • what are the limits of what we can and cannot compute?

1.1 Mathematical Preliminaries and Notation

The mathematical concepts used in the Linz textbook include:

• sets
• functions
• relations
• graphs
• trees
• proof techniques

1.1.1 Sets

Students in this course should be familiar with the following set concepts from previous study in mathematics:

• literal set notation such as $\{ a, b, c \}$, $\{ 2, 4, 6, \cdots \}$, and $\{ i : i > 10, i < 100 \}$
• element (member) $e \in S$
• not an element $e \notin S$
• union $S \cup T$ (in one or both)
• intersection $S \cap T$ (in both)
• difference $S - T$ (in $S$ but not $T$)
• universal set $U$ (all possible elements)
• complementation $\bar{S}$ (in $U$ but not $S$)
• empty set $\emptyset$ (no elements)
• subset $S \subseteq T$ (all from $S$ in $T$)
• proper subset $S \subset T$ (subset but not equal)
• disjoint sets $S \cap T = \emptyset$ (no common elements)
• finite and infinite sets
• cardinality $|S|$ (number elements of finite set)
• powerset $2^{S}$ (set of all subsets of a set)
• Cartesian product $S \times T$ (set of all ordered pairs)
• partition of a set (breaking a set into mutually disjoint, nonempty subsets whose intersection is the entire set)

Laws for operations on the empty set:

• $S \cup \emptyset = S$ (identity element for union)
• $S \cap \emptyset = \emptyset$ (zero element for intersection)
• $\bar{\emptyset} = U$
• $\bar{\bar{S}} = S$ (complementation is inverse for itself)

DeMorgan’s Laws:

• $\bar{S_{1} \cup S_{2}} = \bar{S_{1}} \cap \bar{S_{2}}$
• $\bar{S_{1} \cap S_{2}} = \bar{S_{1}} \cup \bar{S_{2}}$

1.1.2 Functions

Function $f: D \rightarrow R$ means that

• $f \subseteq D \times R$, where
  • domain $\subseteq D$
  • range $\subseteq R$
  • $f$ maps an element of its domain to a unique element of its range

Function $f$ is a

• total function if domain = D
• partial function otherwise

1.1.3 Relations

A relation on $X$ and $Y$ is any subset of $X \times Y$.

An equivalence relation $\equiv$ is a generalization of equality. It is:

1. reflexive: $x \equiv x \forall x$
2. symmetric: if $x \equiv y$ then $y \equiv x$
3. transitive: if $x \equiv y$ and $y \equiv z$ then $x \equiv z$

1.1.4 Graphs

A $graph$ $\langle V, E \rangle$ is a mathematical entity where

• $V = \{ v_{1}, v_{2}, \ldots, v_{n} \}$ is a finite set of vertices (or nodes)

• $E = \{ e_{1}, e_{2}, \ldots, e_{m} \}$ is a finite set of edges (or arcs)

• each edge $e_{i} = ( v_{j}, v_{k} )$ is a pair of vertices

A directed graph (or digraph) is a graph in which each edge $e_{i} = ( v_{j}, v_{k} )$ has a direction from vertex $v_{j}$ to vertex $v_{k}$.

Edge $e_{i} = ( v_{j}, v_{k} )$ on a digraph is an outgoing edge from vertex $v_{j}$ and an incoming edge to vertex $v_{k}$.

If there are no directions associated with the edges, then the graph is undirected.

Graphs may be labeled by assigning names or other information to vertices or edges.

We can visualize a graph with a diagram in which the vertices are shown as circles and edges as lines connecting a pair of vertices. For directed graphs, the direction of an edge is shown by an arrow.

Linz Figure 1.1 shows a digraph $\langle V, E \rangle$ where $V = \{ v_{1}, v_{2}, v_{3} \}$ and edges $E = \{ (v_{1} v_{3}),(v_{3},v_{1}),(v_{3},v_{2}),(v_{3},v_{3}) \}$.

A sequence of edges $(v_{i},v{j}), (v_{j},v{k}), \ldots, (v_{m},v_{n})$ is a walk from $v_{j}$ to $v_{n}$. The length of the walk is the total number of edges traversed.

A path is a walk with no edge repeated. A path is simple if no vertex is repeated.

A walk from some vertex $v_{i}$ to itself is a cycle with base $v_{i}$. If no vertex other than the base is repeated, then the cycle is simple.

In Linz Figure 1.1:

• $(v_{1},v_{3}), (v_{3},v_{2})$ is a simple path from $v_{1}$ to $v_{2}$
• $(v_{1},v_{3}), (v_{3},v_{3}), (v_{3},v_{1})$ is a cycle but not simple

If the edges of a graph are labelled, then the label of a walk (or path) is the sequence of edges encountered on a traversal.

1.1.5 Trees

A tree is a directed graph with no cycles and a distinct root vertex such that there is exactly one path from the root to every other vertex.

The root of a tree has no incoming edges.

A vertex of a tree without any outgoing edges is a leaf of the tree.

If there is an edge from $v_{i}$ to $v_{j}$ in a tree, then:

• $v_{i}$ is the parent of $v_{j}$

• $v_{j}$ is a child of $v_{i}$

The level associated with each vertex is the number of edges in the path from the root to the vertex.

The height of a tree is the largest level number of any vertex.

If we associated an ordering with the vertices at each level, then the tree is an ordered tree.

The above terminology is illustrated in Linz Figure 1.2.

1.1.6 Proof Techniques

Students in this course should be familiar with the following proof techniques from previous study in mathematics:

• Deduction
  • Prove $P$ from axioms and previously proved theorems by a sequence of steps guaranteed by the rules of logic.
• Contradiction
  • Assume $P$ is false, prove a sequence of deductive steps that this leads to something we know is false. Hence, this is a contradiction. Thus $P$ must be true.
• Induction
  • Basis step: Prove $P_{0}$ (i.e, for all primitive cases)
  • Inductive step: Assume $P_{n}, n \geq 0$, prove $P_{n+1}$.

We will see an example of an inductive proof in the next section.

1.2 Three Basic Concepts

Three fundamental ideas are the major themes of this course:

1. languages
2. grammars
3. automata

1.2.1 Languages

Our concept of language is an abstraction of the concept of a natural language.

1.2.1.1 Language Concepts

Linz Definition (Alphabet): An alphabet, denoted by $\Sigma$, is a finite, nonempty set of symbols.

By convention, we use lowercase letters near the beginning of the English alphabet $a, b, c, \ \cdots$ to represent elements of $\Sigma$.

For example, if $\Sigma = \{ a, b \}$, then the alphabet has two unique symbols denoted by $a$ and $b$.

Linz Definition (String): A string is a finite sequence of symbols from the alphabet.

By convention, we use lowercase letters near the end of the English alphabet $\cdots\ u, v, w, x, y, z$ to represent strings. We write strings left to right. That is, symbols appearing to the left are before those appearing to the right.

For example, $w = baabaa$ is a string from the above alphabet. The string begins with a $b$ and ends with an $a$.

Linz Definition (Concatenation): The concatenation of strings $u$ and $v$ means appending the symbols of $v$ to the right end (i.e., after) the symbols of $u$, denoted by uv.

If $u = a_{1} a_{2} a_{3}$ and $v = b_{1} b_{2} b_{3}$, then $uv = a_{1} a_{2} a_{3} b_{1} b_{2} b_{3}$.

Definition (Associativity): Operation $\oplus$ is associative on set $S$ if, for all $x$, $y$, and $z$ in $S$, $(x \oplus y) \oplus z = x \oplus (y \oplus z)$. We often write associative expressions without explicit parentheses, e.g., $x \oplus y \oplus z$.

String concatenation is associative, that is, $(u v) w = u (v w)$.

Thus we normally just write $uvw$ without parentheses.

Definition (Commutativity): Operation $\oplus$ is commutative on set $S$ if, for all $x$ and $y$ in $S$, $x \oplus y = y \oplus x$.

String concatenation is not commutative. That is, $uv \neq vu$.

Linz Definition (Reverse): The reverse of a string $w$, denoted by $w^{R}$, is the string with same symbols, but with the order reversed.

If $w = a_{1}a_{2}a_{3}$, then $w^{R} = a_{3}a_{2}a_{1}$.

Linz Definition (Length): The length of a string w, denoted by $|w|$, is the number of symbols in string $w$.

Linz Definition (Empty String): The empty string, denoted by $\lambda$, is the string with no symbols, that is, $|\lambda| = 0$.

Definition (Identity Element): An operation $\oplus$ has an identity element $e$ on set $S$ if, for all $x \in S$, $x \oplus e = x = e \oplus x$.

The empty string $\lambda$ is the identity element for concatenation. That is, $\lambda w = w \lambda = w$.

1.2.1.2 Formal Interlude: Inductive Definitions and Induction

We can define the length of a string with the following inductive definition:

1. $|\lambda| = 0$ (base case)
2. $|wa| = |w| + 1$ (inductive case)

Note: This inductive defintion and proof differs from the textbook. Here we begin with the empty string.

Using the fact that $\lambda$ is the identity element and the above definition, we see that

$|a| = |\lambda a| = |\lambda| + 1 = 0 + 1 = 1$.

Prove $|uv|\ =\ |u| + |v|$.

Noting the definition of length above, we choose to do an induction over string v (or, if you prefer, over the length of $v$, basing induction at 0).

Base case $v\ =\ \lambda$ (that is, length is 0)

Inductive case $v=wa$ (that is, length is greater than 0)
Induction hypothesis: $|uw| = |u| + |w|$

Thus we have proved $|uv| = |u| + |v|$. QED.

1.2.1.3 More Language Concepts

Linz Definition (Substring): A substring of a string $w$ is any string of consecutive symbols in $w$.

If $w = a_{1}a_{2}a_{3}$, then the substrings are $\lambda, a_{1}, a_{1}a_{2}, a_{1}a_{2}a_{3}, a_{2}, a_{2}a_{3}, a_{3}$.

Linz Definition (Prefix, Suffix): If $w = vu$, then $v$ is a prefix of $w$ and $u$ is a suffix.

If $w = a_{1}a_{2}a_{3}$, the prefixes are $\lambda, a_{1}, a_{1}a_{2}, a_{1}a_{2}a_{3}$.

Linz Definition ($w^{n}$): $w^{n}$, for any string w and $n \geq 0$ denotes $n$ repetitions of string (or symbol) $w$. We further define $w^{0} = \lambda$.

Linz Definition (Star-Closure): $\Sigma^{*}$, for alphabet $\Sigma$, is the set of all strings obtained by concatenating zero or more symbols from the alphabet.

Note: An alphabet must be a finite set.

Linz Definition (Positive Closure): $\Sigma^{+} = \Sigma^{*} - \lambda$

Although $\Sigma$ is finite, $\Sigma^{*}$ and $\Sigma^{+}$ are infinite.

For a string $w$, we also write $w^{*}$ and $w^{+}$ to denote zero or more repetitions of the string and one or more repetitions of the string, respectively.

Linz Definition (Language): A language, for some alphabet $\Sigma$, is a subset of $\Sigma^{*}$.

Linz Definition (Sentence): A sentence of some language $L$ is any string from $L$ (i.e., from $\Sigma^{*}$).

1.2.1.4 Linz Example 1.9: Example Languages

Let $\Sigma = \{ a, b \}$.

• $\Sigma^{*} = \{ \lambda, a, b, aa, ab, ba, bb, aaa, aab, \ \cdots\ \}$.

• $\{a, aa, aab \}$ is a language on $\Sigma$.

Since the language has a finite number of sentences, it is a finite language.

• $L = \{ a^{n} b^{n} : n \geq 0 \}$ is also a language on $\Sigma$.

Sentences $aabb$ and $aaaabbbb$ are in $L$, but $aaabb$ is not.

As with most interesting languages, $L$ is an infinite language.

1.2.1.5 Operations on Languages

Languages are represented as sets. Operations on languages can be defined in terms of set operations.

Linz Definition (Union, Intersection, and Difference): Language union, intersection, and difference are defined directly as the corresponding operations on sets.

Linz Definition (Concatenation): Language complementation with respect to $\Sigma^{*}$ is defined such that $\bar{L} = \Sigma^{*} - L$.

Linz Definition (Reverse): Language reverse is defined such that $L^{R} = \{ w^{R} : w \in L \}$. (That is, reverse all strings.)

Linz Definition (Concatenation): Language concatenation is defined such that $L_{1} L_{2} = \{ x y : x \in L_{1}, y \in L_{2} \}$.

Linz Definition ($L^{n}$): $L^{n}$ means $L$ concatenated with itself $n$ times.

$L^{0} = \{ \lambda \}$ and $L^{n+1} = L^{n}L$

Definition (Star-Closure): Star-closure (Kleene star) is defined such that $L^{*} = L^{0} \cup L^{1} \cup L^{2} \cup \cdots$.

Definition (Positive Closure): Positive closure is defined such that $L^{+} = L^{1} \cup L^{2} \cup \cdots$.

1.2.1.6 Language Operation Examples

Let $L = \{ a^{n} b^{n} : n \geq 0 \}$.

• $L^{2} = \{ a^{n} b^{n} a^{m} b^{m} : n \geq 0, m \geq 0 \}$ (where n and m are unrelated).

• $abaaabbb \in L^{2}$.

• $L^{R} = \{b^{n} a^{n} : n \geq 0 \}$

How would we express in $\bar{L}$ and $L^{*}$?

Although set notation is useful, it is not a convenient notation for expressing complicated languages.

1.2.2 Grammars

1.2.2.1 Grammar Concepts

Linz Definition 1.1 (Grammar): A grammar $G$ is a quadruple $G = (V, T, S, P)$ where

$V$ is a finite set of objects called variables.
$T$ is a finite set of objects called terminal symbols.
$S \in V$ is a special symbol called the start symbol.
$P$ is a finite set of productions.
$V$ and $T$ are nonempty and disjoint.

Linz Definition (Productions): Productions have form $x \rightarrow y$ where:

$x \in (V \cup T)^{+}$, i.e., $x$ is some non-null string of terminals and variables
$y \in (V \cup T)^{*}$, i.e., $y$ is some, possibly null, string of terminals and variables

Consider application of productions, given $w = uxv$:

• $x \rightarrow y$ is applicable to string $w$.

• To use the production, substitute $y$ for $x$.

  Thus the new string is $z = uyv$.

  We say $w$ derives $z$, written $w \Rightarrow z$.

• Continue by applying any applicable productions in arbitrary order.

  $w_{1} \Rightarrow w_{2} \Rightarrow w_{3} \Rightarrow \cdots \Rightarrow w_{n}$.

Linz Definition (Derives): $w_{1} \overset{*}{\Rightarrow} w_{n}$ means that $w_{1}$ derives $w_{n}$ in zero or more production steps.

Linz Definition (Language Generated): Let $G = (V, T, S, P)$ be a grammar. Then $L(G) = \{ w \in T^{*} : S \overset{*}{\Rightarrow} w \}$ is the language generated by $G$.

That is, $L(G)$ is the set of all strings that can be generated from the start symbol $S$ using the productions $P$.

Linz Definition (Derivation): A derivation of some sentence $w \in L(G)$ is a sequence $S\Rightarrow w_{1} \Rightarrow w_{2} \Rightarrow w_{3} \Rightarrow \cdots \Rightarrow w_{n} \Rightarrow w$.

The strings $S, w_{1}, \cdots, w_{n}$ above are sentential forms of the derivation of sentence $w$.

1.2.2.2 Linz Example 1.11 (Grammar)

Consider $G = (\{S\},\{a,b\},S,P)$ where P is the set of productions

• $S \rightarrow aSb$
• $S \rightarrow \lambda$

Consider $S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb$. Hence, $S \overset{*}{\Rightarrow} aabb$.

$aabb$ is a sentence of the language; the other strings in the derivation are sentential forms.

Conjecture: The language formed by this grammar, $L(G)$, is $\{ a^{n} b^{n} : n \geq 0 \}$.

Usually, however, it is difficult to construct an explicit set definition for a language generated by a grammar.

Now prove the conjecture.

First, prove that all sentential forms of the language have the structure $w_{i} = a^{i}Sb^{i}$ for $i \geq 0$ by induction on i.

Basis step:

Clearly, $w_{0} = S$ is a sentential form, the start symbol.

Inductive step:

Assume $w_{m} = a^{m}Sb^{m}$ is a sentential form, show that $w_{m+1} = a^{m+1}Sb^{m+1}$.

Case 1: If we begin with the assumption and apply production $S \rightarrow aSb$, we get sentential form $w_{m+1} = a^{m+1}Sb^{m+1}$.

Case 2: If we begin with the assumption and apply production $S \rightarrow \lambda$, we get the sentence $a^{m}b^{m}$ rather than a sentential form.

Hence, all sentential forms have the form $a^{i}Sb^{i}$.

Given that $S \rightarrow \lambda$ is the only production with terminals on the right side, we must apply it to derive any sentence. As we noted in case 2 above, application of the production to any sentential form gives a sentence of the form $a^{m}b^{m}$. QED.

1.2.2.3 Linz Example 1.12: Finding a Grammar for a Language

Given $L = \{a^{n}b^{n+1} : n \geq 0 \}$.

• Recursive production $S \rightarrow aSb$ would generate sentential forms $a^{n}Sb^{n}$.

• Need production(s) to add the extra b to the final sentence.

• Suggest $S \rightarrow b$.

A slightly different grammar might introduce nonterminal A as follows:

• $S \rightarrow Ab$
• $A \rightarrow aAb$
• $A \rightarrow \lambda$

1.2.2.4 More Grammar Concepts

To show that a language $L$ is generated by a grammar $G$, we must prove:

1. For every $w \in L$, there is a derivation using $G$.

2. Every string derived from $G$ is in $L$.

Linz Definition (Equivalence): Two grammars are equivalent if they generate the same language.

For example, the two grammars given above for the language $L = \{a^{n}b^{n+1} : n \geq 0 \}$ are equivalent.

1.2.2.5 Linz Example 1.13

Let $\Sigma = \{a,b\}$ and let $n_{a}(w)$ and $n_{b}(w)$ denote the number of $a$’s and $b$’s in the string $w$.

Let grammar $G$ have productions

$S \rightarrow SS$
$S \rightarrow \lambda$
$S \rightarrow aSb$
$S \rightarrow bSa$

Let $L = \{w : n_{a}(w) = n_{b}(w) \}$.

Prove $L(G) = L$.

Informal argument follows. Actual proof would be an induction over length of $w$.

Consider cases for $w$.

1. Case $w \in L(G)$. Show $w \in L$.

   Any production adding an a also adds a b. Thus there is the same number of a’s and b’s.

2. Case $w \in L$. Show $w \in L(G)$.

   • Consider $w = a w_{1} b$ or $w = bw_{1} a$ for some $w_{1} \in L$.

     String $w$ was generated by either $S \rightarrow aSb$ or $S \rightarrow bSa$ in the first step.

     Thus $w \in L$.

   • Consider $w = aua$ (or $w = bub$) for some $u \in L$.

     Examine the symbols of w from the left – add 1 for each a, subtract 1 for each b.

     Since sum must be 0 at right, there must be a point where the sum crosses 0.

     Break at that point into form $w = w_{1}w_{2}$ where $w_{1}, w_{2} \in L$.

     First production is $S \rightarrow SS$.

     Thus $w \in L(G)$.

1.2.3 Automata

An automaton is an abstract model of a compute

As shown in Linz Figure 1.4, a computer:

1. reads input from an input file – one symbol from each cell – left to right

2. produces output

3. may use storage – unlimited number of cells (may be different alphabet)

4. has a control unit

   • finite number of states
   • state changes in defined manner
   • “next-state” or transition function – specifies state changes

A configuration is a state of the control unit, input, and storage.

A move is a transition from one state configuration to another.

Automata can be categorized based on control:

• A deterministic automaton has a unique next state from the current configuration.

• A nondeterministic automaton has several possible next states.

Automata can also be categorized based on output:

• An accepter has only yes/no output.

• A transducer has strings or symbols for output,

Various models differ in

• how the output is produced

• the nature of temporary storage

1.3 Applications

1.3.1 Linz Example 1.15: C Identifiers

The syntax rules for identifiers in the language C are as follows:

• An identifier is a sequence of letters, digits, and underscores.

• An identifier must start with a letter or underscore.

• Identifiers allow both uppercase and lowercase letters.

Formally, we can describe these rules with the grammar:

    <id>       -> <letter><rest>   | <underscr><rest>
    <rest>     -> <letter><rest>   | <digit><rest>    |
                  <underscr><rest> | <lambda>
    <letter>   -> a|b|c|...|z|A|B|C|...|Z
    <digit>    -> 0|1|2|...|9
    <underscr> -> _

Above <lambda> represents the symbol $\lambda$,-> is the $\rightarrow$ for productions, and | denotes alternative right-hand-sides of the productions.

The variables are <id>, <letter>, <digit>, <underscr>, and <rest>. The other alphanumeric symbols are literals.

Linz Figure 1.6 shows a drawing of an automaton that accepts all legal C identifiers as defined above.

We can interpret the automaton in Linz Figure 1.6 as follows:

• The machine starts in state 1.
• It reads the string left to right, one character at a time.
• If the first character is a <digit> then the machine moves to state 3. The machine stops reading with answer No (non-accepting).
• If first character is a <letter> or <underscr> then it moves to state 2. The machine continues.
• As long as the next character is a <letter>, <underscr>, or <digit>, then the machine reads the input and remains in state 2.
• The machine stops in state 2 when either there is no more input or unacceptable input.
• If no more input and in state 2, then machine stops with answer Yes (accepting). Otherwise, it stops with the answer No (non-accepting).

1.3.2 Linz Example 1.17: Binary Adder

Let $x = a_{0} a_{1} a_{0} \cdots a_{n}$ where $a_{i}$ are bits.

Then $value(x) = \sum_{i=0}^{n} a_{i} 2^{i}$.

This is the usual binary representation in reverse.

A serial adder process two such numbers x and y, bit by bit, starting at the left end. Each bit addition creates a digit for the sum and a carry bit as shown in Linz Figure 1.7.

A block diagram for the machine is shown in Linz Figure 1.8.

A transducer automaton to carry out the addition of two numbers is shown in Linz Figure 1.9.

The pair on the edges represents the two inputs. The value following the slash is the output.

2 Finite Automata

In chapter 2, we approach automata and languages more precisely and formally than in chapter 1.

A finite automaton is an automaton that has no temporary storage (and, like all automata we consider in this course, a finite number of states and input alphabet).

2.1 Deterministic Finite Accepters

2.1.1 Accepters

Linz Definition (DFA): A deterministic finite accepter, or dfa, is defined by the tuple $M = ( Q, \Sigma, \delta, q_{0}, F )$ where

• Q is a finite set of internal states

• $\Sigma$ is a finite set of symbols called the input alphabet

• $\delta : Q \times \Sigma \rightarrow Q$ is a total function called the transition function

• $q_{0} \in Q$ is the initial state.

• $F \subseteq Q$ is a set of final states.

A dfa operates as described in the following pseudocode:

currentState := $q_{0}$

position input at left end of string

while more input exists

currentInput := next_input_symbol

advance input to right

currentState := $\delta$(currentState,currentInput)

if currentState $\in F$ then ACCEPT else REJECT

2.1.2 Transition Graphs

To visualize a dfa, we use a transition graph constructed as follows:

• Vertices represent states
  • labels are state names
  • exactly one vertex for every $q_{i} \in Q$
• Directed edges represent transitions
  • label on edge is current input symbol
  • directed edge $(q, r)$ with label $a$ if and only if $\delta(q,a) = r$

2.1.3 Linz Example 2.1

The graph pictured in Linz Figure 2.1 represents the dfa $M = (\{ q_{0}, q_{1}, q_{2} \},\{ 0, 1 \},\delta, q_{0}, \{q_{1}\})$, where $\delta$ is represented by

$\delta(q_{0},0) = q_{0}$, $\delta(q_{0},1) = q_{1}$
$\delta(q_{1},0) = q_{0}$, $\delta(q_{1},1) = q_{2}$
$\delta(q_{2},0) = q_{2}$, $\delta(q_{2},1) = q_{1}$

Note that $q_{0}$ is the initial state and $q_{1}$ is the only final state in this dfa.

The dfa in Linz Figure 2.1:

• Accepts 01, 101
• Rejects 00, 100

What about 0111? 1100?

2.1.4 Extended Transition Function for a DFA

Linz Definition: The extended transition function $\delta^{*} : Q \times \Sigma^{*} \rightarrow Q$ is defined recursively:

$\delta^{*}(q,\lambda) = q$
$\delta^{*}(q,wa) = \delta(\delta^{*}(q,w),a)$

The extended transition function gives the state of the automaton after reading a string.

2.1.5 Language Accepted by a DFA

Linz Definition 2.2 (Language Accepted by DFA): The language accepted by a dfa $M = ( Q, \Sigma, \delta, q_{0}, F )$ is $L(M) = \{ w \in \Sigma^{*} : \delta^{*}(q_{0}, w) \in F \}$.

That is, $L(M)$ is the set of all strings on the input alphabet accepted by automaton M.

Note that above $\delta$ and $\delta^{*}$ are total functions (i.e., defined for all strings).

2.1.6 Linz Example 2.2

The automaton in Linz Figure 2.2 accepts all strings consisting of arbitrary numbers of $a$’s followed by a single $b$.

In set notation, the language accepted by the automaton is $L = \{ a^{n}b : n \geq 0 \}$.

Note that $q_{2}$ has two self-loop edges, each with a different label. We write this compactly with multiple labels.

A trap state is a state from which the automaton can never “escape”.

Note that $q_{2}$ is a trap state in the dfa transition graph shown in Linz Figure 2.2.

Transition graphs are quite convenient for understanding finite automata.

For other purposes–such as representing finite automata in programs–a tabular representation of transition function $\delta$ may also be convenient (as shown in Linz Fig. 2.3).

2.1.7 Linz Example 2.3

Find a deterministic finite accepter that recognizes the set of all string on $\Sigma = \{a, b\}$ starting with the prefix $ab$.

Linz Figure 2.4 shows a transition graph for a dfa for this example.

The dfa must accept $ab$ and then continue until the string ends.

This dfa has a final trap state $q_{2}$ (accepts) and a non-final trap state $q_{3}$ (rejects).

2.1.8 Linz Example 2.4

Find a dfa that accepts all strings on $\{ 0, 1 \}$, except those containing the substring $001$.

• need to “remember” whether last two inputs were $00$

• use state changes for “memory”

Linz Figure 2.5 shows a dfa for this example.

Accepts: $\lambda$, 0, 00, 01, 010000

Rejects: 001, 000001, 0010101010101

2.1.9 Regular Languages

Linz Definition 2.3 (Regular Language): A language L is called regular if and only if there exists a dfa M such that $L = L(M)$.

Thus dfas define the family of languages called regular.

2.1.10 Linz Example 2.5

Show that the language $L = \{ awa : w \in \{ a, b \}^{*}\}$ is regular.

• Construct a dfa.

• Check whether begin/end with “a”.

• Am in final state when second a input.

Linz Figure 2.6 shows a dfa for this example.

Question: How would we prove that a languages is not regular?

We will come back to this question in chapter 4.

2.1.11 Linz Example 2.6

Let $L$ be the language in the previous example (Linz Example 2.5).

Show that $L^{2}$ is regular.

$L^{2} = \{ aw_{1}aaw_{2}a: w_{1}, w_{2} \in \{a,b\}^{*} \}$.

• Construct a dfa.

• Use Example 2.5 dfa as starting point.

• Accept two consecutive strings of form $awa$.

• Note that any two consecutive $a$’s could start a second string.

Linz Figure 2.7 shows a dfa for this example.

The last example suggests the conjecture that if a language $L$ then so is $L^2$, $L^3$, etc.

We will come back to this issue in chapter 4.

2.2 Nondeterministic Finite Accepters

2.2.1 Nondeterministic Accepters

Linz Definition 2.4 (NFA): A nondeterministic finite accepter or nfa is defined by the tuple $M = ( Q, \Sigma, \delta, q_{0}, F )$ where $Q$, $\Sigma$, $q_{0}$, and $F$ are defined as for deterministic finite accepters, but

$\delta : Q \times (\Sigma \cup \{\lambda\}) \rightarrow 2^{Q}$.

Remember for dfas:

• Q is a finite set of internal states.

• $\Sigma$ is a finite set of symbols called the input alphabet.

• $q_{0} \in Q$ is the initial state.

• $F \subseteq Q$ is a set of final states.

The key differences between dfas and nfas are

1. dfa: $\delta$ yields a single state
   nfa: $\delta$ yields a set of states

2. dfa: consumes input on each move
   nfa: can move without input ($\lambda$)

3. dfa: moves for all inputs in all states
   nfa: some situations have no defined moves

An nfa accepts a string if some possible sequence of moves ends in a final state.

An nfa rejects a string if no possible sequence of moves ends in a final state.

2.2.2 Linz Example 2.7

Consider the transition graph shown in Linz Figure 2.8.

Note the nondeterminism in state $q_{0}$ with two possible transitions for input $a$.

Also state $q_{3}$ has no transition for any input.

2.2.3 Linz Example 2.8

Consider the transition graph for an nfa shown in Linz Figure 2.9.

Note the nondeterminism and the $\lambda$-transition.

Note: Here $\lambda$ means the move takes place without consuming any input symbol. This is different from accepting an empty string.

Transitions:

• for $(q_{0},0)$?

• for $(q_{1},0)$?

• for $(q_{2},0)$?

• for $(q_{2},1)$?

Accepts: $\lambda$, 10, 1010, 101010

Rejects: 0, 11

2.2.4 Extended Transition Function for an NFA

As with dfas, the transition function can be extended so its second argument is a string.

Requirement: $\delta^{*}(q_{i},w) = Q_{j}$ where $Q_{j}$ is the set of all possible states the automaton may be in, having started in state $q_{i}$ and read string $w$.

Linz Definition (Extended Transition Function): For an nfa, the extended transition function is defined so that $\delta^{*}(q_{i},w)$ contains $q_{j}$ if there is a walk in the transition graph from $q_{i}$ to $q_{j}$ labelled $w$.

2.2.5 Language Accepted by an NFA

Linz Definition 2.6 (Language Accepted by NFA): The language $L$ accepted by the nfa $M = ( Q, \Sigma, \delta, q_{0}, F )$ is defined

$L(M) = \{ w \in \Sigma^{*} : \delta^{*}(q_{0}, w) \in F \neq \emptyset \}$.

That is, $L(M)$ is the set of all strings $w$ for which there is a walk labeled $w$ from the initial vertex of the transition graph to some final vertex.

2.2.6 Linz Example 2.10 (Example 2.8 Revisited)

Let’s again examine the automaton given in Linz Figure 2.9 (Example 2.8).

This nfa, call it $M$:

• must end in $q_{0}$

• $L(M) = \{ (10)^{n} : n \geq 0 \}$

Note that $q_{2}$ is a dead configuration because $\delta^{*}(q_{0},110) = \emptyset$.

2.2.7 Why Nondeterminism

When computers are deterministic?

• an nfa can model a search or backtracking algorithm

• nfa solutions may be simpler than dfa solutions (can convert from nfa to dfa)

• nondeterminism may model externally influenced interactions (or abstract more detailed computations)

2.3 Equivalence of DFAs and NFAs

2.3.1 Meaning of Equivalence

When are two mechanisms (e.g., programs) equivalent?

• When they have exactly the same descriptions?

• When they always go through the exact same sequence of steps?

• When the same input generates the same output for both?

The last seems to be the best approach.

Linz Definition 2.7 (DFA-NFA Equivalence): Two finite accepters $M_{1}$ and $M_{2}$ are said to be equivalent if $L(M_{1}) = L(M_{2})$. That is, if they both accept the same language.

Here “same language” refers to the input and “both accept” refers to the output.

Often there are many accepters for a language.

Thus there are many equivalent dfa and nfas.

2.3.2 Linz Example 2.11

Again consider the nfa represented by the graph in Linz Fig. 2.9. Call this $M_{1}$.

As we saw, $L(M_{1}) = \{ (10)^{n} : n \geq 0 \}$.

Now consider the dfa represented by the graph in Linz Figure 2.11. Call this $M_{2}$.

$L(M_{2}) = \{ (10)^{n} : n \geq 0 \}$.

Thus, $M_{1}$ is equivalent to $M_{2}$.

2.3.3 Power of NFA versus DFA

Which is more powerful, dfa or nfa?

Clearly, any dfa $D$ can be made into a nfa $N$.

• Keep the same states.
• Define $\delta_{N}(q,a) = \{ \delta_{D}(q,a) \}$.

Can any nfa $N$ be made into a dfa $D$?

• Yes, but it is less obvious. (See theorem below.)

Thus, dfas and nfas are “equally powerful”.

Linz Theorem 2.2 (Existence of DFA Equivalent to NFA): Let $L$ be the language accepted by the nfa $M_{N} = (Q_{N}, \Sigma, \delta_{N}, q_{0}, F_{N})$. Then there exists a dfa $M_{D} = (Q_{D}, \Sigma, \delta_{D}, \{ q_{0} \}, F_{D})$ such that $L = L(M_{D})$.

A pure mathematician would be content with an existence proof.

But, as computing scientists, we want an algorithm for construction of $M_{D}$ from $M_{N}$. The proof of the theorem follows from the correctness of the following algorithm.

Key ideas:

• After reading $w$, $M_{N}$ will be in the some state from $\{ q_{i},q_{j}, \ldots\ q_{k} \}$. That is, $\delta^{*}(q_{0},w) = \{ q_{i}, q_{j}, \ldots\ q_{k} \}$.

• Label the dfa state that has accepted $w$ with the set of nfa states $\{ q_{i},q_{j}, \ldots\ q_{k} \}$. This is an interesting “trick”!

Remember from the earlier definitions in these notes and from discrete mathematics:

• $\Sigma$ is finite (and the same for the nfa and dfa).

• $Q_{N}$ is finite.

• $\delta_{D}$ is a total function. That is, every vertex of the dfa graph has $|\Sigma|$ outgoing edges.

• The maximum number of dfa states with the above labeling is $|2^{Q_{N}}| = 2^{|Q_{N}|}$. Hence, finite.

• The maximum number of dfa edges is $2^{|Q_{D}|}|\Sigma|$. Hence, finite.

Procedure nfa_to_dfa

Given a transition graph $G_{N}$ for nfa $M_{N} = (Q_{N}, \Sigma, \delta_{N}, q_{0}, F_{N})$, construct a transition graph $G_{D}$ for a dfa $M_{D} = (Q_{D}, \Sigma, \delta_{D}, q_{0}, F_{D})$. Label each vertex in $G_{D}$ with a subset of the vertices in $G_{N}$.

1. Initialize graph $G_{D}$ to have an initial vertex $\{ q_{0} \}$ where $q_{0}$ is the initial state of $G_{N}$.

2. Repeat the following steps until no more edges are missing from $G_{D}$:

   1. Take any vertex from $G_{D}$ labeled $\{ q_{i}, q_{j}, \ldots\ q_{k} \}$ that has no outgoing edge for some $a \in \Sigma$.

   2. For this vertex and input, compute $\delta^{*}_{N}(q_{i},a),\delta^{*}_{N}(q_{j},a), \ldots\ \delta^{*}_{N}(q_{k},a)$. (Each of these is a set of states from $Q_{N}$.)

   3. Let $\{ q_{l},q_{m},\ldots\ q_{n} \}$ be the union of all $\delta^{*}_{N}$ sets formed in the previous step.

   4. If vertex $\{ q_{l},q_{m},\ldots\ q_{n}\}$ constructed in the previous step (step 2c) is not already in $G_{D}$, then add it to $G_{D}$.

   5. Add an edge to $G_{D}$ from vertex $\{ q_{i},q_{j}, \ldots\ q_{k} \}$ (vertex selected in step 2b) to vertex $\{ q_{l},q_{m},\ldots\ q_{n}\}$ (vertex possibly created in step 2d) and label the new edge with $a$ (input selected in step 2b).

3. Make every vertex of $G_{D}$ whose label contains any vertex $q_{f} \in F_{N}$ a final vertex of $G_{D}$.

4. If $M_{N}$ accepts $\lambda$, then vertex $\{ q_{0} \}$ in $G_{D}$ is also a final vertex.

This, if the loop terminates, it constructs the dfa corresponding to the nfa.

Does the loop terminate?

• Each iteration of the loop adds one edge to $G_{D}$.

• There are a finite number of edges possible in $G_{D}$.

• Thus the loop must terminate.

What is the loop invariant? (This ia a property always that must hold at the loop test.)

• If there is a walk $(\{ q_{0}\}, \ldots\ \{ \ldots\ q_{i}, \ldots \})$ in $G_{D}$ labeled $w$, then there is a walk $(q_{0}, \ldots\ q_{i})$ in $G_{N}$ labeled $w$.

2.3.4 Linz Example 2.12

Convert the nfa in Linz Figure 2.12 to an equivalent dfa.

Intermediate steps are shown in Figures 2.12-1 and 2.12-2, with the final results in Linz Figure 2.13.

2.3.5 Linz Example 2.13

Convert the nfa shown in Linz Figure 2.14 into an equivalent dfa.

$\delta_{D}(\{q_{0}\},0) = \delta^{*}_{N}(q_{0},0) = \{ q_{0}, q_{1} \}$

$\delta_{D}(\{q_{0}\},1) = \delta^{*}_{N}(q_{0},1) = \{ q_{1} \}$

$\delta_{D}(\{q_{0},q_{1}\},0) = \delta^{*}_{N}(q_{0},0) \cup \delta^{*}_{N}(q_{1},0) = \{ q_{0}, q_{1}, q_{2} \}$

$\delta_{D}(\{q_{0},q_{1}, q_{2}\},1) = \delta^{*}_{N}(q_{0},1) \cup \delta^{*}_{N}(q_{1},1) \cup \delta^{*}_{N}(q_{2},1) = \{ q_{1}, q_{2} \}$

The above gives us the partially constructed dfa shown in Linz Figure 2.15.

$\delta_{D}(\{q_{1}\},0) = \delta^{*}_{N}(q_{1},0) = \{ q_{2} \}$

$\delta_{D}(\{q_{1}\},1) = \delta^{*}_{N}(q_{1},1) = \{ q_{2} \}$

$\delta_{D}(\{q_{2}\},0) = \delta^{*}_{N}(q_{1},0) = \emptyset$

$\delta_{D}(\{q_{2}\},1) = \delta^{*}_{N}(q_{2},1) = \{ q_{2} \}$

$\delta_{D}(\{q_{0},q_{1}\},1) = \delta^{*}_{N}(q_{0},1) \cup \delta^{*}_{N}(q_{1},1) = \{ q_{1}, q_{2} \}$

$\delta_{D}(\{q_{0},q_{1}, q_{2}\},0) = \delta^{*}_{N}(q_{0},0) \cup \delta^{*}_{N}(q_{1},0) \cup \delta^{*}_{N}(q_{2},0) = \{ q_{0}, q_{1}, q_{2} \}$

$\delta_{D}(\{q_{1},q_{2}\},0) = \delta^{*}_{N}(q_{1},0) \cup \delta^{*}_{N}(q_{2},0) = \{ q_{2} \}$

$\delta_{D}(\{q_{1},q_{2}\},1) = \delta^{*}_{N}(q_{1},1) \cup \delta^{*}_{N}(q_{2},1) = \{ q_{2} \}$

Now, the above gives us the dfa shown in Linz Figure 2.16.

2.4 Reduction in the Number of States in Finite Automata

This section is not covered in this course.

3 Regular Languages and Regular Grammars

Regular languages

• are accepted by dfas and nfas
• but dfas and nfas are not concise descriptions

Thus we will examine other notations for representing regular languages.

3.1 Regular Expressions

3.1.1 Syntax

We define the syntax (or structure) of regular expressions with an inductive definition.

Linz Definition 3.1 (Regular Expression): Let $\Sigma$ be a given alphabet. Then:

1. $\emptyset$, $\lambda$, and $a \in \Sigma$ are all regular expressions. These are called primitive regular expressions.

2. If $r_{1}$ and $r_{2}$ are regular expressions, then $r_{1} + r_{2}$, $r_{1} \cdot r_{2}$, $r_{1}^{*}$, and $(r_{1})$ are also regular expressions.

3. A string is a regular expression if and only if it can be derived from the primitive regular expressions by a finite number of applications of the rules in (2).

We use the the regular expression operators as follows:

• $r + s$ represents the union of two regular expressions.

• $r \cdot s$ is the concatenation of two regular expressions.

• $r^{*}$ is the star closure of a regular expression.

• $(r)$ is the same as regular expression $r$. It is parenthesized to express the order of operations explicitly.

For example, consider regular expression $(a + (b \cdot c))^{*}$ over the alphabet $\{a,b,c\}$. Note the use of parentheses.

• $a$, $b$, and $c$ are primitive regular expressions.

• $(b \cdot c)$ is a concatenation of regular expressions $a$ and $b$.

• $(a + (b \cdot c))$ is union of regular expressions $a$ and $(b \cdot c)$.

• $(a + (b \cdot c))^{*}$ is the star-closure of regular expression $(a + (b \cdot c))$.

As with arithmetic expressions, precedence rules and conventions can be used to relax the need for parentheses.

• Star-closure ($^{*}$) has a higher precedence (i.e., priority or binding power) than concatenation ($\cdot$). That is, $r \cdot s^{*}$ is equal to $r \cdot (s^{*})$, not $(r \cdot s)^{*}$.

• Concatenation ($\cdot$) higher precedence than union ($+$). That is, $r \cdot s + t$ is equal to $(r \cdot s) + t$, not $r \cdot (s + t)$. And, transitively, star-closure has a higher precedence than concatenation.

• Concatenation operator ($\cdot$) can usually be omitted. That is, $rs$ means $r \cdot s$.

A string $(a + b +)$ is not a regular expression. It cannot be generated using the above definition (as augmented by the precedence rules and convention).

3.1.2 Languages Associated with Regular Expressions

But what do we “mean” by a regular expression? That is, what is its semantics.

In particular, what languages do regular expressions describe?

Consider the regular expression $(a + (b \cdot c))^{*}$ from above. As implied by the names for the operators, we intend this regular expression to represent the language $(\{a\} \cup \{bc\})^{*}$ which is $\{\lambda, a, bc, aa, abc, bca, bcbc, aaa, aabc,bcaa, \ldots \}$.

We again give an inductive definition for the language described by a regular expression. It must consider all the cases given in the definition of regular expression itself.

Linz Definition 3.2: The language $L(r)$ denoted by any regular expression $r$ is defined (inductively) by the following rules.

Base cases:

1. $\emptyset$ is a regular expression denoting the empty set.
2. $\lambda$ is a regular expression denoting $\{ \lambda \}$.
3. For every $a \in \Sigma$, $a$ is a regular expression denoting $\{ a \}$.

Inductive cases: If $r_{1}$ and $r_{2}$ are regular expressions, then

4. $L(r_{1} + r_{2}) = L(r_{1}) \cup L(r_{2})$
5. $L(r_{1} \cdot r_{2}) = L(r_{1})L(r_{2})$
6. $L((r_{1})) = L(r_{1})$
7. $L(r_{1}^{*}) = (L(r_{1}))^{*}$

3.1.3 Linz Example 3.2

Show the language $L(a^{*} \cdot (a + b))$ in set notation.

3.1.4 Examples of Languages for Regular Expressions

Consider the languages for the following regular expressions.

$L(a^{*} \cdot b \cdot a^{*} \cdot b \cdot (a + b)^{*})$

$=$ $\{a\}^{*} \{b\} \{a\}^{*} \{b\} \{a,b\}^{*}$

$=$ $\{ w : w \in \{ a, b \}^{*}, n_{b}(w) \geq 2 \}$

$L((a + b)^{*} \cdot b \cdot a^{*} \cdot b \cdot a^{*})$

$=$ $\{a,b\}^{*} \{b\} \{a\}^{*} \{b\} \{a\}^{*}$

$=$ same as above

$L((a+b)^{*} \cdot b \cdot (a + b)^{*} \cdot b \cdot (a + b)^{*})$

$=$ $\{a,b\}^{*} \{b\} \{a,b\}^{*} \{b\} \{a,b\}^{*}$

$=$ same as above

3.1.5 Linz Example 3.4

Consider the regular expression $r = (aa)^{*} (bb)^{*} b$.

• This expression denotes the set of all strings with an even number of $a$’s followed by an odd number of $b$’s.

• In set notation, $L(r) = \{ a^{2n}b^{2m+1} : n \geq 0, m \geq 0 \}$.

3.1.6 Linz Example 3.5

For $\Sigma = \{ 0, 1 \}$, give a regular expression $r$ such that

$L(r) = \{w \in \Sigma^{*} : w$ has at least one pair of consecutive zeros }.

• 00 must appear somewhere in any string.
• Before and after 00 there is an arbitrary string $(0 + 1)^{*}$.
• $r = (0 + 1)^{*} 00 (0 + 1)^{*}$

3.1.7 Examples of Regular Expressions for Languages

Show regular expressions on the alphabet $\{ a, b \}$ for the following languages.

• exactly one “a”

  $b^{*}ab^{*}$

• at least one “$a$”

  $b^{*}a(a+b)^{*}$ – featuring first $a$

  $(a+b)^{*}a(a+b)^{*}$ – featuring middle $a$

  $(a+b)^{*}ab^{*}$ – featuring last $a$

• at most one “$a$”

  $b^{*}ab^{*} + b^{*}$

  $b^{*}(a + \lambda)b^{*}$

• all $a$’s immediately followed by a $b$

  $(b^{*}abb^{*})^{*} + b^{*}$

3.2 Connection Between Regular Expressions and Regular Languages

3.2.1 Regular Expressions Denote Regular Languages

Regular expressions provide a convenient and concise notation for describing regular languages.

Linz Theorem 3.1 (NFAs for Regular Expressions): Let $r$ be a regular expression. Then there exists some nondeterministic finite accepter (nfa) that accepts $L(r)$. Consequently, $L(r)$ is a regular language.

Proof Sketch: Show that any regular expression generated from the inductive definition corresponds to an nfa. Here we proceed informally.

Linz Figure 3.1 diagrammatically demonstrates that there are nfas that correspond to the primitive regular expressions.

1. nfa accepts $\emptyset$
2. nfa accepts $\{ \lambda \}$
3. nfa accepts $\{ a \}$

Linz Figure 3.2 shows a general scheme for a nondeterministic finite accepter (nfa) that accepts $L(r)$, with an initial state and one final state.