编译原理
武汉大学计算机学院编译原理课程组
本章内容简介
·DFA、NFA
·DFA到NFA的转换
·正规文法与FA
·正规表达式与FA
第3章有穷自动机
自动机是一种能进行运算并实现自我控制的装置，计算机就是一部自动机。自动机是描述符号串处理的强有力的工具。
“确定”：下一个输入字符惟一地确定了下一个当前状态。
1. 确定的有穷自动机DFA DFA=(Q ，∑，t，q 0，F)
3.1有穷自动机的形式定义
Q——有穷非空的状态集。
∑——有穷的输入字母表。
t——映射Q ×Σ→Q 。
q 0——∈Q ，是开始状态。
F——?Q ，非空终止状态集合。
3.1 FA的形式定义—DFA
2. FA的表示：
①状态转换表
②状态转换图
DFA映射的扩充，使得DFA可以描述对符号串的识别。DFA=（Q ，Σ，t，q 0，F）扩充的映射
t：Q ×Σ*→Q
定义为⑴
t(q,ε)=q ⑵t(q,aα)=t(t(q,a),α)
其中q ∈Q ，a ∈Σ, α∈Σ*。
3.1 FA 的形式定义——DFA 的扩充
DFA=（Q ，Σ，t，q 0，F），如果t(q 0,α)=∈F ，则α可被DFA接受。被DFA 识别的符号串集合，记为L(A)。
3.1 FA 的形式定义——FA 的等价性
如果两个有穷自动机A 1和A 2满足
L(A 1)=L(A 2)
则称自动机自动机A 1和A 2是等价的。
FA 的等价性举例
DFA A=({q 0，q 1}，{a，b}，t，q 0，{q 0})
t(q 0，a)=q 1，t(q 1，b)=q 0
DFA B=({q 0′,q 1′,q 2′}，{a，b}，t′,q 0′,{
q 0′,q 2′})t′(q 0′,a)=q 1′，t′(q 1′,b)=q 2′，t′(q
2′,a)=q 1′
L(A)=L(B)={(ab)n |n≥0}
3. 非确定的有穷自动机NFA NFA=(Q，∑，t，Q
0，F)
3.1有穷自动机的形式定义
Q——有穷非空的状态集。
∑——有穷的输入字母表。
t——映射Q×Σ→Q的幂集。
Q0——?Q，是开始状态集。
F——?Q，非空终止状态集合。
NFA=（Q ，Σ，t，Q 0，F）扩充的映射
t：Q ×Σ*→Q 的幂集
定义为⑴
t(q,ε)=q ⑵t(q,aα)=t(q 1,α)∪t(q 2,α)∪…∪t(q n ,α)
其中a ∈Σ, α∈Σ*，t(q,a)∈{q 1 ，q 2 ，…，q n }。
3.1 FA 的形式定义——NFA 的扩充
如果q ∈t(q 0,α) ，q 0∈Q 0，q ∈F,
则α可被NFA接受。被NFA识别的符号串集合，记为L(A)。
·DFA 最小化——构造状态集合的划分
·确定化——子集法、造表法
NDFA 到DFA 的转换：
3.2 NFA到DFA的转换
3.2 NFA到DFA的转换——子集法、造表法
①状态子集的ε闭包
假设I是状态集合Q的一个子集。
定义I的ε闭包（ε-CLOSURE（I））为：
ⅰ.如果状态P∈I，则P∈ε-CLOSURE（I）；
ⅱ.如果状态P∈I，则Pˊ∈ε-CLOSURE（I）。
其中Pˊ为由状态P出发，经任意条ε弧能到达的Q中的状态。
3.2 NFA到DFA的转换——子集法、造表法
子集
②I
a
设I是状态集Q的一个子集。
由I中的状态出发，经历一条a弧（跳过a弧前的任意条ε弧）可到达的状态的集合称为J，则
I a=ε-CLOSURE（J）
NFA到DFA的转换
③利用子集法构造确定的有穷自动机
′，F′）。与NFA 假设已知的NFA为（Q′，Σ′，t′，Q
，F）。
等价的DFA为（Q，Σ，t，Q
Σ：可由NFA所含有的输入字母集合得到。
Q：由Q′的一些子集组成。
q0：是包含NFA的开始状态在内的Q ′的一个子集。
F：由包含NFA的终止状态F ′在内的Q ′的一些子集组成。
计算理论 字母表：一个有穷的符号集合。 字母表上的字符串是该字母表中的符号的有穷序列。 一个字符串的长度是它作为序列的长度。 连接反转Kleene星号L* ，连接L中0个或多个字符串得到的所有字符串的集合。 有穷自动机：描述能力和资源极其有限的计算机模型。 有穷自动机是一个5元组M=(K,∑,?,s,F),其中 1）K是一个有穷的集合，称为状态集 2）∑是一个有穷的集合，称为字母表 3）?是从KX∑→K的函数，称为转移函数 4）s∈K是初始状态 5）F?K是接收状态集 M接收的语言是M接收的所有字符串的集合，记作L(M). 对于每一台非确定型有穷自动机，有一台等价的确定型有穷自动机 有穷自动机接受的语言在并、连接、Kleene星号、补、交运算下是封闭的。 每一台非确定型有穷自动机都等价于某一台确定型有穷自动机。一个语言是正则的当且仅当它被有穷自动机接受。 正则表达式：称R是一个正则表达式，如果R是
1）a，这里a是字母表∑中的一个元素。 2）?，只包含一个字符串空串的语言 3）?，不包含任何字符串的语言 4)(R1∪R2),这里R1和R2是正则表达式 5）(R10R2),这里R1和R2是正则表达式 6）(R1*),这里R1*是正则表达式 一个语言是正则的当且仅当可以用正则表达式描述。 2000年4月 1、根据图灵机理论,说明现代计算机系统的理论基础。 1936年，图灵向伦敦权威的数学杂志投了一篇论文，题为《论数字计算在决断难题中 的应用》。在这篇开创性的论文中，图灵给“可计算性”下了一个严格的数学定义，并 提出著名的“图灵机”(Turing Machine)的设想。“图灵机”不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算机装置，用来计算所有能想像得到的可计算函数。这个装置由下面几个部分组成：一个无限长的纸带，一个读写头。（中间那个大盒子），内部状态（盒子上的方块，比如A,B,E,H），另外，还有一个程序对这个盒子进行控制。这个装置就是根据程序的命令以及它的内部状态进行磁带的读写、移动。工作带被划分为大小相同的方格，每一格上可书写一个给定字母表上的符号。控制器可以在带上左右移动，它带有一个读写出一个你期待的结果。这一理论奠定了整个 现 代计算机的理论基础。“图灵机”更在电脑史上与“冯·诺依曼机”齐名，被永远载
1、请你从形式定义、计算过程和对应的语言特点关系等诸方面综合比较DFA、PDA和图灵机 2、对于简单文法（正则语言、上下文无关语言），能够根据其产生式写出其语言 3、正则语言泵引理和上下文无关语言泵引理的理解、相互比较和应用 4、最简DFA、最简PDA的概念；DFA和PDA的简化过程；（带ε和不带ε的）NFA化简成最简DFA的过程 5、图灵机的Golder编码和通用图灵机的编码 6、上下文无关文法的乔姆斯基范式 7、DFA的计算过程 8、上下文无关文法的推导过程以及其歧义相关概念及分析 9、关于四类乔姆斯基语言及其对应的自动机类型特点分析 10、四类乔姆斯基语言的各种运算类型并形式化表示 11、关于CFG和DFA的若干判定问题 12、关于若干渐进符号：同阶渐进符号Θ、大O、小O和大Ω符号的含义和用法 13、请从NP类问题、P类问题、确定型单带TM、确定型多带TM、非确定型TM等角度综述 时间复杂性规律 相关例题： 1、请你综合比较DFA、PDA和图灵机 2、请写出下列表达式生成的正则语言 1）设有文法G=(V,T,P,S)，其中V={S,A,B}，T={a,b}，P：S→aB；S→bA；A→bAA；A →a；A→aS；B→b；B→bS；B→aBB 请写出L(G)= 2）设一个有穷自动机M=(Q,∑,δ,q0,F)，其中Q={q0,q1,q2,q3)，∑={0,1}, F={q0}，δ如下： δ(q0,0)=q2, δ(q0,1)=q1, δ(q1,0)=q3, δ(q1,1)=q0 δ(q2,0)=q0, δ(q2,1)=q3, δ(q3,0)=q1, δ(q3,1)=q2 请写出L(M)= 3）设有文法G=({S,A},{a,b,c,d};R,S)，其中R：S→aSd|aAd， A→bAc|bc 请写出L(G)= 3、用泵引理证明下列论点 1）A1={a n b n c n|n≥0}不是正则语言 2）D={ww|w∈{0，1}*}不是上下文无关语言 4、把下面状态转换图代表的DFA变化成最简DFA
编译原理作业三 T3-1构造自动机A ，使得它能识别形式如±dd*·d*E ±dd 的实数，其中，d ∈{0,1,2,3,4,5,6,7,8,9} T3-4将图所示NFA 确定化和最小化。 解：依据该NFSA 的状态图构造DFSA 如下表所示。 I I x I y [q 0] 0 [q 1] 1 [q 2] 2 [q 1] 1 [q 2,q 3] 3 [q 2] 2 [q 1,q 3] 4 [q 2,q 3] 3 [q 3,q 4] 5 [q 1,q 3] 4 [q 1,q 3] 4 [q 2,q 3,q 4] 6 [q 3] 7 [q 3,q 4] 5 [q 3,q 4] 5 [q 3] 7 [q 2,q 3,q 4] 6 [q 3,q 4] 5 [q 1,q 3] 4 [q 3] 7 [q 3,q 4] 5 [q 3] 7 DFSA 相应的状态图如下图所示： 6 1 2 3 4 5 7 X X y y y X X X X X y y y y S 3 1 4 2 5 6 7 ± d E d d d d ±
对DFSA 进行最小化： 已知K={0，1,2,3,4,5,6,7}，K 可分为两个子集 K1={0,1,2,3,4,7}（非终态集） K2={5,6}（终态集） 在K1中，因为状态1只有x 输入，状态2只有y 输入，其他状态均有x ，y 输入，所以可以将K1分割为K11={0,3,4,7} K12={1} K13={2} 在K11中 {0}x=1∈K12 {3,4,7}x={5,6}?K2 故可将K11分割为 K111={0} K111={3,4,7} {3,4,7}x={5,6}?K2 {3,4,7}y={4,7}?K111 因此状态3,4,7是否等价取决于对K2的划分结果 在状态K2={5,6}中 {5,6}x=5∈K2 {5,6}y={4,7}?K111 所以状态5,6等价，所以状态3,4,7等价 所以，将原状态集合划分为{0}、{3,4,7}、{1}、{2}、{5,6} 最小化后的状态图为： S 1 2 3 5 X X X X y y y y
第三章 ******************************************************* ************************ 1．构造下列语言的DFA ( 陶文婧 02282085 ) （1）{0，1}* ，1 （2）{0，1}+ ，1 （3）{x|x{0，1}+且x中不含00的串} （设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态） （4）{ x|x{0，1}*且x中不含00的串} （可接受空字符串，所以初始状态也是接受状态） （5）{x|x{0，1}+且x中含形如10110的子串} （6）{x|x{0，1}+且x中不含形如10110的子串} （设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）
（7）{x|x{0，1}+且当把x看成二进制时，x模5和3同余，要求当x为0时，|x|=1,且x0时，x的首字符为1 } 1.以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进 入陷阱状态 2.设置7个状态：开始状态q s,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以5 余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态q t （8）{x|x{0，1}+且x的第十个字符为1} （设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态） （9）{x|x{0，1}+且x以0开头以1结尾} （设置陷阱状态，当第一个字符为1时，进入陷阱状态）
（10）{x|x{0，1}+且x中至少含有两个1} （11）{x|x {0，1}+且如果x以1结尾，则它的长度为偶数；如果x以0结尾，则它的长度为奇数} 可将{0，1}+的字符串分为4个等价类。 q0：[]的等价类，对应的状态为终止状态 q1:x的长度为奇且以0结尾的等价类 q2：x的长度为奇且以1结尾的等价类 q3: x的长度为偶且以0结尾的等价类 q4: x的长度为偶且以1结尾的等价类 （12）{x|x是十进制非负数}
第三章词法分析 本章要点 １．词法分析器设计， ２．正规表达式与有限自动机， ３．词法分析器自动生成。 本章目标： １．理解对词法分析器的任务，掌握词法分析器的设计； ２．掌握正规表达式与有限自动机； ３．掌握词法分析器的自动产生。 本章重点： 1．词法分析器的作用和接口，用高级语言编写词法分析器等内容，它们与词法分析器的实现有关。应重点掌握词法分析器的任务与设计，状态转换图等内容。 2．掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法。 （1）非形式描述的语言?正规式 （2）正规式→ NFA（非确定的有限自动机） （3）NFA → DFA（确定的有限自动机） （4）DFA →最简DFA 本章难点 （1）非形式描述的语言?正规式 （2）正规式→ NFA（非确定的有限自动机） （3）NFA → DFA（确定的有限自动机） （4）DFA →最简DFA
作业题 一、单项选择题 （按照组卷方案，至少15道） 1. 程序语言下面的单词符号中，一般不需要超前搜索 a. 关键字 b. 标识符 c. 常数 d. 算符和界符 2. 在状态转换图的实现中，一般对应一个循环语句 a. 不含回路的分叉结点 b. 含回路的状态结点 c. 终态结点 d. 都不是 3. 用了表示字母，d表示数字， ={l，d}，则定义标识符的正则表达式可以是：。 (a)ld*(b)ll*(c)l(l | d)*(d)ll* | d* 4. 正规表达式(ε|a|b)2表示的集合是 (a){ε，ab，ba，aa，bb} (b){ab，ba，aa，bb} (c){a，b，ab，aa，ba，bb} (d){ε，a，b，aa，bb，ab，ba} 5. 有限状态自动机可用五元组（V T，Q，δ，q0，Q f）来描述，设有一有限状态自动机M的定义如下： V T={0，1}，Q={q0，q1，q2}，Q f={q2}，δ的定义为： δ（q0，0）=q1δ（q1，0）=q2 δ（q2，1）=q2δ（q2，0）=q2 M所对应的状态转换图为。
2006年秋《计算理论基础》本科生试卷 填空题 1、确定型有穷自动机的形式定义是一个5元组(Q，∑，δ，q0，F)其中： (1)Q为有穷状态集，（2）∑有穷字母表，（3）δ(q,a)是转移函数，它的第1个自变量为q∈Q，第二个自变量a∈∑，其结果δ(q,a)∈Q，即为Q×∑→Q的函数（映射），（4）q0为初始状态(一般只有一个)，（5）F有一些接受状态（可以为多个。 2、非确定型有穷自动机N接受字符串w=b1b2…b m，是指存在状态序列r0,r1,…,r m,且满足：（1）r0=q0；（2）r i+1∈δ(r i,a i+1) (i=0,1,…,m-1)，(3)r m∈F。 3、正则表达式的定义是：（1）a∈∑，空串ε，空集Φ均为合法的正则表达式，（2）若R1，R2是正则表达式，则(R1?R2)、R1?R2、R1*均是正则表达式。 4、将正则表达转换成自动机时，先建立单个字符的自动机，再用并、连、星号运算得到复杂正则表达的自动机，而将自动机转换为正则表达式时，需要先建立新开始状态与一个新接受态，在新开始状态与原开始状态之间连上空串边，在原来所有的接受状态与新接受状态间连空串边。 5、对于正则语言A的任意字符串s，当其长度≥p（泵长度）时，则一定存在满足|y|>0、|xy|≤p分解方式S=xyz，使得任意i≥0，xy i z∈A。这是正则语言的性质，基于此性质并利用反证法可证明一个语言不是正则语言，这时需要验证满足“|y|>0、|xy|≤p”的每种可能分解方式，都不满足“任意i≥0，xy i z∈A”。 6、非确定型下推自动机PDA接受w=w1w2…w m，是指存在状态序列r0,r1,…,r m，栈字字符串序列s0,s1,…,s m∈Γ*，满足：（1）r0=q0,s0=ε；（2）(r i+1,b)∈δ(r i,w i+1,a)，其中s i=at(此时a 为栈顶元素)，s i+1=bt(b为当前动作后的栈顶元素)；（3）r m∈F,s m=ε。 7、Turing机特点：（1）可以从输送带中读出字符，也可以修改输入带中的字符；（2）可沿输入带向右移动直到遇到字符串结束标志为止，也可从右向左移动直到遇到左端标志为止；（3）可以边读写边移动读写头，也可以不读写而单纯移动；（4）如果进入了“接受”状态则停机(不必消耗所有字符)，如果进入了“拒绝”状态也停机，否则一直运行，永不停机。 8、图灵机的形式定义是7元组(Q,∑,Γ,δ,q0,q accept,q reject)，其中：（1）Q为状态集；（2）∑为输入字母表，不包括空白符号；（3）Γ为带字母表，包括∑与空格；（4）δ：Q?Γ→Q?Γ?{L,R}，转换函数，第1个自变量的取值范围是Q，第2个自变量的取值范围是Γ，其值域是一个三元组，第一个分量表示下一个状态，第二个分量表示写入到输入带上的字符，第三个分量表示下一步的位置；（5）q0∈Q是初始状态；（6）q accept∈Q是接受状态；（7）q reject∈Q拒绝状态，且q reject≠q accept。 9、图灵机M接受字符串w，是指存在一系列的格局C1,C2,…,C k，使得：（1）C1是M 在输入w的起始格局，即C1=q0w；（2）每个C i确定地产生C i+1；（3）Ck是接受格局，即从起始格局起，经过有限步后可达到接受格局。 二、简述题 1、每个多带图灵机等价于某台单带图灵机。请参考下图陈述单带图灵机描述多带图灵机的的细节。多带图灵机为M，待的单带图灵机记为S。
形式语言与自动机课后作业答案 第二章 4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。 答：G={N,T,P,S} 其中N={S,A,B,C,D} T={x,y} 其中x∈{所有字母} y∈{所有的字符} P如下: S→x S→xA A→y A→yB B→y B→yC C→y C→yD D→y 6．构造上下文无关文法能够产生 L={ω/ω∈{a,b}*且ω中a的个数是b的两倍} 答：G={N,T,P,S} 其中N={S} T={a,b} P如下: S→aab S→aba S→baa S→aabS S→aaSb S→aSab S→Saab S→abaS S→abSa S→aSba S→Saba S→baaS S→baSa S→bSaa S→Sbaa 7．找出由下列各组生成式产生的语言（起始符为S） (1)S→SaS S→b (2)S→aSb S→c (3)S→a S→aE E→aS 答：（1）b(ab)n /n≥0}或者L={(ba)n b/n≥0} (2) L={a n cb n /n≥0} (3)L={a2n+1 /n≥0} 第三章 1．下列集合是否为正则集，若是正则集写出其正则式。 （1）含有偶数个a和奇数个b的{a,b}*上的字符串集合 （2）含有相同个数a和b的字符串集合 （3）不含子串aba的{a,b}*上的字符串集合 答：（1）是正则集，自动机如下 (2) 不是正则集，用泵浦引理可以证明，具体见17题（2）。
(3) 是正则集 先看L’为包含子串aba的{a,b}*上的字符串集合 显然这是正则集，可以写出表达式和画出自动机。（略） 则不包含子串aba的{a,b}*上的字符串集合L是L’的非。 根据正则集的性质，L也是正则集。 4．对下列文法的生成式，找出其正则式 （1）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→abS A→bB B→b B→cC C→D D→bB D→d （2）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→cC A→bB B→bB B→a C→D C→abB D→d 答：(1) 由生成式得： S=aA+B ① A=abS+bB ② B=b+cC ③ C=D ④ D=d+bB ⑤ ③④⑤式化简消去CD，得到B=b+c(d+bB) 即B=cbB+cd+b =>B=(cb)*(cd+b) ⑥ 将②⑥代入① S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+ε)(cb)*(cd+b) (2) 由生成式得： S=aA+B ① A=bB+cC ② B=a+bB ③ C=D+abB ④ D=dB ⑤ 由③得 B=b*a ⑥ 将⑤⑥代入④ C=d+abb*a=d+ab+a ⑦ 将⑥⑦代入② A=b+a+c(d+b+a) ⑧ 将⑥⑧代入① S=a(b+a+c(d+ab+a))+b*a =ab+a+acd+acab+a+b*a 5.为下列正则集，构造右线性文法： (1){a,b}* (2)以abb结尾的由a和b组成的所有字符串的集合
一．填空题 1.语言类P 、PSPACE 、NP 、NPSPACE 、EXPTIME 之间的关系为 （EXPTIME NPSPACE PSPACE NP P ?=??）。 2.产生语言{12n 03n |n ≥0}的上下文无关文法是（00011|A A ε→）。 3.命题“利用递归定理，一个TM M 可以得到自己的描述
第三章习题参考解答 3.1 构造自动机A，使得 ① ② ③当从左至右读入二进制数时，它能识别出读入的奇数； ④它识别字母表{a, b}上的符号串，但符号串不能含两个相邻的a，也不含两个相邻的b； ⑤它能接受字母表{0, 1}上的符号串，这些符号串由任意的1、0和随后的任意的11、00对组成。 ⑥它能识别形式如 ±dd*? d*E ±dd 的实数，其中，d∈{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}。 3.2 构造下列正规表达式的DFSA： ① xy*∣yx*y∣xyx； ② 00∣(01)*∣11； ③ 01((10∣01)*(11∣00))*01； ④ a(ab*∣ba*)*b。 3.3 消除图3.24所示自动机的空移。 b ε q 1 q 2 q 3 a b a,b q a q 6 q 4 q 5 a b ε ε ε 图3.24 含空移的自动机 3.4 将图3.25所示NDFSA确定化和最小化。 x y q q 1 q 2 q 4 q 3 x y x y x,y x 图3.25 待确定化的NDFSA
3.5 设e、e1、e2是字母表∑上的正规表达式，试证明 ① e∣e=e；② {{e}}={e}；③ {e}=ε∣e{e}；④ {e1 e2} e1= e1{e2 e1}; ⑤ {e1∣e2}={{e1}{e2}}={{e1}∣{e2}}。 3.6 构造下面文法G[Z]的自动机，指明该自动机是不是确定的，并写出它相应的语言： G[Z]: Z→A0 A→A0∣Z1∣0 3.7 设NDFSA M=({x, y},{a, b},f, x, {y}), 其中，f(x, a)={x, y}, f(x, b)={y}, f(y, a)=?, f(y, b)={x, y}。试对此NDFSA确定化。 3.8 设文法G[〈单词〉]： 〈单词〉→〈标识符〉∣〈无符号整数〉 〈标识符〉→〈字母〉∣〈标识符〉〈字母〉∣〈标识符〉〈数字〉 〈无符号整数〉→〈数字〉∣〈无符号整数〉〈数字〉 〈字母〉→a∣b 〈数字〉→1∣2 试写出相应的有限自动机和状态图。 3.9 图3.29所示的是一个NDFSA A，试构造一个正规文法G，使得L(G)= L(A)。 A B b S a a,b C a D b 图3.29 FSA A 3.10 构造一个DFSA，它接受∑={a, b}上的符号串，符号串中的每一个b都有a直接跟在右边；然后，再构造该语言的正规文法。 参考答案 3.1 解 (1) (2) (3) 依题意，当二进制数的末尾为1时，表示此二进制数为奇数。因此自动机接收由0、1构成的一个二进制串，且串的最后一位必为1（特殊情况下，接收数字1）。构造的自动机如下: z S 1 0,1
1.如果一个语言被有穷自动机识别，则这个语 言是正则语言。 2.正则语言在并运算、连结、星号运算下封闭 3.每一台非确定有穷自动机都等价与一台确 定型有穷自动机。 4.一个语言是正则的当且仅当有一台非确定 型有穷自动机识别。 5.空集连接到任何集合上得到空集，空串连接 到任何一个串上不改变这个字符串。 6.一个语言是正则的，当且仅当有一个正则表 达式描述。 7.如果一个语言是正则的，则可以用正则表达 式描述它。 8.任何一个上下文无关语言都可以用乔姆斯 基范式的上下文无关文法产生。 9.一个语言是上下文无关的当且仅当存在一 台下推自动机识别它。 10.如果一个语言被下推自动机识别，则它是上 下文无关的。 11.每一个正则语言都是上下文无关的。 1.格局——图灵机计算过程中，当前状态、当 前带内容和读写头当前的位置组合在一起， 称为图灵机的格局。 2.图灵可识别（递归可枚举语言）——如果一 个语言可能被某一图灵机识别，则称该语言 是图灵可识别的。 3.图灵可判定（递归语言）——如果一个语言 能被某一图灵机判定，则称它是一个图灵可 判定的。 ——在输入上运行一个TM时，可能出现三种结果：接受、拒绝或者循环。这里循环仅仅指机器不停机，而不一定是这个词所指的那样，永远以同样的方式重复同样的步骤。 ——图灵机有两种方式不接受：一种是它进入拒绝状态而拒绝它，另一种是进入循环。 4.判定器——有时候很难区分进入循环还是 需要耗费很长时间的运行，因此，我们更喜 欢讨论所有输入都停机的图灵机，他们永远 不循环，这种机器称为判定器。他们总是能 决定接受还是拒绝，也称识别某个语言的判 定器判定该语言。 5.每一个可判定语言都是图灵可识别的。 6.每一个多带图灵机等价于一个单带图灵机。 7.非确定型图灵机都等价于一个确定型图灵 机。8.如果一个语言是图灵可识别的，当且仅当存 在非确定型图灵机识别它。 9.一个语言是图灵可判定的，当且仅当存在非 确定型图灵机判定它。 10.丘奇图灵论题——算法的明确定义。 11.详细描述图灵机的术语——①形式化描述， 详尽的写出图灵机的状态、转移函数，这是 最底层次的、最详细程度的描述。②描述水 平要高一些，称为实现描述，使用日常用语 来描述图灵机，没有给出状态和转移函数③ 高水平描述，他也是使用日常用语来描述算 法，忽略了实现模型不需要提及图灵机怎样 管理它的带子和读写头。 12.A DFA（确定型有穷自动机）、A NFA（非确定 型有穷自动机）、A REX（正则表达式）、 E DFA（判Φ的确定型有穷自动机）、EQ DFA（两 个判别同一个语言的DFA）、 A CFG（上下文无关文法）、ＥCFG（判Φ上下文 无关文法）、 A LBA（线性界限自动机）、是一个可判定语言 每一个上下文无关语言是可判定的。 A TM（图灵机）、停机问题、HALT TM（一个图 灵机对于给定的输入是否停机）、E TM（不接受任 何语言图灵机）、REGULAR TM（正则图灵机）、 EQ TM（接受串相等的图灵机）、 E LBA（不接受语言的线性界限自动机）、 ALL CFG、PCP（波斯地图对应实例）是不可判定 的。 A TM（补）是不可识别的。 13.一个语言的补是由不在此语言中的所有串 构成的语言。如果一个语言的补集是图灵可 识别的语言，则称它是补图灵可识别的。 14.一个语言是可判定的，当且仅当它既是图灵 可识别的，也是补图灵可识别的。 15.设M是一个图灵机，w是一个串。M在w 上的一个接受计算历史（accepting computation history）是一个格局序列C1、 C2、……、C l，其中C1是M在w上的起始 格局，C l是M的一个接受格局，且每个C i 都是C i-1的结果，即符合M规则。M在w 上的一个拒绝计算历史可类似定义。只是 C l是一个拒绝格局。 16.计算历史都是有限序列。如果M在w上永 不停机，则在M上既没有接受历史，也没 有拒绝计算历史存在。确定型机器在任何给 定的输入上最多只有一个计算历史。非确定 型机器即使在单个输入上都有多个计算历 史，他们与各个分支相对应。 17.线性有穷自动机是一种受到限制的图灵机， 它不允许其读写头离开包含输入带的区域。 如果此机器试图将它的读写头离开输入的 两个端点，则读写头就在原地保持不动。这 与普通的图灵机读写头不会离开带子的左 端点方式一样。 18.讲一个问题归约为另一个问题的概念可以 用多种方式来定义，选择哪种方式要根据具 体应用的情况。我们选择一种简单方式的可 归约性，叫做映射可归约性。 19.用映射可归约性把问题A归约为问题B指 的是：存在一个可计算函数，他将问题A 的实例转换成问题B的实例。如果有了这样 一个转换函数（称为归约），就能用B的解 决方案来解决A。 20.函数f：∑*→∑*是一个可计算函数，如果 有某个图灵机M，使得每个输入w上M停 机，且此时只有f(w)出现在带上。 21.语言Ａ是映射可归约到语言Ｂ的，如果存在 可计算函数f：∑*→∑*使得对每个ｗ ｗ∈Ａ<=>f(w)∈Ｂ 22.记做Ａ≤ｍＢ，称作函数ｆ为Ａ到Ｂ的归约。 如果Ａ≤ｍＢ且Ａ是不可判定的，则Ｂ也是不 可判定的。 如果Ａ≤ｍＢ且Ｂ是图灵可识别的，则Ａ也是 图灵可识别的 23.EQ TM既不是图灵可识别的，也不是补图灵 可识别的。 24.令ｔ：Ｎ→Ｒ＋是一个函数，定义时间复杂 性类TIME(t(n))为由时间O(t(n))的图灵机可 判定的所有语言的集合。 25.t(n)是一个函数，t(n)≥n。则每一个多带图 灵机都和某一个O(t2(n))时间的单带图灵机 等价。 26.t(n)是一个函数，t(n)≥n。则每一个t(n)时间 的非确定型单带图灵机都与某一个2O(t(n))时 间的确定型单带图灵机等价。 27.P类是一个语言类，该类在多项式时间内可 判定。 28.PATH∈P、RELPRIME∈P、每一个上下文 无关文法都是P 29.一个语言在NP中，当且仅当它能被某个非 确定型多项式时间的图灵机判定。 30.{HAMPATH, CLQUE, SUBSET-SUM, SAT, 3SAT, UHAMPATH, }∈NP 31.P=成员可以快速判定的语言类 NP=成员可以快速验证的语言类 32.若存在多项式时间图灵机M，使得在任何输 入w上，M停机时f(w)恰好在带上，函数f： ∑*→∑*是一个多项式时间可计算函数。 33.语言A称作多项式时间映射可归约到语言 B，或者简称为多项式时间可归约到B，记 为Ａ≤pＢ，若存在多项式时间可计算函数 f：∑*→∑*，对于每一个w，有 ｗ∈Ａ<=>f(w)∈Ｂ 函数f称为A到B的多项式时间归约。 34.列文-库克定理 SAT∈P，当且仅当P=NP 35.3SAT多项式时间可归约到CLIQUE。 36.令f：N→R+是一个函数。空间复杂性类和 NSPACE(f(n))定义如下： SPACE(f(n))={L|L是被O(f(n))空间的确定型 图灵机判定的语言} NSPACE(f(n))={L|L是被O(f(n))空间的非确定 型图灵机判定的语言} 37.萨维奇定理
计算理论习题解答 练习 1.1图给出两台DFA M i和M2的状态图?回答下述有关问题? a. M 1的起始状态是q1 b. M1的接受状态集是{q2} c. M2的起始状态是q1 d. M2的接受状态集是{ q1, q4) e. 对输入aabb,M1经过的状态序列是q1, q2, q3, q1, q1 f. M 1接受字符串aabb吗？否 g. M 2接受字符串￡吗？是 1.2给出练习 2.1中画出的机器M1和M2的形式描述 M 1=(Q 1,2,3 1,q1,F1)其中 1) Q1={q 1,q2,q3,}; 2) 2 ={a,b}; 3) 3 1 为： a b q1q2 q1 q2q3 q3 q3q2 q1 4) q1 5) F1={q 2} M2=(Q2,2,3 2,q2,F2)其中 1) Q2={q 1,q2,q3,q4}; 2) 2 ={a,b}; 3) 3 2为： a b q1q1 q2 q2q3 q4 q3q2 q1 q4q3 q4 3) q2是起始状态 4) F2={q 1,q4} 1.3 DFA M 的形式描述为({q1, q2, q3, q4, 机器的 q5}, {u,d}, 3 ,q3, {q3}),其中3在表2-3中给出。试画出此状态图。
1.6画出识别下述语言的DFA的状态图。 a){w | w从1开始以0结束} c) {w | w含有子串0101} 彳 c n 1 d) {w | w的长度不小于3,且第三个符号为0} 0,1
,1 g) {w | w 的长度不超过 5} 0,1 0,1 0,1 h){w | w i){w | w 的奇位置均为1} k) { 2} 斗「0,1 1 I) {w | w 含有偶数个0，或恰好两个1} 1 - 1 . 1 0 0 0 1 m)空集 _ 0,1 n)除空串外的所有字符串 1.7给出识别下述语言的 NFA ，且要求符合规定的状态数。
第三章有穷自动机 1、教学目的及要求： 本章介绍有关有穷自动机的基本概念和理论以及正规文法、正规表达式与有穷自动机之间的相互关系。要求掌握正则文法、状态转换图、DFA、NFA、正规式和正规集的基本概念。 2、教学内容： 本章介绍有关有穷自动机的基本概念和理论以及正规文法、正规表达式与有穷自动机之间的相互关系。 3、教学重点： 状态转换图。 4、教学难点： ◇正规式的定义-如何用作单词的描述工具 ◇有穷自动机的定义和分类-如何用作单词的识别系统 ◇正规式到有穷自动机的转换算法-词法分析程序的自动构造原理 ◇正则文法、正规集、DFA、NFA的相互转化。 5、课前思考 ◇什么是有穷自动机？ ◇什么是状态转换图？ 6、章节内容 第一节有穷自动机的形式定义 第二节 NFA到DFA的转换 第三节正规文法与有穷自动机 第四节正规表达式与FA 第五节 DFA在计算机中的表示
3.1 有穷自动机的形式定义 有穷状态自动机(Finite-state Automata 或简称FA)在识别功能上与正规文法类等价，而且也等价于一个特殊类型的语言产生器——正规表达式(Regular Expression)。因此许多简单的程序语言都可由FA所识别。事实上，它是描述词法的有效工具，也是进行词法分析的主要理论基础。 为了构造词法分析程序，要研究构词法，每种词类的结构模式以及识别它的数学模型——有穷自动机。它的模拟程序可以作为词法分析程序的控制程序。 有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。 有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有穷自动机(Nondeterministic Finite Automata) 。 一、确定有穷自动机的形式定义 一个确定的有穷自动机M(记作DFA M)是一个五元组Ｍ＝(K，Σ，f，S，Z)，其中(ａ) K是一个有限状态集合。 (ｂ) Σ是一个字母表，它的每个元素称为一个输入字符。 (ｃ) S∈K，S 称为初始状态，唯一。 (ｄ) Z?K，Z称为终态集合, 终态也称可接受状态或结束状态。 (ｅ) f是转换函数，是一个从K×Σ到K的单值映射。f(k i，a)＝k j（k i,k j∈Ｑ,a∈Σ）k j称为k i的一个后继状态。 确定性的体现：初始状态唯一；转换函数为单值映射。 例：设DFA M=({S，U，V，Q}，{a，b}，f，S，｛Q｝)其中 f（S，a）＝U，f（S，b）＝V f（U，a）＝Q，f（U，b）＝V f（V，a）＝U，f（V，b）＝Q f（Q，a）＝Q，f（Q，b）＝Q 因为（1）初始状态唯一是S，（2）每个转换函数均为单值映射。所以该FA为确定有穷自动机。 二、状态转换表 DFA的映射关系可以由一个矩阵表示，矩阵的行标表示状态，列标表示输入字符，矩阵元素表示f(s,a)的值，这个矩阵称为状态转换表。 例：
第三章作业答案 1．已知DFA M1与M2如图3－18所示。 (敖雪峰 02282068) (1) 请分别给出它们在处理字符串1011001的过程中经过的状态序列。 (2) 请给出它们的形式描述。 S q q 1 图3－18 两个不同的DFA 解答：(1)M1在处理1011001的过程中经过的状态序列为q 0q 3q 1q 3q 2q 3q 1q 3; M2在处理1011001的过程中经过的状态序列为q 0q 2q 3q 1q 3q 2q 3q 1; (2)考虑到用形式语言表示,用自然语言似乎不是那么容易, 所以用图上作业法把它们用正则表达式来描述: M1: [01+(00+1)(11+0)][11+(10+0)(11+0)]* M2: (01+1+000){(01)*+[(001+11)(01+1+000)]*} ******************************************************************************* 2．构造下列语言的DFA ( 文婧 02282085 ) （1）{0，1}* ，1 （ 2）{0，1} + ，1 （3）{x|x {0，1}+ 且x 中不含00的串} （设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）
（4）{ x|x∈{0，1}*且x中不含00的串} （可接受空字符串，所以初始状态也是接受状态） （5）{x|x∈{0，1}+且x中含形如10110的子串} （6）{x|x∈{0，1}+且x中不含形如10110的子串} （设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态） （7）{x|x∈{0，1}+且当把x看成二进制时，x模5和3同余，要求当x为0时，|x|=1,且x≠0时，x的首字符为1 } 1.以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进入 陷阱状态 2.设置7个状态：开始状态q s,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以 5余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态q t
编译原理作业集-第三章-修 订版 -标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII
第三章词法分析 本章要点 １．词法分析器设计， ２．正规表达式与有限自动机， ３．词法分析器自动生成。 本章目标： １．理解对词法分析器的任务，掌握词法分析器的设计； ２．掌握正规表达式与有限自动机； ３．掌握词法分析器的自动产生。 本章重点： 1．词法分析器的作用和接口，用高级语言编写词法分析器等内容，它们与词法分析器的实现有关。应重点掌握词法分析器的任务与设计，状态转换图等内容。 2．掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法。 （1）非形式描述的语言正规式 （2）正规式 NFA（非确定的有限自动机） （3）NFA DFA（确定的有限自动机） （4）DFA 最简DFA 本章难点 （1）非形式描述的语言正规式 （2）正规式 NFA（非确定的有限自动机） （3） NFA DFA（确定的有限自动机） （4） DFA 最简DFA
作业题 一、单项选择题 （按照组卷方案，至少15道） 1. 程序语言下面的单词符号中，一般不需要超前搜索 a. 关键字 b. 标识符 c. 常数 d. 算符和界符 2. 在状态转换图的实现中，一般对应一个循环语句 a. 不含回路的分叉结点 b. 含回路的状态结点 c. 终态结点 d. 都不是 3. 用了表示字母，d表示数字， ={l，d}，则定义标识符的正则表达式可以是：。 (a)ld* (b)ll* (c)l(l | d)* (d)ll* | d* 4. 正规表达式(ε|a|b)2表示的集合是 (a){ε，ab，ba，aa，bb} (b){ab，ba，aa，bb} (c){a，b，ab，aa，ba，bb} (d){ε，a，b，aa，bb，ab，ba} 5. 有限状态自动机可用五元组（V T，Q，δ，q0，Q f）来描述，设有一有限状态自动机M的定义如下： V T={0， 1}，Q={q0， q1， q2}，Q f={q2}，δ的定义为： δ（q0，0）=q1δ（q1，0）=q2 δ（q2，1）=q2δ（q2，0）=q2
《计算理论》复习题总结 1、自动机、可计算性、复杂性内涵及关系； 计算理论的三个传统的核心领域：自动机、可计算性和复杂性。通过“计算机的基本能力和局限性是什么？“这一问题将这三个领域联系在一起。可计算理论与复杂性理论是密切相关的，在复杂性理论中，目标是把问题分成容易计算的和难计算的；而在可计算理论中，是把问题分成可解的和不可解。自动机阐述了计算的数学模型的定义和性质，主要包含两种模型：有穷自动机模型；上下文无关文法模型。可计算性理论和复杂性理论需要对计算机给了一个准确的定义。自动机理论允许在介绍与计算机科学的其他非理论领域有关的概念时使用计算的形式化定义。 2、有穷自动机、正则语言、正则表达式、非确定有穷自 动机、非正则语言； 有穷自动机：描述能力和资源极其有限的计算机模型。是一个5元组（Q，∑，δ，q0,F），其中1）Q是一个有穷集合，称为状态集。2）∑是一个有穷集合，称为字母表。3）δ：Q×∑→Q是转移函数。4）q0∈Q是起始状态。5）F?Q是接受状态集。 正则语言：如果一个语言能被有穷自动机识别。 正则表达式：用正则运算符构造描述语言的表达式。称R是正则表达式，如果R是：1）a，a是字母表中的一个元素；2）ε；3）?;4）（R1?R2）；5）(R1 R2)；6）(R1*) 非确定有穷自动机：是一个5元组（Q，∑，δ，q0,F），其中1）Q是有穷状态集。2）∑是有穷字母表。3）δ：Q×∑ε→P（Q）是转移函数。4）q0∈Q是起始状态。5）F?Q是接受状态集。 3、上下文无关语言及上下文无关文法、歧义性、乔姆 斯基范式、下推自动机、等价性、非上下文无关语言； 上下文无关语言：用上下文无关文法生成的语言。 上下文无关文法：是一个4元组（V，∑，R，S）且1）V是一个有穷集合，称为变元集2）∑是一个与V不相交的有穷集合，称为终结符集3）R是一个有穷规则集，每条规则由一个变元和一个由变元及终结符组成的字符串构成，4）S∈V是起始变元 歧义性：如果字符串W在上下文无关文法G中有两个或者两上以上不同的最左派生，则称G歧义地产生的字符串W。如果文法G歧义的产生某个字符串则称G是歧义的。 乔姆斯基范式：一个上下文无关文法如果它的每一个规则具有如下形式A→BC A→a其中a为任意终结符，ABC为任意变元且BC不是起始变元，此外允许规则S→ε其中S是起始变元。 下推自动机：是6元组Q，∑，Γ，δ，q0,F），这里Q，∑，Γ，F都是有穷集合，并且1）Q是状态集 2）∑是字母表 3）Γ是栈字母表 4）δ： Q×∑ε×Γε→P（Q×Γε）是转移函数学 5）q0∈Q是起始状态。6）F?Q是接受状态集。 4、各种等价性； 每一台非确定型有穷自动机等价于一台确定的有穷自动机；一个语言是正则的当且仅当可以用正则表达式描述；一个语言是上下文无关的则存在一台下推自动机识别它。 5、计算科学；能性问题；Church-Turing论题；计算； 可计算； 计算科学：系统的研究信息描述和变换的算法，包括其理论、分析、设计、效率、实现和应用。用计算科学涵盖并称谓计算机科学和计算机工程。计算机科学所研究问题的核心是能行问题。能行问题：什么能被（有效的）自动化？什么不能被（有效）的自动化？ Church－Turing论题：可计算性等价于Turing机可计算性。 计算：Truing机所进行的工作就是计算。 可计算：Turing机能够进行的工作就叫可计算。 6、几个计算模型；各种计算模型的特点；图灵机的特点； 计算模型：1、递归函数。G?del，Church，等人提出并完善了递归函数理论。从数学演算的思想出发，考虑从简单的、直观上可计算的函数出发构复杂的可计算函数。2、Turing机（理论模型）：Turing研究的Turing机计算模型与现代计算机更接近，在Turing机的基础上引进了大量的自动机。 3、Church－λ演算：用来描述计算过程，基本思想主要用于函数式程序语言的研制。4、Post系统（符号变换系统）：Post系统的基础上引进了大量的形式语言。 Turing机的特点：存储无穷，时间无限制。Turing机可计算只是理论上可计算，并不是现实可计算。现实可计算：研究计算复杂性。但如果Turing机不可计算则现实更不可计算。 7、原语言，指令系统，输入输出规定； 原语言：变元、标号（语句标号）、指令：X＝X＋1；X＝X－1；To A IF X≠0；To A；Y＝X输入变元用x表示 x，x1，x2，x3，……输出变元用y表示，函数只输出一个值。 对程序做如下两点规定：1、当程序开始执行时自动认为一切变元的值为0 （输入变元除外）2、当程序出现下列两种情形之一时，自动认为停机。a、转向无定义的标号b、执行程序的最后一条指令。 8、n元程序对应的n元函数的定义； 若程序P恰有n个输入变元X1，X2，……，Xn，而没有其它X变元，则称P为n元程序。