Transcript Document

Introduction to the Theory of
Computation
My name: 冯好娣
My office: 计算中心430
Email: [email protected]
 2004 SDU
Text book: Introduction to the Theory of
Computation, Michael Sipser, 机械工业出版社
References:
 Martin, John C. Introduction to Languages and The
Theory of Computation (3rd edition), MC. GrawHill.
2003
 Garey, Michael R. and Johnson, David S. Computers
and Intractability: A guide to Theory of NPcompleteness, W.H.Freeman 1979
 2004 SDU
2
Grading
Final exam 70%
Homework 30%
 2004 SDU
3
Lecture one:
Overview and Concepts
 2004 SDU
What is this course about
Why it is important
Subject:
The fundamental mathematical properties of computers
(hardware, software and certain applications).
Questions:
What does computation mean?
What can be computed and what can not?
How quickly?
With how much memory?
On which type of machines?
 2004 SDU
5
The three central areas of TOC
The main question in TOC:
What are the fundamental capabilities and limitations of computers?
Each of the three central areas of TOC focuses on this question
but interprets it differently.

Automata Theory:
What can be computed with different sorts of weak machines, such as
 Finite automata,
 Pushdown automata, etc.?

Computability Theory:
What can be computed with the strongest possible machines,
such as Turing machines?
Complexity Theory:
How efficiently can things be computed, in particular, in how much
 Time,
 2004 SDU
6
 Space?
Set
Set-- Any collection of distinct objects (“elements”)

E ={1,2,3,…}; E ={x | x = 2y for some positive integer y}; E = {G | G is a spanning tree of
graph F}; etc.
aA -- “a is an element of A” or “a is in A”
aA -- “a is not an element of A” or “a is not in A”
S T --- “S is a subset of T”, i.e., every element of S is also an element of T
AB -- “the union of A and B”, i.e., the set of objects that are in either A or B or both
AB -- “the intersection of A and B” , i.e., the set of objects that are in both A and B
A -- “The complement of a set A” contains exactly those elements under
consideration that are not in A
-- “the empty set”
P(S) --- “the power set of S”
i.e. the set of all subsets of S
 2004 SDU
7
Sequence, Tuple, Cartesian Product
•Sequence-- a list of objects in order.
• E.g., (7, 7, 21,35) is a sequence of natural numbers.
•n Tuple– a sequence of n elements.
• (2,3)—2 tuple (pair)
• (3,1,2)– 3 tuple (triple)
• Two n-tuples (a1, a2, a3, …, an) and (b1, b2, b3, …, bn) are equal if and only if
they contain exactly the same elements in the same order, i.e. ai = bi for 1  i 
n.
•Cartesian product of two sets A and B is defined by
AB = {(a, b) | aA and bB}
• A = 
Similarly, S1  S2  ...  Sn={(s1,s2,…,sn) | s1S1, s2S2, …, snSn}
• Ak = A A … A
 2004 SDU
8
function
Function (mapping) f from set A to set B --- assignment of a unique element f(a)B
to each aA
A
the domain of f
B
f
a
1
2
3
4
b
c
f: A  B
N --- natural numbers: {0,1,2,…}
the range of f
the type of f
R --- rational numbers: {0, 5, 8.6, 1/3, etc.}
If x,y always take values from N, what are the types of f,g,h?
f(x)=2x
g(x)=x/2
h(x,y)=x+y
f: N  N
g: N  R
h: NN  N
 2004 SDU
9
Graphs
Undirected graph: G=(V, E), where V is a set of
nodes(vertices), and E is a set of edges, i.e., set of
unordered pairs of nodes.
Directed graph: edge is ordered.
Path: sequence of nodes connected by edges.
Simple path: no repeat of nodes
Connected: each pair of nodes are connected by path
Cycle: a path with same start and end points
Tree: connected and acyclic
Degree: # of edges incident with a specified node
Leaves: nodes of a tree with degree one
 2004 SDU
10
Strings and Languages
An alphabet is a finite, nonempty set A of objects called symbols.
 ={0,1}, ={a,b,c,d,…,z}
A string over an alphabet A is a finite sequence of symbols from A.
 000110 is a string over {0,1}, abcdefsssg is a string over {a,b,c,…}
String length-- |w|, number of symbols in w.
Empty string-- string with length zero. 
Concatenation of strings x, y, written as xy-- the string obtained by
end of x
appending y at the
 E.g., u = “monkey”, v = “business”, uv = “monkeybusiness”
k
xk --- x x … x,
i.e., to concatenate a string to itself many times.
A substring of a string s-- a consectutive sequence withhin s.
A Language (over alphabet ) -- a set of strings (over ).

* is the language consists of all the strings on .
 2004 SDU
11
Boolean logic
A Boolean variable takes on one of 0 (FALSE)
and 1 (TRUE).
The negation of x, denoted by x, is 1-x.
We will use the following Boolean operators:
  conjunction
 disjunction
 negation
 2004 SDU
12
If and only if
P if and only if Q, or P iff Q.
 if: QP
 Only if: PQ
 2004 SDU
13
Sets equality
A=B
 For each xAx B
 For each xBx A
 2004 SDU
14
Disproof by Counterexample
A counterexample to x P(x) is an object c so that P(c) is false.
Statements such as x (P(x)  Q(x)) can be disproved by
simply providing a counterexample.
Statement: “All birds can fly.”
Disproved by counterexample: Penguin.
 2004 SDU
15
Proof by construction
To prove some special objects exist.
Example: for each even number n greater than 2,
there exists a 3-regular graph with n nodes.
 2004 SDU
16
Proof by contradiction
2
is irrational.
Proof: otherwise,
2
Then:
m
n
2
is rational. W.l.o.g, suppose
, where m and n have no common divisors.
2n 2  m 2 , which implies that m is even, let m  2k ,
then 2n 2  4k 2 , then n 2  2k 2 , which implies n is even,
a contradict ion.
 2004 SDU
17
Induction
•The principle of mathematical induction is a useful tool for
proving that a certain predicate is true for all natural numbers.
•If we have a propositional function P(n), and we want to prove
that P(n) is true for any natural number n, we do the following:
•
•
•
 2004 SDU
Show that P(1) is true.
(basis step)
Show that if P(n) then P(n + 1) for any n  N.
(inductive step)
Then P(n) must be true for any n  N.
(conclusion)
18
Induction
•
1.
2.
Example (“Gauss”): P(n): 1 + 2 + … + n = n (n + 1)/2
Show that P(1) is true.
(basis step)
Show that if P(n) then P(n + 1) for any n  N (inductive step)
1.
2.
3.
4.
5.
6.
7.
3.
If 1 + 2 + … + n = n (n + 1)/2
Then 1 + 2 + … + n + (n + 1) = n (n + 1)/2 + (n + 1)
= (2n + 2 + n (n + 1))/2
= (2n + 2 + n2 + n)/2
= (2 + 3n + n2 )/2
= (n + 1) (n + 2)/2
= (n + 1) ((n + 1) + 1)/2
Then P(n) must be true for any n  N (conclusion)
 2004 SDU
19