Transcript 形式语言与自动机 - 哈尔滨工程大学智能

计算理论
韩启龙
[email protected]
1
序
言
一. 本课的性质以及研究的内容
 任何一门学科都有它的基础和它的基本问题，如物质
的本质是什么？有机体生命的基础和起源是什么？
 什么是计算机科学的基础？什么是计算机科学的基本
问题？
诸如什么是形式语言？什么是计算？什么是能计算的？
什么是不能计算的？什么是算法？如何评价算法？什
么样的算法是可行的？这些问题能否判定？这又引出
什么是可判定的？什么是不可判定的？
 这些问题就是计算理论要讨论的问题。
2
序
言
性质：该课是计算机科学的理论课。
 计算理论：就是研究理论计算机的科学。
 理论计算机：是研究计算机的理论模型，研究计算机
的本质，也就是把计算机看成一个数学系统。(因为计算
机科学的基本思想和模型在本质上是数学——离散的。)
内容：
 形式语言与自动机理论：
正规文法与有限自动机(正规语言) 、
上下文无关文法与下推自动机(上下文无关语言)
图灵机(递归可枚举语言)
 可计算性理论： 什么是可计算？
 计算复杂性理论： 时间复杂性 、 空间复杂性。
序
言
二. 学习目的：
 了解这些计算理论
我们知道计算机不论从它的诞生还是它的快速发展过程
都没有离开计算理论，也就是它是在计算理论指导下诞生
和发展的。本课所涉及的都是计算机科学的基本问题。不
首先了解它们，是很难理解计算机科学的。作为计算机科
学与技术专业的本科生和研究生应该了解这些计算理论。
 培养能力
此外此课可以培养学生抽象逻辑思维和形式化思维的能
力。
序
言
三.学时、学分
32学时/2学分
四.基础
离散数学(数理逻辑，集合论，图论)
5
序
言
教材 & 参考书
 Textbook
 Introduction to the Theory of Computation (2nd Edition), by
Michael Sipser
 《计算理论导引 》
• 英文版，（美）MICHAEL SIPSER，
• 中文第2版：唐常杰等译
 We will follow very closely to this book
 References
 Computational Complexity, by C. Papadimitiou
 Introduction to Automata Theory, Languages, and Computation, by
J. Hopcroft, R. Motwani, and J. Ullman.
6
序
言
考 核
Homework:
Theorem Proof:
Final Exam:
-----------------------------------------Total
40%
30%
30%
100%
7
序
言
授课计划
 教材详略处理
 讲要点，前后次序有少数调整，
 教学计划，大致8周 最后两章不讲或用讨论班形式讨论，
有了基础，如果需要，已经能自学。（通常其它院校，
如川大16-18周）
 参考国内外同行（如Berkeley, MIT、四川大学等）对这门
课程教材的处理经验，准备：
 略讲或自学的部分，要求了解主要思想
 快讲的部分，要求一般了解的章节，要求了解主要方法
和演绎框架
 要求深入掌握的部分——能作题目或作难题，通过考试
8
序
言
What will you learn from this course?
How to define a computer?
Automata theory
Are there problems that a computer
cannot solve? If so, can we find one
such problem?
Computability theory
Complexity Theory
9
序
言
Complexity Theory
现实中计算的问题是多种多样的，有容易的，
有困难的。
 排序问题，相对较简单
 课程表问题，复杂（需要满足合理的限制）
复杂性理论的核心问题：
What makes some problems computationally
hard and others easy?
目前重要成果之一：按照计算难度将问题分类
 即使不能证明问题是难计算的，但也能给出某些问
题是难计算的证据的方法。
10
序
言
Complexity Theory
You have several options when you
confront a problem that appears to be
computationally hard.
1.弄清问题困难的根源——变动——容易解决；
2.求问题的并不完美的解——近似解；
3.某些问题在最坏情况下是困难的，通常易解；
4.可以选择其他计算类型，如随机计算，可加速
某些计算工作。
11
序
言
Computability theory
一些基本问题是不能用计算机解决的
如：确定一个命题是真是假
可计算理论PK复杂性理论：
1. 复杂性理论——把问题分成容易计算与难计算的
2. 可计算理论——把问题分成可解的和不可解的
Automata theory
阐述了计算的数学模型的定义和性质
12
目 录
 第0章
 第1章
 第2章
 第3章
 第4章
 第5章
 第6章
 第7章
 第8章
 第9章
 第10章
绪论——2学时
正则语言——5学时
上下文无关文法——3学时
丘奇-图灵论题——2学时
可判定性——2学时
可归约性——2学时
可计算理论高级专题——2学时
时间复杂性——4学时
空间复杂性——3学时
难解性——3学时
复杂性理论高级专题——4学时
13
序
言
Mathematics Review
Unlike other CS courses, this course is a
MATH course…
We will look at a lot of definitions,
theorems and proofs
基本数学概念与术语回顾
Set, Sequence, Function, Graph,
String…
证明技术
By construction, induction,
contradiction
14
Set（集合）
 A set is a group of items
 集合描述方法之一: list every item in the group
inside { }
E.g., { 12, 24, 5 } is a set with three items
 When the items in the set has trend: use …
E.g., { 1, 2, 3, 4, … } means the set of
natural numbers
 描述方法之二： state the rule
E.g., { n | n = m2 for some positive integer
m } means the set { 1, 4, 9, 16, 25, … }
 A set with no items is an empty set denoted by
{ } or 
15
Set（集合）
Conditional: A = { x | x  N , f(x)=0 }
Union:
AB
Intersection: AB
Complement: A
Cartesian Product: AB
Power set（幂集）: P (A) 或 2A
16
Set（集合）
The power set of A is the set of all
subsets of A, denoted by 2A
E.g., A = { 0, 1 }
2A = { {}, {0}, {1}, {0,1} }
How many items in the above power set
of A?
If A has n items, how many items does
its power set contain? Why?
子集编码：
000…00
000…01
…
111…11
17
Sequence（序列）
 A sequence of items is a list of these items in
some order（某种顺序）
 One way to describe a sequence: list the items
inside ( )
 ( 5, 12, 24 )
 Order of items inside ( ) matters
 ( 5, 12, 24 ) ≠ ( 12, 5, 24 )
 Repetition also matters
 ( 5, 12, 24 ) ≠ ( 5, 12, 12, 24 )
 Finite sequences are also called tuples（元组）
 ( 5, 12, 24 ) is a 3-tuple
 ( 5, 12, 12, 24 ) is a 4-tuple
18
Sequence（序列）
Given two sets A and B
 The Cartesian product of A and B, denoted
by A x B, is the set of all possible 2-tuples
with the first item from A and the second
item from B
E.g., A = {1, 2} and B = {x, y, z}
A x B = { (1,x), (1,y), (1,z), (2,x), (2,y),
(2,z) }
 The Cartesian product of k sets, A1, A2, …,
Ak, denoted by A1 x A2 x … x Ak, is the set
of all possible k-tuples with the ith item
from Ai
19
Functions
A function takes an input and produces an
output
If f is a function, which gives an output b
when input is a, we write
f(a) = b
For a particular function f, the set of all
possible input is called f’s domain（定义域）
The outputs of a function come from a set
called f’s range（值域）
20
Functions
To describe the property of a
function that it has domain D and
range R, we write
f : D  R
E.g., The function add (to add two
numbers) will have an input of two
integers, and output of an integer
We write: add: Z x Z  Z
21
Functions
Guess: What does the following DOW
function do?
 DOW(9,11)
 DOW(9,12)
 DOW(9,13)
 DOW(9,17)
 DOW(10,1)
= 2
= 3
= 4
= 1
= 1
What are the domain and the range of
DOW?
22
Graphs
A graph is a set of points with lines
connecting some of the points
Points are called vertices, lines are
called edges
E.g.,
23
Graphs
The number of edges at a particular vertex
is the degree of the vertex
In the previous example, 3 vertices have
degree = 2
A graph can be described by telling what
are its vertices, and what are its edges.
Formally, a graph G can be written as G =
(V, E), where V is the set of vertices, and
E is the set of edges
24
Graphs
We say a graph G is a subgraph of H if
vertices of G are a subset of the
vertices of H, and all edges in G are
the edges of H on the corresponding
vertices
Subgraph G
shown darker
Graph H
25
Graphs
A path is a sequence of vertices
connected by edges
If every two nodes have a path between
them, the graph is connected
A cycle is a path that starts and ends
at the same vertex
A tree is a connected graph with no
cycles
26
Graphs
Is the following graph connected?
Is it a tree?
Are there any cycles?
How about the
darker subgraph?
27
Directed Graphs
If lines are replaced by arrows, the
graph becomes directed
The number of arrows pointing into a
vertex is called in-degree of the vertex
The number of arrows pointing from a
vertex is called out-degree of the
vertex
A directed path is a path from one
vertex to the other vertex, following
the direction of the “arrows”
28
Directed Graphs
Is there a directed path from a to b?
a
b
29
Strings
An alphabet = a set of characters
E.g., The English Alphabet =
{A,B,C,…,Z}
A string = a sequence of characters
A string over an alphabet S
A sequence of characters, with each
character coming from S
The length of a string w, denoted by |w|,
is the number of characters in w
The empty string (written as ) is a
string of length 0
30
Strings
Let w = w1w2…wn be a string of length n
A substring of w is a consecutive（连续的）
subsequence of w (that is, wiwi+1…wj for
some i  j)
The reverse of w, denoted by wR, is the
string wn…w2 w1
A set of strings is called a language
语言：字符串的集合
31
Proof techniques（证明技术）
By construction（构造法）
By contradiction（反证法）
By induction（归纳法）
32
Proof By Construction
许多定理声明存在一种特定类型的对象。通过
说明如何构造这样的对象是证明这种定理的一
种方法，这种方法就是构造性证明方法 proof
by construction
33
By Construction [Example 1]
Let us define a graph to be k-regular
（k-正则的）if every vertex of the
graph has degree k
E.g.,
2-regular
3-regular
34
By Construction [Example 1]
Theorem: For each even number n  4,
there exists a 3-regular graph with n
vertices.
How to prove it?
35
By Construction [Example 1]
Proof Idea: 构造出一个n个顶点的3正则图。
将n个点均匀排列在一个圆上，对每一个顶点，
连接其左右邻点各为一条边，第三条边与其相
对点相连。
证明: Label the vertices by 1,2,…, n.
The edge set E is the union of
E1 = { {x,x+1} | for x = 1,2,…,n-1 }
E2 = { {1,n} }
E3 = { {x, x+ (n/2)} | for x =
1,2,…,n/2 }
Then, it is easy to check that the degree
of each vertex is exactly 3.
36
By Contradiction [Example 2]
Page 13
By Contradiction [Example 3]
Page 14
37
Homework
0.1
0.2
0.5
0.6
0.9
0.10
0.11
38