COMP2022|2922
Models of Computation
Lesson 5a: Introduction to Machine Models
Presented by
Sasha Rubin
School of Computer Science
What sort of problems are programs meant to solve?
– A computational problem specifies what the input can be and what the output should be.
1. Given numbers x, y, output x + y?
2. Given numbers x, y, output x × y?
3. Given strings w, t, decide if w is a substring of t? 4. Given a string e, decide if e is well-bracketed?
– The last two are called decision problems because their output is either 1 (meaning Yes) or 0 (meaning No).
1/80
Main modeling assumption
We will focus on decision problems where the input is a string.
For you to think about
1. Is focusing on decision problems a serious restriction? What if we replaced the problem
Given numbers x, y, output x + y. by the decision problem
Given numbers x, y, z, decide if x + y = z.
2. Is focusing on input strings a serious restriction?
– We can encode almost anything as a string.
– How would you encode an integer, or a set of integers, or a
graph?
2/80
Strings
Definition
An alphabet Σ is a nonempty finite set of symbols.
Example
– Σ = {0, 1} is the classic binary alphabet.
– Σ = {a, b, c, · · · , z} is the lower-case English alphabet.
3/80
Strings
Definition
A string over Σ is a finite sequence of symbols from Σ. The number of symbols in a string is its length.
Example
– 0110 is a string of length 4 over alphabet {0, 1}
– bob is a string of length 3 over alphabet {a,b,c,··· ,z}.
– If w has length n we write w = w1w2 ···wn where each wi ∈ Σ.
– There is only one string of length 0. It is denoted ε.
– The set of all strings over Σ is denoted Σ∗.
– The reason for this notation will be made clear later.
3/80
Strings
Concatenation of strings
– The concatenation of strings x, y is the string xy formed by appending y to the end of x.
– The concatenation of x = 010 and y = 01 is 01001. – wε=εw=wforallstringsw.
– 01ε=01
3/80
Decision problems
Definition
A decision problem is a function P : Σ∗ → {0, 1}. Example
1 if the length of the string s ∈ {0, 1}∗ is odd,
P(s) =
0 otherwise.
We will also write the decision problem like this:
Input: String s over alphabet {0, 1}.
Output: 1 if the length of the string s is odd, and 0 otherwise.
4/80
Programs that solve problems
Definition
A program solves a decision problem P : Σ∗ → {0, 1} if for every input string x ∈ Σ∗, the program on input x outputs P(x).
5/80
Programs that solve problems
1 2 3
Definition
A program solves a decision problem P : Σ∗ → {0, 1} if for every input string x ∈ Σ∗, the program on input x outputs P(x).
Example
The program
def L(s): # s binary -string
# a % b returns the remainder of a divided by b return len(s)%2
solves the decision problem
Input: A string s.
Output: 1 if the length of the string s is odd, and 0 otherwise.
5/80
Programs that solve problems
Definition
A program solves a decision problem P : Σ∗ → {0, 1} if for every input string x ∈ Σ∗, the program on input x outputs P(x).
Example
The program
1 def Q(x): # binary string x encoding natural number 2 # least significant digit first
3 return x[0]
solves the decision problem
Input: A string encoding a natural number. Output: 1 if the integer is odd, and 0 otherwise.
5/80
What decision problems can be solved by programs?
Input: Strings encoding integers x, y, z. Output: 1 if z = x + y, and 0 otherwise.
Input: Strings w, t.
Output: 1 if w is a substring of t, and 0 otherwise.
Input: Strings encoding integers x, y, z. Output: 1 if z = x × y, and 0 otherwise.
Input: String encoding an arithmetic expression e. Output: 1 if e is well-bracketed, and 0 otherwise.
Input: String encoding a (Python) program p. Output: 1 if p enters an infinite loop, and 0 otherwise.
6/80
What decision problems can be solved by programs?
We will see that, in a very precise sense:
1. “addition” and “substring” can be decided with limited memory, 2. “multiplication” and “well-bracketed” require recursion,
3. “infinite loop” cannot be decided by any program.
To do this, we introduce mathematical models of programs that solve decision problems.
1. Limited memory: regular expressions and finite automata (L5-L7).
2. Plus recursion: context-free grammars and pushdown automata (L8-L9).
3. Universal: Turing machines and Lambda-calculus (L10-L11).
7/80
One more modeling choice
We will think of decision problems as deciding if the input is in some set of strings.
Example
Here are two ways of describing the same problem.
Input: A binary string encoding a natural number. Output: 1 if the integer is odd, and 0 otherwise.
Input: A binary string encoding a natural number.
Output: 1 if the string is in the set {w ∈ {0,1}∗ : w[0] = 1}, and 0 otherwise.
8/80
Sets of strings are called languages. They are so important, they have their own field of study called Formal Language Theory.
9/80
Languages
Definition
A set L ⊆ Σ∗ of strings is called a (formal) language over Σ.
Example
Let Σ = {a, b}.
– L1 ={x∈Σ∗ :xstartswithab}
– L2 ={x∈Σ∗ :xhasanevennumberofbs}.
– L3 ={x∈Σ∗ :xhasthesamenumberofasasbs}.
– The empty set ∅.
– Note. The empty set ∅ has no elements in it, but the set {ε} has one element in it, the empty string.
10/80
For you to think about after class
1. Is HTML a formal language? If so, what is the alphabet and what are the strings?
2. Is music a formal language? If so, what is the alphabet and what are the strings?
11/80
Important operations on languages
Definition
Let A, B be languages over Σ.
– The union of A and B, written A ∪ B, is the language
{x∈Σ∗ :x∈Aorx∈B}.
– The concatenation of A and B, written A ◦ B, is the language {xy∈Σ∗ :x∈A,y∈B}.
– The star of A, written A∗, is the language {x1x2···xk ∈Σ∗ :k≥0,k∈Z,eachxi ∈A}.
123
∗
– SoA ={ε}∪ A ∪A◦A∪A◦A◦A∪….
12/80
Important operations on languages
Examples
1. {a,ab}∪{ab,aab}= 2. {a,ab}◦{ab,aab}= 3. {a,ab}∗ =
13/80
COMP2022|2922
Models of Computation
Lesson 5b: Regular Languages Chapter 1 of Sipser (eReserve)
Presented by
Sasha Rubin
School of Computer Science
Regular expressions in a nutshell
– Expressions that describe languages – Extremely useful
– Pattern matching (Control-F) – Specification of data formats – Lexical analysis
– Based on three operations:
– Language Union L1 ∪ L2
– Language Concatenation L1 ◦ L2
– Language Iteration/Kleene-star L∗
14/80
Regular expressions: Syntax
Definition
Let Σ be an alphabet. The regular expressions over Σ are defined by the following recursive process:
R1. The symbols ∅ and ε are regular expressions.
R2. Each symbol a ∈ Σ is a regular expression.
R3. If R1, R2 are regular expressions then so is (R1 ∪ R2)
R4. If R1, R2 are regular expressions then so is (R1 ◦ R2), also written (R1R2)
R5. If R is a regular expressions then so is R∗
15/80
Regular expressions
Examples
Let Σ = {a, b}. – (a∪∅)
– (a◦ε)
– b∗
– (a∗∪b∗) – (a∪b)∗ – (a◦b)∗
16/80
Regular expressions: Semantics
A regular expression R matches certain strings, collectively called L(R).
Definition
Let Σ be an alphabet. The language L(R) represented by a regular expression R is defined by the following recursive procedure:
1. L(∅) = ∅ and L(ε) = {ε}.
2. L(a)={a}fora∈Σ.
3. L((R1 ∪ R2)) = L(R1) ∪ L(R2).
4. L((R1◦R2))=L(R1)◦L(R2).
5. L(R∗) = L(R)∗ = {ε}∪L(R)∪L(R)◦L(R)∪L(R)◦L(R)◦L(R)∪···
17/80
Regular expressions
Notation.
– The symbol ∪ in the regular expression (a∗ ∪ ε) is just a symbol (in some texts it is denoted + or |), and is different from the union operation on languages.
– So, strictly speaking, we should have defined the syntax of regular expressions using different notation, e.g., (a∗ ∪ ε).
– But this is inconvenient to write, and so we overload and use the same symbol in the syntax and the semantics.
18/80
Regular expressions
Examples
Let Σ = {a, b}.
– L((a∪∅))=
– L((a◦ε))=
– L(b∗) =
– L((a∗∪b∗))= – L((a∪b)∗)= – L((a◦b)∗)=
19/80
Regular expressions
Examples
Let Σ = {a, b}. Write regular expressions for the following languages:
1. The set of strings ending in a.
– ((a∪b)∗◦a),alsowritten((a∪b)∗a).
2. The set of strings whose second last symbol is an a. – ((a∪b)∗ ◦a◦(a∪b))
3. The set of strings that have aba as a substring. – ((a∪b)∗ ◦a◦b◦a◦(a∪b)∗)
4. The set of strings of even length.
5. The set of strings with an even number of a’s.
20/80
Regular expressions
Important questions
1. Which languages can be described by regular expressions? All languages?
2. There are natural decision problems associated with regular expressions. Are there programs that solve them?
Input: Regular expression R and string s Output: 1 if s ∈ L(R), and 0 otherwise.
Input: Regular expressions R1, R2
Output: 1 if L(R1) = L(R2), and 0 otherwise.
21/80
COMP2022|2922 Models of Computation
Lesson 5c: Finite Automata Presented by
Sasha Rubin
School of Computer Science
Finite automata in a nutshell
A deterministic finite automaton is like a program that can only scan its input string once, and cannot write anything. At the end of reading the input string, it must decide if the string is in the language (accept it) or not (reject it).
22/80
Why study such a simple model of computation?
1. It is part of computing culture.
– first appeared in McCulloch and Pitt’s model of a neural network (1943)
– then formalised by Kleene (American mathematician) as a model of stimulus and response
2. It has numerous practical applications.
– lexical analysis (tokeniser)
– pattern matching
– communication protocols with bounded memory – circuits with feedback
– finite-state reactive systems
– finite-state controllers
– non-player characters in computer games
– …
3. It is simple to implement/code.
23/80
Drawing deterministic finite automata (DFA)
24/80
Definition of a determinisitc finite automaton (DFA)
Definition
A deterministic finite automaton (DFA) M is a tuple (Q,Σ,δ,q0,F) where
1. Q is a finite set of states,
2. Σ is a finite set called the alphabet,
3. δ : Q × Σ → Q is the transition function,
4. q0 ∈ Q is the start state, and
5. F ⊆ Q is the set of accept states, sometimes called final states.
′a′
If q = δ(q, a) we write q −→ q , called a transition. The source of
the transition is q, the target is q′, and the label is a.
25/80
Language described by a DFA
A DFA M describes a language L(M): all strings that label paths from the start state to an accepting state.
Examples
Let Σ = {a, b}. Draw DFAs for the following languages: 1. {aba}
2. all strings over Σ
3. the set of strings ending in a
4. L((a◦b)∗)
5. the set of strings with an even number of a’s 6. the set of strings with an odd number of b’s
26/80
Designing DFAs
Draw a DFA for the language {aba}
27/80
Designing DFAs
Draw a DFA for the set of all strings over {a, b}
28/80
Designing DFAs
Draw a DFA for the set of all strings ending in a
29/80
Designing DFAs
Draw a DFA for the set of all strings matching (ab)∗
30/80
Designing DFAs
Draw a DFA for the set of all strings with an even number of a’s
31/80
Designing DFAs
Draw a DFA for the set of all strings with an odd number of b’s
32/80
Definition of the language recognised by a DFA
Definition
Let M = (Q,Σ,δ,q0,F) be a DFA, and let w = w1w2 ···wn be a string over Σ.
– ArunofM onwisasequencer=r0r1···rn ofstatesofM such that
1. r0 = q0, and
2. δ(ri,wi+1)=ri+1 fori=0,…,n−1.
– The run r is accepting if also 3. rn ∈F.
– If w has an accepting run then we say that M accepts w.
The set L(M) = {w ∈ Σ∗ : M accepts w} is the language recognised by M.
33/80
DFAs
Important questions
1. Which languages can be described by DFAs? All languages?
2. There are natural decision problems associated with DFAs. Are there programs that solve them?
Input: DFA M and string w
Output: 1 if w ∈ L(M), and 0 otherwise.
Input: DFA M
Output: 1 if L(M) = ∅, and 0 otherwise.
Input: DFAs M1,M2
Output: 1 if L(M1) = L(M2), and 0 otherwise.
34/80
The problem
Input: DFA M and string w
Output: 1 if w ∈ L(M), and 0 otherwise.
1 2 3 4 5 6 7 8
is solved by the program
def run(M,w):
cur = q_0
for i = 1 to len(w):
cur = δ(cur,w_i) if cur in F:
return 1 else:
return 0
35/80
Definition
A language L is called regular if L = L(M) for some DFA M.
36/80
Theorem
The regular languages are closed under complementation. That is, if A is regular, then Σ∗ \ A is regular.
Example
Let Σ = {a, b}. Draw DFAs for the following languages: 1. strings that contain aba as a substring
2. strings that do not contain aba as a substring
37/80
Theorem
The regular languages are closed under complementation. That is, if A is regular, then Σ∗ \ A is regular.
Construction (“swap accept and reject states”)
1. Given A = L(M) for some DFA M = (Q,Σ,δ,q0,F). 2. We will construct a DFA M ′ recognising Σ∗ \ L(M ). 3. DefineM′ =(Q,Σ,δ,q0,F′)whereF′ =Q\F.
37/80
Theorem
The regular languages are closed under union. That is, if A and B are regular, then A ∪ B is regular.
Example
Let Σ = {a, b}. Draw DFAs for the following languages: 1. the strings consisting of an even number of a’s
2. the strings consisting of an odd number of b’s
3. the strings consisting of an even number of a’s or an odd number of b’s.
38/80
39/80
40/80
41/80
Theorem
The regular languages are closed under union. That is, if A1 and A2 are regular, then A1 ∪ A2 is regular.
Construction (“product”)
1. Given DFA Mi = (Qi, Σ, δi, qi, Fi) recognising Ai, i = 1, 2. 2. We will construct a DFA M recognising L(A1) ∪ L(A2). 3. Define M = (Q,Σ,δ,q0,F) where
– Q=Q1×Q2,
– δ maps state (s1,s2) on input a ∈ Σ to state
(δ1(s1, a), δ2(s2, a)),
– q0 =(q1,q2),
– F ={(s1,s2):s1 ∈F1 ors2 ∈F2}.
42/80