PowerPoint Presentation
1/26/2021 CS332 – Theory of Computation 1
BU CS 332 – Theory of Computation
Lecture 2:
• Parts of a Theory of
Computation
• Sets, Strings, and Languages
Reading:
Sipser Ch 0
Mark Bun
January 27, 2021
What makes a good theory?
• General ideas that apply to many different systems
• Expressed simply, abstractly, and precisely
Parts of a Theory of Computation
• Models for machines (computational devices)
• Models for the problems machines can be used to solve
• Theorems about what kinds of machines can solve what
kinds of problems, and at what cost
1/26/2021 CS332 – Theory of Computation 2
What is a (Computational) Problem?
For us: A problem will be the task of recognizing whether
a string is in a language
• Alphabet: A finite set Ʃ Ex. Ʃ = {a, b}
• String: A finite concatenation of alphabet symbols
Ex. bba, ababb
𝜀 denotes empty string, length 0
Σ∗ = set of all strings using symbols from Ʃ
Ex. a, b ∗ = {𝜀, a, b, aa, ab, ba, bb, … }
• Language: A set 𝐿 ⊆ Σ∗ of strings
1/26/2021 CS332 – Theory of Computation 3
Examples of Languages
Parity: Given a string consisting of a’s and b’s, does
it contain an even number of a’s?
Ʃ = 𝐿 =
Primality: Given a natural number 𝑥 (represented in
binary), is 𝑥 prime?
Ʃ = 𝐿 =
Halting Problem: Given a C program, can it ever get
stuck in an infinite loop?
Ʃ = 𝐿 =
1/26/2021 CS332 – Theory of Computation 4
Machine Models
Computation is the processing of information by the
unlimited application of a finite set of operations or rules
1/26/2021 CS332 – Theory of Computation 5
Input a b a a
Finite
control
…
Abstraction: We don’t care how the control is implemented. We just
require it to have a finite number of states, and to transition between
states using fixed rules.
Machine Models
• Finite Automata (FAs): Machine with a finite amount of
unstructured memory
1/26/2021 CS332 – Theory of Computation 6
Input a b a a
Finite
control
…
Control scans left-to-right
Can check simple patterns
Can’t perform unlimited counting
Useful for modeling chips, simple control systems, choose-your-
own adventure games…
Machine Models
• Turing Machines (TMs): Machine with unbounded,
unstructured memory
1/26/2021 CS332 – Theory of Computation 7
Input a b a a
Finite
control
…
Control can scan in both directions
Control can both read and write
Model for general sequential computation
Church-Turing Thesis: Everything we intuitively think of as
“computable” is computable by a Turing Machine
What theorems would we like to prove?
We will define classes of languages based on which
machines can recognize them
Inclusion: Every language recognizable by a FA is also
recognizable by a TM
Non-inclusion: There exist languages recognizable by TMs
which are not recognizable by FAs
Completeness: Identify a “hardest” language in a class
Robustness: Alternative definitions of the same class
Ex. Languages recognizable by FAs = regular expressions
1/26/2021 CS332 – Theory of Computation 8
Why study theory of computation?
• You’ll learn how to formally reason about computation
• You’ll learn the technology-independent foundations
of CS
Philosophically interesting questions:
• Are there well-defined problems which cannot be solved by
computers?
• Can we always find the solution to a puzzle faster than trying
all possibilities?
• Can we say what it means for one problem to be “harder”
than another?
1/26/2021 CS332 – Theory of Computation 9
Why study theory of computation?
• You’ll learn how to formally reason about computation
• You’ll learn the technology-independent foundations
of CS
Connections to other parts of science:
• Finite automata arise in compilers, AI, coding, chemistry
https://cstheory.stackexchange.com/a/14818
• Hard problems are essential to cryptography
• Computation occurs in cells/DNA, the brain, economic
systems, physical systems, social networks, etc.
1/26/2021 CS332 – Theory of Computation 10
https://cstheory.stackexchange.com/a/14818
What appeals to you about the theory of
computation?
1. I want to learn new ways of thinking about computation
2. I like math and want to see how it’s used in computer
science
3. I’m excited about the philosophical questions about
computation
4. I want to practice problem solving and algorithmic
thinking
5. I want to develop a “computational perspective” on other
areas of math/science
6. I actually wanted to take CS 320 or 350 but they were full
1/27/2021 CS332 – Theory of Computation 11
Why study theory of computation?
Practical knowledge for developers
1/26/2021 CS332 – Theory of Computation 12
“Boss, I can’t find an efficient algorithm.
I guess I’m just too dumb.”
“Boss, I can’t find an efficient algorithm
because no such algorithm exists.”
Will you be asked about this material on job interviews?
No promises, but a true story…
More about strings and
languages
1/26/2021 CS332 – Theory of Computation 13
String Theory
• Symbol: Ex. a, b, 0, 1
• Alphabet: A finite set Ʃ Ex. Ʃ = {a, b}
• String: A finite concatenation of alphabet symbols
Ex. bba, ababb
𝜀 denotes empty string, length 0
Σ∗ = set of all strings using symbols from Ʃ
Ex. a, b ∗ = {𝜀, a, b, aa, ab, ba, bb, … }
• Language: A set 𝐿 ⊆ Σ∗ of strings
1/27/2021 CS332 – Theory of Computation 14
• Length of a string, written |𝑥|, is the number of symbols
Ex. abba = 𝜀 =
• Concatenation of strings 𝑥 and 𝑦, written 𝑥𝑦, is the
symbols from 𝑥 followed by the symbols from 𝑦
Ex. 𝑥 = ab, 𝑦 = ba ⇒ 𝑥𝑦 =
𝑥 = ab, 𝑦 = 𝜀 ⇒ 𝑥𝑦 =
• Reversal of string 𝑥, written 𝑥𝑅 , consists of the symbols
of 𝑥 written backwards
Ex. 𝑥 = aab ⇒ 𝑥𝑅 =
1/27/2021 CS332 – Theory of Computation 15
String Theory
Fun with String Operations
What is 𝑥𝑦 𝑅?
Ex. 𝑥 = aba, 𝑦 = bba ⇒ 𝑥𝑦 =
⇒ 𝑥𝑦 𝑅 =
1. 𝑥𝑅𝑦𝑅
2. 𝑦𝑅𝑥𝑅
3. 𝑦𝑥 𝑅
4. 𝑥𝑦𝑅
1/27/2021 CS332 – Theory of Computation 16
Fun with String Operations
Claim: 𝑥𝑦 𝑅 =
Proof: Let 𝑥 = 𝑥1𝑥2…𝑥𝑛 and 𝑦 = 𝑦1𝑦2…𝑦𝑚
Then 𝑥𝑦 𝑅 =
Not even the most formal way to do this:
1. Define string length recursively
2. Prove by induction on |𝑦|
1/27/2021 CS332 – Theory of Computation 17
Languages
A language 𝐿 is a set of strings over an alphabet Σ
i.e., 𝐿 ⊆ Σ∗
Languages = computational (decision) problems
Input: String 𝑥 ∈ Σ∗
Output: Is 𝑥 ∈ 𝐿? (YES or NO?)
1/27/2021 CS332 – Theory of Computation 18
Some Simple Languages
1/27/2021 CS332 – Theory of Computation 19
∅ (Empty set)
Σ∗ (All strings)
Σ𝑛 = {𝑥 ∈ Σ∗ | 𝑥 = 𝑛}
(All strings of length 𝑛)
Σ = {0, 1} Σ = {a, b, c}
Some More Interesting Languages
• 𝐿1 = The set of strings 𝑥 ∈ a, b
∗ that have an equal
number of a’s and b’s
• 𝐿2 = The set of strings 𝑥 ∈ a, b
∗ that start with (0 or
more) a’s and are followed by an equal number of b’s
• 𝐿3 = The set of strings 𝑥 ∈ 0, 1
∗ that contain the
substring ‘0100’
1/27/2021 CS332 – Theory of Computation 20
Some More Interesting Languages
• 𝐿4 = The set of strings 𝑥 ∈ a, b
∗ of length at most 4
• 𝐿5 = The set of strings 𝑥 ∈ a, b
∗ that contain at least
two a’s
1/27/2021 CS332 – Theory of Computation 21
New Languages from Old
𝐿6 = The set of strings 𝑥 ∈ a, b
∗ that have an equal
number of a’s and b’s and length greater than 4
Since languages are just sets of strings, can build them
using set operations:
𝐴 ∪ 𝐵 “union”
𝐴 ∩ 𝐵 “intersection”
ҧ𝐴 “complement”
1/27/2021 CS332 – Theory of Computation 22
New Languages from Old
𝐿6 = The set of strings 𝑥 ∈ a, b
∗ that have an equal
number of a’s and b’s and have length greater than 4
• 𝐿1 = The set of strings 𝑥 ∈ a, b
∗ that have an equal
number of a’s and b’s
• 𝐿4 = The set of strings 𝑥 ∈ a, b
∗ of length at most 4
⇒ 𝐿6 =
1/27/2021 CS332 – Theory of Computation 23
Operations Specific to Languages
• Reverse: 𝐿𝑅 = {𝑥𝑅 𝑥 ∈ 𝐿
Ex. 𝐿 = {𝜀, a, ab, aab} ⇒ 𝐿𝑅 =
• Concatenation: 𝐿1 ∘ 𝐿2 = 𝑥𝑦 𝑥 ∈ 𝐿1, 𝑦 ∈ 𝐿2}
Ex. 𝐿1 = {ab, aab} 𝐿2 = {𝜀, b, bb}
⇒ 𝐿1 ∘ 𝐿2 =
1/27/2021 CS332 – Theory of Computation 24
A Few “Traps”
String, language, or something else?
𝜀
∅
{𝜀}
{∅}
1/27/2021 CS332 – Theory of Computation 25
Languages
Languages = computational (decision) problems
Input: String 𝑥 ∈ Σ∗
Output: Is 𝑥 ∈ 𝐿? (YES or NO?)
The language recognized by a program is the set of strings
𝑥 ∈ Σ∗ that it accepts
1/27/2021 CS332 – Theory of Computation 26
What Language Does This Program Recognize?
Alphabet Σ = a, b
On input 𝑥 = 𝑥1𝑥2…𝑥𝑛:
count = 0
For 𝑖 = 1,… , 𝑛:
If 𝑥𝑖 = a:
count = count + 1
If count ≤ 4: accept
Else: reject
1/27/2021 CS332 – Theory of Computation 27
1. {𝑥 ∈ Σ∗ | 𝑥 > 4}
2. {𝑥 ∈ Σ∗ 𝑥 ≤ 4
3. {𝑥 ∈ Σ∗ | 𝑥 = 4}
4. {𝑥 ∈ Σ∗ | 𝑥 has more than 4 a′s}
5. {𝑥 ∈ Σ∗ 𝑥 has at most 4 a′s
6. {𝑥 ∈ Σ∗ | 𝑥 has exactly 4 a′s}