Notes on Models of Computation
H. Conrad Cunningham
014April 2022
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.
Why study theory?
In this course, we study the following models:
The mathematical concepts used in the Linz textbook include:
Students in this course should be familiar with the following set concepts from previous study in mathematics:
Laws for operations on the empty set:
DeMorgan’s Laws:
Function $f: D \rightarrow R$ means that
Function $f$ is a
A relation on $X$ and $Y$ is any subset of $X \times Y$.
An equivalence relation $\equiv$ is a generalization of equality. It is:
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:
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.
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.
Students in this course should be familiar with the following proof techniques from previous study in mathematics:
We will see an example of an inductive proof in the next section.
Three fundamental ideas are the major themes of this course:
Our concept of language is an abstraction of the concept of a natural language.
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$.
We can define the length of a string with the following inductive definition:
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)
$| u \lambda |$ | |
= | { identity for concatenation } $\longleftarrow$ justification for step in braces |
$| u |$ | |
= | { identity for + } |
$| u | + 0$ | |
= | { definition of length } |
$| u | + | \lambda |$ |
Inductive case
$v=wa$
(that is, length is greater than 0)
Induction hypothesis:
$|uw| = |u| + |w|$
$| u (w a) |$ | |
= | { associativity of concatenation } |
$| (uw)a |$ | |
= | { definition of length } |
$| uw | + 1$ | |
= | { induction hypothesis } |
$(|u| + |w|) + 1$ | |
= | { associativity of + } |
$|u| + (|w| + 1)$ | |
= | { definition of length (right to left) } |
$|u| + (|w a|)$ |
Thus we have proved $|uv| = |u| + |v|$. QED.
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^{*}$).
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.
Sentences $aabb$ and $aaaabbbb$ are in $L$, but $aaabb$ is not.
As with most interesting languages, $L$ is an infinite language.
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$.
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.
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$.
Consider $G = (\{S\},\{a,b\},S,P)$ where P is the set of productions
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.
Clearly, $w_{0} = S$ is a sentential form, the start symbol.
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.
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:
To show that a language $L$ is generated by a grammar $G$, we must prove:
For every $w \in L$, there is a derivation using $G$.
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.
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$.
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.
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)$.
An automaton is an abstract model of a compute
As shown in Linz Figure 1.4, a computer:
reads input from an input file – one symbol from each cell – left to right
produces output
may use storage – unlimited number of cells (may be different alphabet)
has a control unit
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
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:
<digit>
then the
machine moves to state 3. The machine stops reading with answer No
(non-accepting).<letter>
or
<underscr>
then it moves to state 2. The machine
continues.<letter>
,
<underscr>
, or <digit>
, then the
machine reads the input and remains in state 2.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.
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).
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.
currentState := $q_{0}$
To visualize a dfa, we use a transition graph constructed as follows:
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.