Microsoft PowerPoint – CS332-Lec02
1/27/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/27/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.
• String: A finite concatenation of alphabet symbols
Ex.
denotes empty string, length 0
∗ = set of all strings using symbols from
Ex. ∗
• Language: A set ∗ of strings
1/27/2021 CS332 ‐ Theory of Computation 3
Examples of Languages
Parity: Given a string consisting of ’s and ’s, does
it contain an even number of ’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/27/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/27/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/27/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/27/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/27/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/27/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/27/2021 CS332 ‐ Theory of Computation 10
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/27/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/27/2021 CS332 ‐ Theory of Computation 13
String Theory
• Symbol: Ex.
• Alphabet: A finite set Ex.
• String: A finite concatenation of alphabet symbols
Ex.
denotes empty string, length 0
∗ = set of all strings using symbols from
Ex. ∗
• Language: A set ∗ of strings
1/27/2021 CS332 ‐ Theory of Computation 14
• Length of a string, written , is the number of symbols
Ex.
• Concatenation of strings and , written is the
symbols from followed by the symbols from
Ex.
• Reversal of string , written consists of the symbols
of written backwards
Ex.
1/27/2021 CS332 ‐ Theory of Computation 15
String Theory
Fun with String Operations
What is
Ex.
1.
2.
3.
4.
1/27/2021 CS332 ‐ Theory of Computation 16
Fun with String Operations
Claim:
Proof: Let and
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 )
Some More Interesting Languages
• The set of strings ∗ that have an equal
number of ’s and ’s
• The set of strings ∗ that start with (0 or
more) ’s and are followed by an equal number of ’s
• The set of strings ∗ that contain the
substring ‘ ’
1/27/2021 CS332 ‐ Theory of Computation 20
Some More Interesting Languages
• The set of strings ∗ of length at most 4
• The set of strings ∗ that contain at least
two ’s
1/27/2021 CS332 ‐ Theory of Computation 21
New Languages from Old
The set of strings ∗ that have an equal
number of ’s and ’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
The set of strings ∗ that have an equal
number of ’s and ’s and have length greater than 4
• The set of strings ∗ that have an equal
number of ’s and ’s
• The set of strings ∗ of length at most 4
1/27/2021 CS332 ‐ Theory of Computation 23
Operations Specific to Languages
• Reverse:
Ex.
• Concatenation:
Ex.
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
On input :
count =
For
If
count count
If count : 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