淮阴工学院
编译原理课程设计报告
选题名称:有穷自动机的化简与确定化
系（院）:计算机工程学院
专业:计算机科学与技术
班级:软件1071
姓名: XXX 学号: XXXXXXX
指导教师:王文豪、陈剑洪
学年学期:2010 ~ 2011 学年第 1 学期
2010 年12 月30 日
设计任务书
指导教师（签章）：
年月日
摘要：
编译原理课程是高校计算机类专业的重要基础和骨干课程，对计算机专业的学生的重要性与高等数学对理科学生的重要性几乎可以相提并论。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。在编译系统中，词法分析阶段是整个编译系统的基础。对于单词的识别，有穷自动机FA也叫有限自动机，是一种十分有效的工具，机器识别的语言是正规语言。有穷自动机由其映射f是否为单值而分为确定的有穷自动机DFA和非确定的有穷自动机NFA，唯一区别是它们的转移函数不同。DFA对每一个可能的输入只有一个状态的转移，NFA对每一个可能的输入可以有多个状态转移，接受到输入时从这多个状态转移中非确定地选择一个。NFA 可以转化为DFA，确定化后的自动机可以最小化。
关键词：NFA；DFA；确定化；最小化；正规语言；有穷自动机；
目录
1课题综述 (1)
1.1课题来源 (1)
1.2课题意义 (1)
1.3预期的目标 (1)
1.4面对的问题 (1)
1.5需解决的关键技术 (1)
2 系统分析 (2)
2.1涉及的知识基础 (2)
2.2总体方案 (3)
2.3解决问题的基本思路 (3)
2.4功能模块图 (4)
3 系统设计 (4)
3.1实现原理 (4)
3.2实现方法 (5)
3.3详细流程图 (6)
4代码编写 (7)
4.1NFA到DFA的转化 (7)
5 程序调试 (8)
5.1调试步骤 (8)
5.2发现的问题 (9)
5.3解决的方法 (9)
6 运行与测试 (9)
总结 (12)
致谢 (13)
参考文献 (14)
1课题综述
1.1课题来源
由于很多计算机系统都配有多个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上看，一个编译程序就是一个语言翻译程序。语言翻译程序把源语言书写的程序翻译成目标语言的等价程序。经过编译程序的设计可以大大提高学生的编程能力。
编译程序的工作过程通常是词法分析、语法分析、语义分析、代码生成、代码优化。由于现在有很多词法分析程序工具都是基于有穷自动机的，而词法分析又是语法分析的基础，所以我们有必要进行有穷自动机的确定化和最小化。1.2课题意义
编译程序的这些过程的执行先后就构成了编译程序的逻辑结构。有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。正规表达式与自动机理论在词法构造乃至整个编译器构造过程中起着至关重要的作用，同时它们被广泛应用于计算机科学的各个领域，它们与计算机其它学科之间也有着很大的联系。
1.3预期的目标
(1) 正规式到DFA的转化；
(2) NFA到DFA的转化；
(3) DFA的最小化；
(4) 对输入字符的测试。
1.4面对的问题
(1) 调试程序时经常出现编译错误；
(2) 主界面的设计以及各种头文件的添加问题；
(3) NFA的构造算法。
1.5需解决的关键技术
程序以文件方式读取文法。读取TXT文件时会出现的错误是会跳出“提示
是否保存文件”的对话框。
2 系统分析
2.1涉及的知识基础
2.1.1 NFA的概念
一个不确定性有限状态自动机由以下部分所组成：M=(K, Σ , f, S , Z)
1. K是一个有穷集，它的每个元素称为一个状态；
2. Σ是一个有穷字母表，它的每个元素称为一个输入符号；
3. f 是一个从K*Σ→K到K的子集映像，即：K*Σ→2K，其中2K表示K的幂集；
4. S? K，是一个非空初态集；
5. Z? K，是一个终态集；
一个含有m个状态和n个输入符号的NFA可表示成一张状态转换图：这张图含有m个状态结点，每个结点可射出若干条箭弧与别的结点相连接，每条弧用Σ*中的一个串做标记，整个图至少含有一个初态结点以及若干个终态结点。
2.1.2 DFA的概念
一个确定性有限状态自动机由以下部分所组成：M=(K, Σ , f, S , Z)
1. K是一个有穷集，它的每个元素称为一个状态；
2. Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表；
3. f是转换函数，是K*Σ→K上得映像，即，如f(ki ,a)=kj(ki∈K, kj∈K)就意味着，当前状态为k，输入字符为a时，将转换到下一状态kj，我们把kj称作ki的一个后继状态；
4. S∈K，是唯一的一个状态；
5. Z? K,是一个终态集，终态也称可接受或结束状态。
2.1.3 DFA 的矩阵表示
一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。用双箭头“=>”标明初态；否则第一行即是初态，相应终态行在表的右端标以1，
非终态标以0。
2.1.4 NFA向DFA的转换
从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA 的每一个状态对应NFA的一组状态.DFA使用它的状态记录在NFA读入一个输入符号后可能达到的所有状态.
2.2总体方案
(1)如果读入正规式，则先将其转换为NFA，再将此NFA转换为DFA并最小化，输入测试字符串，输出测试结果。
(2)如果读入NFA，则将其转化为DFA并最小化，输入测试字符串，输出测试结果。
(3如果读入DFA,则直接将其最小化，输入测试字符串，输出测试结果。2.3解决问题的基本思路
(1)按照设计的要求和内容先画出流程图，通过使用switch语句来完成，对于头文件通过上网找了相应的资料正确地添加了程序中所需的头文件：用.h 的头文件，就不用using namespace std；
用没有.h 的头文件，就必须用using namespace std。
conio.h是字符屏幕操作头文件。
(2)通过type(char re)函数实现：如果遇到操作符：|和*，则return OP；遇到操作数则return OP_D；其他则return -1。
(3)NFA构造算法
a、单字母，一个状态到另一状态，它们之间的状态跃迁弧上标上该单字符。
b、空集，只有初始状态，无接受状态。
c、并运算，补充一初始状态，它到原来两个自动机的转移为空转移，其余不变。
d、连接运算，在第一个自动机的接受状态与第二个自动机的初态间引入空转移，并改第一个自动机的接受状态为非接受态。
e、星号运算，补充一初始状态，在原自动机的接受状态和初始状态间引入空移，新状态到原自动机的初始状态也是空转移。
2.4功能模块图
图2.1 功能模块图
3 系统设计
3.1实现原理
3.1.1 NFA转换成等价的DFA
将NFA转换成等价的DFA里，NFA到相应的DFA的构造的基本思想是让DFA的每一个状态对应NFA的一组状态。也就是说让DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态，在读入输入符号之后，DFA 处在a1a2......a n那样一个状态，该状态表示这个NFA的状态的一个子集T，T是从NFA的开始状态沿着某个标记为a1a2......a n可以达到的那些状态构成的。
对状态集合I的几个有关运算：
(1) 状态集合I的ε-闭包，表示为ε-closure(I)，定义为一状态集，是状态集
中的任何状态S经任意条ε弧而能够到达的状态的集合。
(2) 状态集合I的a弧转换，表示为move(I,a)定义为状态集合J，其中J是
所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。
3.1.2 NFA的确定化
一、子集法
1．先把DFA M’中的Q’和F’置为空集；
2．M’的开始状态q0’=[q0]，把[q0]置为未标记后加入到Q’中；
3．如果Q’中存在未标记的状态[q1,q2,…，qi]，则对每个a∈∑定义：δ’([q1,q2,…，qi],a)=[p1,p2,…,pi]当且仅当δ({q1,q2,…，qi},a)={p1,p2,…,pi}。如果[q1,q2,…，qi]不在Q’中，则把它置为为标记后加入到Q’中；如果p1,p2,…,pi 中至少有一个是M的终态，则同时把[p1,p2,…,pi]加入到F’中；然后给Q’中所有的状态都标记为止；
4．重复执行（3），直到不能向Q’中加入新状态，并且Q’中所有的状态都有标记为止；
5. 重新命名Q’中的状态，最后获得等价的DFA M’。
二、对含ε变迁的NFA的确定化：
1．置Q’, F’为空集；
2．令q0’=[ε_CLOSURE({q0})],并把[q0]置为未标记后加入到Q’中；
3．如果Q’中存在未标记状态[q1,q2,…,qi],则对每个a∈∑定义：d‘([q1,q2,…qi],a)=[p1,p2,…,pj]当且仅当d({q1,q2,…qi},a)={r1,r2,…,rk}, ε_CLOSURE({r1,r2,…,rk})= {p1,p2,…,pj}。如果[p1,p2,…,pj]不在Q’中，则把它置为未标记后加入到Q’中；如果p1,p2,…,pj中至少有一个是M的终态，则同时把[p1,p2,…,pj]加入到F’中；然后给Q’中的状态[q1,q2,…,qi]加上标记；
4．重复执行3，直到不能向Q’中加入新状态，并且Q’中所有的状态都有标记为止；
5．重新命名Q’中的状态，然后获得等价的DFA M’
3.2实现方法
(1)有穷自动机的确定化：使用ProcessNFAToDFA()函数来实现；
(2)确定的有穷自动机的最小化：使用函数MinimizeDFA()来实现，在该函数中还调用了CombineEquality()和RemoveFutility()函数。
(3)对生成串的测试：使用TestString()函数实现。
3.3详细流程图
图3.1 详细流程图
图3.2.1 NFA转换成DFA原理
4代码编写
4.1 NFA到DFA的转化
void REManage::ProcessNFAToDFA()
{
EDGE edge; //临时变量
vector
//vector
int over=-1; //标记已处理过的状态集
//由NFA得到初始状态集
Find_NULL_Closure(startNFA, DFAState,NFA_EDGE);
DFAStateGather.push_back(DFAState);
startDFA=DFAStateGather.size()-1; //得到初始状态
/*=========================add=========================*/ for(int m=0;m { if(find(DFAState.begin(),DFAState.end(),endNFA[m])!=DFAState.end()) break; } if(m endDFA.push_back(DFAStateGather.size()-1); else nonEndDFA.push_back(DFAStateGather.size()-1); /*=========================add=========================*/ /*****************Process NFA**********************/ queue tempState.push(DFAState); vector while(tempState.size()>0) { over++; edge.start=find(DFAStateGather.begin(),DFAStateGather.end(), tempState.front())-DFAStateGather.begin(); for(int i=0;i { //求队列首状态集在输入为input[i]时的结果状态 Move(tempState.front(),NFAInput[i],DFAState,NFA_EDGE); if(DFAState.size()<1) break; //填充DFA的边 edge.input=NFAInput[i]; iter=find(DFAStateGather.begin(),DFAStateGather.end(),DFAState); //如果所产生的状态集不在DFAStateGather中，则保存该状态集 if(iter==DFAStateGather.end()) { DFAStateGather.push_back(DFAState); for(int m=0;m { if(find(DFAState.begin(),DFAState.end(),endNFA[m])!=DFAState.end()) break; } if(m endDFA.push_back(DFAStateGather.size()-1); else nonEndDFA.push_back(DFAStateGather.size()-1); edge.end=DFAStateGather.size()-1; } else edge.end=iter-DFAStateGather.begin(); //保存边 DFA_EDGE.push_back(edge); if(DFAState!=tempState.front()&&edge.end>over) tempState.push(DFAState); } tempState.pop(); } 5 程序调试 5.1 调试步骤 (1) 编译后，点击运行键，出现运行窗口； (2) 4个选择项：1.输入正规式2.输入NFA 3.输入DFA 4.退出； (3) 输入2，按回车键后，出现NFA.txt记事本，输入NFA后并保存NFA.txt 记事本后关闭，在运行窗口按任意键进行处理，跳出Result.txt记事本，并在该记事本中输出了运行结果，运行窗口也出现2个选择项：1.测试生成串，2.完成。输入1，按回车则出现TestString.txt记事本，在该记事本中输入要测试的字符串保存TestString.txt记事本后关闭，回到运行窗口按任意键后，跳出TestResult.txt 记事本，该记事本输出了测试结果。运行窗口又出现那两个选项，输入2按回车后，出现第一次的4个选项； (4) 输入3，按回车键后，出现DFA.txt记事本，输入DFA后并保存DFA.txt 记事本后关闭，在运行窗口按任意键进行处理，跳出Result.txt记事本，并在该记事本中输出了运行结果，运行窗口也出现2个选择项：1.测试生成串，2.完成。输入1，按回车则出现TestString.txt记事本，在该记事本中输入要测试的字符串保存TestString.txt记事本后关闭，回到运行窗口按任意键后，跳出TestResult.txt 记事本，该记事本输出了测试结果。运行窗口又出现那两个选项，输入2按回车后，出现第一次的4个选项； (5) 输入4，则退出运行窗口结束程序运行。 5.2 发现的问题 (1) 使用头文件#include (2) 调用记事本失败。 5.3 解决的方法 (1) 添加using namespace std语句。 (2) 将使用到得记事本和编的程序代码同放在一个文件夹中。 (3) 把字符串分为三类：操作符,如|和*；操作数，如输入状态：字母或数字；其他。对每类字符串的处理返回不同的值。 6 运行与测试 (1)点击运行键后： 图6.1 初始界面 (2)NFA到最小化DFA的转化以及对生成串的测试： 图6.2 输入NFA 图6.3 转化结果 图6.4 输入测试串 图6.5测试结果 总结 编译原理是一门重要但难学的课程，因为编译原理是关于编写编译器的技术，编译器的编写一直被认为是十分困难的事情，所以这次拿到课程设计的课题就有些无从下手的感觉，感觉任务挺艰巨的。设计要求从理论上就不太好理解，不像以前的设计编写一个应用程序实现常见的功能，这次的课程设计注重各种算法的实现，比如用子集法实现有穷自动机的确定化、又能够分割法实现有穷自动机的化简。课题虽然感觉难懂了一些，但我想不管结果如何，只要自己努力，尽力了就行。自己始终相信“世上无难事，只怕有心人”。 由于课程设计只有短短的一周时间，时间有些紧迫，所以这在这短短的一周设计中，我们小组团结合作，互帮互助，大家都感觉这周过的非常充实，尽管累了点。同时通过这次课程设计我深深地感觉到团队的力量，深深体会到“团结就是力量”。当我们开始困惑无从下手时，我们你一句我一句的意见很快让我们找到了前进的方向。当自己遇到疑难时，和组员一起讨论解决了问题感觉非常欣慰，无助和孤独感也顿时消失。 通过这次课程设计给我另一个很大的体会是：流程图的重要性。说实话，每次不管是课程设计报告还是实习报告，我们最害怕做的就是画流程图，所以每次报告中能省则省。而这次发现根据系统需实现的功能和算法画出流程图后，就很清楚地知道我们的程序需要哪些模块，每个模块需要实现什么功能。所以在我们以后的学习中我们不能畏惧画流程图，我们要积极锻炼我们画流程图的能力，从而来帮助我们提高编程的能力。 每次的课程设计，和以前的相比，我发现了自己的一次又一次的进步，因为越到最后，越会发现自己的不足，就会想着怎样去改进，怎样去完善自己的系统，所以每学期的课程设计是很必要的，因为我在这些过程中都学到了很多知识。 致谢 一周的实习很快就过去了，在这一周中我相信大家都是静下心来认真做的，并且在确定选题后我们就都开始为课程设计做准备：有去图书馆查资料的，上网浏览相关资源的，请教老师和同学的。所以实习虽然只有短短的一周，可我们的收获却甚多。收获来源于压力，俗话说没压力就没动力。因此是这一周的任务压着我们去自主学习，自主解决学习时的困难。 这次实习来源于学校给我们的安排，所以在此感谢淮阴工学院给我们这样一个时间机会，提供给我们免费的机房，从而给我们的学习创造了良好的环境。当然学校也给我们提供了宝贵的资料地：图书馆。在那里我们可以方便地找到我们需要的学习资料。同时也要感谢我们的指导老师，在我们设计过程中遇到困难时，老师们都是细心耐心地辅导我们，帮我们越过一个个障碍，克服一个个困难，从而使我们建立起信心。当然在课后遇到难题时，我都会去向罗艳请教，她也总是会先放下自己的事来尽力帮助我，在此真的要好好感谢她，同时也很佩服她的钻研精神和解决难题的能力，要向她好好学习。在本次实习中，还要感谢同学们的帮助，对与细节上自己没有注意的问题给予了帮助，使我对问题有了更深一步的了解和认识，对所学知识加深了印象。与此同时，更加深刻地体会到团队精神的重要性，一个人的力量是永远不够的，只有同心协力，才能把系统做的更加完善。在这一过程中还有默默为我们服务的帮助者：参考文献的作者门，他们把他们的所学所知写成书，从而让我们在学习中少走了许多弯路。正是由于大家的帮助，才顺利完成了实习的任务。 参考文献 1王文豪.，编译原理课程设计指导书. 淮阴工学院. 计算机工程系，2010 2李劲华.编译原理与技术. 北京：北京邮电大学出版社，2007 3 郑阿奇，丁有和. Visual C++教程. 北京：机械工业出版社，2005 4张素琴，吕映芝，蒋维杜. 编译原理. 北京：清华大学出版社，2007 5蒋宗礼，姜守旭. 形式语言与自动机理论. 北京：清华大学出版社，2003 6 方辉云. C/C++/Visual c++ 程序设计. 北京：科学出版社，2005 7许福，张威. Visual C++ 程序设计技巧与实例. 北京：中国铁道出版社,2003 计算理论 字母表：一个有穷的符号集合。 字母表上的字符串是该字母表中的符号的有穷序列。 一个字符串的长度是它作为序列的长度。 连接反转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），另外，还有一个程序对这个盒子进行控制。这个装置就是根据程序的命令以及它的内部状态进行磁带的读写、移动。工作带被划分为大小相同的方格，每一格上可书写一个给定字母表上的符号。控制器可以在带上左右移动，它带有一个读写出一个你期待的结果。这一理论奠定了整个 现 代计算机的理论基础。“图灵机”更在电脑史上与“冯·诺依曼机”齐名，被永远载 编译原理课程设计设计题目：有限自动机的运行 年级：计062 姓名：黄思铭 学号： 200600401062 日期： 2010-5-18 指导教师: 陈望明 广西工学院计算机工程系 设计目的： 1、 理解有限自动机的作用 2、 利用转态图和状态表表示有限自动机 3、 以程序实现有限自动机的运行过程 设计内容：（注：题目详细要求） 利用状态表和有限自动机的运行原理编制程序，使得程序能够识别一个输入串是否为一个有效的符号串，具体可以选择下面之一：无符号定点实数、自然数、整数、十六进制数或其它自己定义的符号串。 一、分析原理 词法分析：就是从左至右逐个字符地对源程序进行扫描，产生单词序列，用以语法分析。 在这里，我们先把文法转换成有穷自动机，然后构造出状态表，再由状态表构造出程序。 二、分析的算法 将G[<无符号数>]文法转换成有穷自动机： 构造状态矩阵；将有穷自动机的状S 1 S 2 ……S n 及输入的字a 1 a 2 ……a m 构成一个n*m 的矩阵。 再写一个程序，把状态矩阵用二维数组表示。程序通过输入的字符转换状态，从而可以识别出单词。 本程序的关键在状态表和缓冲区的运用。首先定义了一个布尔型函数ReadALine把输入的字符串送到缓冲区中；然后定义了布尔型函数Run 和Getchar实现对输入字符串的正确性判断，更改Run函数可以改变程序功能：如可将状态表改变成识别“偶数”的有限自动机的状态表。 三、程序流程图 四、课程设计出现的问题及解决的方法 刚开始写该程序时，虽然感觉个人的编程能力不错，但由于对编译原理的自动机的实现掌握不足，难以入手。但经过对问题的更深入了解和分析，再通过网上和书本的资料的细读，最后终于把程序编写出来了。程序中，碰到的最大的问题就是状态表的构造和如何把它转变为一个程序的实现过程。解决的方法当然是看书。 五、课程设计的体会 首先，题目给出的文法是有小毛病的。我个人认为<无符号数>不可能推出 . <十进制数> 或者 e <指数部分>的。在写这个程序是只要对编译原理书本词法分析分析很熟悉就可以比较容易地 写出该程序。通过这次课程设计，我对程序的编译和运行有了更进一步的了解，更好地掌握了编译原理的词法分析过程。 六、程序清单 #include 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 编译原理实验报告(二) E01214055 鲁庆河 1.实验名称： 不确定有穷状态自动机的确定化 2.实验目的： a)输入：非确定有穷状态自动机NFA b)输出：确定化的有穷状态自动机DFA 3.实验原理： a)NFA确定化为DFA 同一个字符串α可以由多条通路产生，而在实际应用中，作为描述控制过程的自动机，通常都是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA确定化为DFA。 b)NFA的确定化算法 ----- 子集法： ●若NFA的全部初态为S1，S2，…，S n，则令DFA的初态为： S＝[S1，S2，…，S n]，其中方括号用来表示若干个状态构成的某一状态。 ●设DFA的状态集K中有一状态为[S i，S i+1，…，S j]，若对某符号a∈∑，在NFA中有F（{ S i，S i+1，…，S j}，a） ={ S i’，S i+1’，…，S k’ },则令F（{ S i，S i+1，…，S j }，a）={ S i’，S i+1’，…，S k’ }为DFA的一个转换函数。 若[ S i’，S i+1’，…，S k‘ ]不在K中，则将其作为新的状态加入到K中。 ●重复第2步，直到K中不再有新的状态加入为止。 ●上面得到的所有状态构成DFA的状态集K，转换函数构成DFA的F，DFA的字母表仍然是NFA的字母表∑。 ●DFA中凡是含有NFA终态的状态都是DFA的终态。 c)closure（I）函数，move(I,a)函数的 假设I是NFA M状态集K的一个子集（即I∈K），则定义ε-closure（I）为： 1.若Q∈I，则Q∈ε-closure（I）； 2.若Q∈I，则从Q出发经过任意条ε弧而能到达的任何状态Q’，则Q’∈closure（I）。 3.状态集ε-closure（I）称为状态I的ε闭包。 假设NFA M＝( K,∑,F,S,Z ),若I∈K，a∈∑,则定义I a＝closure（J）,其中J是所有从closure（I）出发,经过一条a弧而到达的状态集。 NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态,将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加,而且可能出现一些等价状态，这时就需要简化。 4.实验思路：(数据结构及变量设计等) 编译原理实验报告 实验名称不确定有限状态自动机的确定化 实验时间 院系计算机科学与技术学院 班级 学号 姓名 1.试验目的 输入：非确定有限（穷）状态自动机。 输出：确定化的有限（穷）状态自动机 2.实验原理 一个确定的有限自动机（DFA）M可以定义为一个五元组，M＝（K，∑，F，S，Z），其中： （1）K是一个有穷非空集，集合中的每个元素称为一个状态； （2）∑是一个有穷字母表，∑中的每个元素称为一个输入符号； （3）F是一个从K×∑→K的单值转换函数，即F（R，a）＝Q，（R，Q∈K）表示当前状态为R，如果输入字符a，则转到状态Q，状态Q称为状态R的后继状态； （4）S∈K，是惟一的初态； （5）Z?K，是一个终态集。 由定义可见，确定有限自动机只有惟一的一个初态，但可以有多个终态，每个状态对字母表中的任一输入符号，最多只有一个后继状态。 对于DFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记符连接形成的字符串可为DFA M所接受。若M的初态结点同时又是终态结点，则称ε可为M所接受（或识别），DFA M所能接受的全部字符串（字）组成的集合记作L（M）。 一个不确定有限自动机（NFA）M可以定义为一个五元组，M＝（K，∑，F，S，Z），其中： （1）k是一个有穷非空集，集合中的每个元素称为一个状态； （2）∑是一个有穷字母表，∑中的每个元素称为一个输入符号； （3）F是一个从K×∑→K的子集的转换函数； （4）S?K，是一个非空的初态集； （5）Z?K，是一个终态集。 由定义可见，不确定有限自动机NFA与确定有限自动机DFA的主要区别是： （1）NFA的初始状态S为一个状态集，即允许有多个初始状态； （2）NFA中允许状态在某输出边上有相同的符号，即对同一个输入符号可以有多个后继状态。即DFA中的F是单值函数，而NFA中的F是多值函数。 因此，可以将确定有限自动机DFA看作是不确定有限自动机NFA的特例。和DFA一样，NFA也可以用矩阵和状态转换图来表示。 对于NFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记（ε除外）连接形成的字符串可为M所接受。NFA M所能接受的全部字符串（字）组成的集合记作L（M）。 由于DFA是NFA的特例，所以能被DFA所接受的符号串必能被NFA所接受。 设M 1和M 2 是同一个字母集∑上的有限自动机，若L（M 1 ）＝L（M 2 ），则称有 限自动机M 1和M 2 等价。 设计有穷自动机DFA实现C++简单程序的词法分析、扫描 前面两篇（一、二）只是直观地针对已明确给出的教学语言Tiny 源程序进行直接的词法分析（其实根本就称不上），不具有一般性（下面这个针对C++源程序的词法分析也相当单一，考虑面不足）。下面是我们的课程实验，需要结合课堂上学到的利用有限自动机DFA的方法来设计并分析源程序，提取出符合要求的Token。 根据老师给出的课件以及教材上的内容，扫描程序（词法分析）有下面3种实现方式，前面两篇（一、二）就是属于“直接编写”这一类，而本文则是“DFA”这一类。 1、按实验要求（如下），目前只拙劣地实现了第（1）和（5）点。 而且第（1）点中有两个要求未能完成： ★浮点数，因为包含单行、多行注释的DFA已经很混乱了，这部分暂时先不实现，考虑将来用“表驱动法”（即状态转换表）来实现。 ★注释，与教材类似不打印单行和多行注释，因此代码实现中少了处理注释的内容。 实验中用到的C++源程序与要求如下图： 2、对实验要求中的“样例程序”稍微修改了一下。 ★头文件 #include 龙源期刊网 https://www.doczj.com/doc/de11664721.html, 有限状态自动机模型 作者：刘威 来源：《新课程·教师》2015年第09期 当我们用计算机进行问题的求解时，首先需要用适当的数据进行问题表示，然后再设计 相应的算法对这些数据进行变换处理来获得问题的求解结果。因此，对问题进行建模和形式化表示，然后进行处理是进行计算机求解的基本途径。数理逻辑、自动机理论给出了如何描述一些基本问题以及如何建立问题的抽象表示，并通过对这些抽象化的表示的性质和它的变化方法进行研究。这些模型都是问题数学模型的典范，给计算机问题求解提供了坚实的理论基础，是计算机求解问题的重要方法和思想。 计算机科学与技术学科是以数学和电子学科为基础发展起来的，一方面研究计算机领域 中的一些普遍规律，描述计算的基本概念与模型，其重点是描述现象、解释规律。另一方面是包括计算机硬件、软件的计算机系统设计和实现的工程技术，简单地说，计算机科学与技术学科通过在计算机上建立模型并模拟物理过程来进行科学调查和研究，它系统地研究信息描述和变换算法，主要包括信息描述和变换算法的理论、分析、效率、实现和应用。 所有问题的描述都要以计算机能识别的语言来实现，计算机语言的文法描述提供了生成 语言的手段，但是，对于语言句子的识别来说，我们需要一些识别语言的模型，我们可以称这种模型为语言的识别模型。这种识别模型应该满足必要的约束条件，首先模型具有有穷个状态，不同的状态代表不同的意义。按照实际的需要，模型可以在不同的状态下完成特定语言的识别。我们可以将输入数据中出现的符号组成一个字符的列表。模型将输入数据作为线性表来进行处理和变换。模型有一个初始的状态，它是系统的开始状态，系统在这个状态下开始进行问题的求解。模型中还有一些状态表示它到目前为止所读入的字符构成的字符串是模型从开始状态引导到这种状态的所有字符串构成的语言就是模型所能识别的输入。我们可以将此模型对应成有穷状态自动机的物理模型，在处理问题的时候，它可以接受一个关于问题的输入数据，数据以字符串的形式提供，我们把这些输入数据划分成一系列的小部分，每个部分由若干字符组成，为了不让输入数据量影响该模型对问题的处理，我们约定，输入数据从开始输入时的时间点开始处理，输入状态可以是无穷的，这就是说，从输入第一部分数据开始，输入端可以有任意长度的输入序列。而且，模型有一个有穷状态控制器，该控制器的状态只有有穷多个，并且规定，模型的每一个动作分为三步，读入待输入的字符，根据当前的状态和读入的字符改变有穷控制器的状态，读下一部分输入数据。计算机的各个组成部分，既包括硬件系统也包括软件系统，都可以对其进行形式化的定义，计算机的硬件系统包括中央处理器、存储器、外部设备，可以形式化地用一个三元组来描述，对计算机个各个硬件部分进行管理的软件的功能也可以用形式化的方法来描述，例如，操作系统的各个功能模块、处理器管理、线程调度、文件系统、设备驱动程序、网络通信管理、虚拟内存管理等都可以进行形式化的定义。有穷状态机就是进行这种形式化定义的模型，有穷状态机是一个五元组，分别是描述状态的有穷非空集合，它称为有穷状态机的一个状态，输入符号表，所有输入有穷状态机的关于问题的描述都是这个符号表中的符号组成的字符串。状态转换函数，表示有穷状态自动机在某一状态读入字符，将 有限状态自动机的确定化 姓名：翟彦清学号：E10914127 一、实验目的 设计并实现将 NFA确定化为DFA的子集构造算法，从而更好地理解有限自动机之间的等价性，掌握词法分析器自动产生器的构造技术。该算法也是构造LR分析器的基础。 输入：非确定有限(穷)状态自动机。 输出：确定化的有限(穷)状态自动机二、实验原理 一个确定的有限自动机(DFA M可以定义为一个五元组，M k( K,E, F, S, Z),其中： (1)K是一个有穷非空集，集合中的每个元素称为一个状态； (2)刀是一个有穷字母表，刀中的每个元素称为一个输入符号； (3)F是一个从K XE^ K的单值转换函数，即 F (R, a)= Q ( R, Q€ K)表示当前状态为R,如 果输入字符 a,则转到状态 Q,状态Q称为状态R的后继状态； (4)S€ K,是惟一的初态； (5)Z K,是一个终态集。 由定义可见,确定有限自动机只有惟一的一个初态,但可以有多个终态,每个状态对字母表中的任一输入符号,最多只有一个后继状态。 对于DFAM,若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记符连接形成的字符串可为DFAM所接受。若M的初态结点同时又是终态结点，则称&可为 M所接受(或识别)，DFA M所能接受的全部字符串(字)组成的集合记作 L(M)。 一个不确定有限自动机(NFA M可以定义为一个五元组，M=(K, E, F, S, Z), 其中：( 1) k 是一个有穷非空集,集合中的每个元素称为一个状态； (2)E是一个有穷字母表，E中的每个元素称为一个输入符号； (3)F是一个从K xE^ K的子集的转换函数； (4)S K,是一个非空的初态集； (5)Z K,是一个终态集。 由定义可见，不确定有限自动机 NFA与确定有限自动机DFA的主要区别是： (1)NFA的初始状态S为一个状态集，即允许有多个初始状态； (2)NFA中允许状态在某输出边上有相同的符号，即对同一个输入符号可以有多个后继状态。即DFA中的F是单值函数，而NFA中的F是多值函数。 因此，可以将确定有限自动机DFA看作是不确定有限自动机NFA的特例。和DFA—样，NFA也可以用矩阵和状态转换图来表示。 对于NFAM,若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记(&除外)连接形成的字符串可为M所接受。NFAM所 能接受的全部字符串(字)组成的集合记作 L(M)。 由于DFA是 NFA的特例，所以能被DFA所接受的符号串必能被NFA所接受。 设M和M是同一个字母集E上的有限自动机，若 L (M)= L (M),贝U称有限自动机M和M等价。 由以上定义可知，若两个自动机能够接受相同的语言，则称这两个自动机等价。DFA是 NFA的特例，因此对于每一个 NFAM总存在一个DFAM，使得L (M) 二L (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。 不确定有限状态自动机的确定化(NFA TO DFA) 不确定有限状态自动机的确定化（NFA TO DFA）2008-12-05 22:11 #include void eclouse(char c,string &he,edge b[]) { int k; for(k=0;k 实验二 无符号数的有穷自动机的实现 学时数：4 [实验内容]： 无符号数的有穷自动机的实现。利用状态表和有限自动机的运行原理编制程序，使得程序能够识别一个输入串是否为一个无符号定点实数。 [实验目的]： 1、理解有限自动机的作用；进一步理解自动机理论。 1、 用状态图和状态表表示有限自动机； 3、以程序实现有限自动机的运行过程；掌握文法转换成自动机的技术及有穷自动机实现的方法。 [实验要求]： 1、 设计要求：利用状态图或状态表相关理论，利用有限自动机理论。 2、 功能要求：输入一个单行无空格的字符串（以“#”号结束），如果该字符串是一个合法的输入，则显示“接受”，否则显示“不接受”。 3、 输入/输出示例（以无符号定点实数为例）：（1）输入：“3.14”，输出：“接受”；（2）输入：“3.1.4”，输出：“不接受”；（3）输入：“3ab ”，输出：“不接受”。 [实验提示]： 1、无符号数的BNF 描述如下： 0．<无符号数> → d <余留无符号数> | . <十进制数> | e <指数部分> 1．<余留无符号数> → d <余留无符号数> | . <十进制数> | e <指数部分> | ε 2．<十进制小数> → d <余留十进制小数> 3．<余留十进制小数> e <指数部分> | d <余留十进制小数> | ε 4．<指数部分> → d <余留整指数数> | + <整指数> | - <整指数> 5．<整指数> → d <余留整指数数> 6．<余留整指数数> → d <余留整指数数> | ε 2、将G[<无符号数>]文法转换成有穷自动机见图1。 图1 3、构造状态矩阵；将有穷自动机的状S 1 S 2 ……S n 及输入的字a 1 a 2 ……a m 构成一个 n*m 的矩阵。 1）根据状态矩阵设计出一个词法分析程序识别无符号数。 2）扫描无符号数，根据文法给出无符号数出错的位置。 [实验报告]： 1、写出无符号数词法分析的思想。 不确定的有限自动机转为确定的自动机 可以识别语言(a|b)*ab 的NFA 的 转换图如图示。 识别(a|b)*ab 的NFA 转换表：每个状态一行，每个输入符号和 （如果需要的话）各占一列，表的第i 行中符号a 的条目是一个状态集合（说得更实际一些，是状态集合的指针），这是NFA 在输入为a 时，状态i 所到达的状态集合。下图是对应的NFA 的转换表。 转换表的优点是可以快速访问给定状态和字符的状态集，缺点是，当输入字母表较大，并且大多数转换是空集时，会占用大量的空间。 转换 例子 识别(a|b)*ab的NFA 这里输入字母表是{a,b},令A={0,1,2,4,7},ε-closure(move(A,a)),在A中，只有2和7有a 转换，分别转到3和8，因此move(A,a)={3,8}，故ε-closure(move(A,a))= ε-closure({3,8}) ={1,2,3,4,6,7,8}，这是因为ε-closure（3）={1,2,3,4,6,7}，并且ε-closure（8）={8}，记 B={1,2,3,4,6,7,8}。于是，B ) (δ。 , A= a 从图中可看出，在A={0,1,2,4,7}中，只有状态4含b转换到5，故该DFA状态A的b转换到达ε-closure(move(A,b))= ε-closure（{5}）={1,2,4,5,6,7},记C={1,2,4,5,6,7}。 用新的没有标记的的集合B和C继续这个过程，最终会达到这样：所有的集合（即 DFA的所有状态）都已标记，因为10个状态的集合的不同子集只有102个，一个集合一旦标记就永远是标记的，所以到终止是肯定的。 对于状态B={1,2,3,4,6,7,8},只有2和7有有a转换，分别到3和8，ε-closure(move(B,a))= ε-closure({3,8})={1,2,3,4,6,7,8}. 同样，对状态B={1,2,3,4,6,7,8}，只有状态4和8有b转换，分别转到5和9，故 ε-closure(move(B,b))= ε-closure({5,9})={1,2,4,5,6,7,9},记D={1,2,4,5,6,7,9}. 对C={1,2,4,5,6,7}，有2和7有a转换，分别转到3和8，因此move(C,a)={3,8}，故ε-closure(move(C,a))= ε-closure({3,8})={1,2,3,4,6,7,8}=B. 对C={1,2,4,5,6,7},只有状态4含b转换到5, 故 一．填空题 1.语言类P 、PSPACE 、NP 、NPSPACE 、EXPTIME 之间的关系为 （EXPTIME NPSPACE PSPACE NP P ?=??）。 2.产生语言{12n 03n |n ≥0}的上下文无关文法是（00011|A A ε→）。 3.命题“利用递归定理，一个TM M 可以得到自己的描述 不确定有限状态自动机的确定化 【实验目的】 输入：非确定有限（穷）状态自动机。 输出：确定化的有限（穷）状态自动机。 【实验原理】 同一个字符串α可以由多条通路产生，而在实际应用中，作为描述控制过程的自动机，通常都是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA确定化为DFA。 NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能出现一些等价状态，这时就需要简化。 【程序代码】 #include string first;//边的初始结点 string change;//边的条件 string last;//边的终点 }; int N;//NFA的边数 vector 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.萨维奇定理计算机考博试题计算理论及答案
编译原理课程设计报告(无符号数的有穷自动机的实现)
计算机研究生《计算理论》复习题
不确定有穷状态自动机的确定化实验报告
不确定有限状态自动机的确定化
设计有穷自动机DFA实现C
有限状态自动机模型
有限状态自动机的确定化
湖南大学计算理论引论期末试题2006年秋本科试卷a-答案
不确定有限状态自动机的确定化(NFA TO DFA)
编译原理实验 无符号数的有穷自动机的实现
将不确定的有限自动机转换为确定的自动机
计算理论2013 12题
不确定有限状态自动机的确定化
计算理论知识点
相关主题
文本预览