有穷状态自动机
西北师范大学计算机科学与工程学院学生实验报告
班级技师(1)班姓名111
学号111111 专业计算机科
学与技术
课程名称编译原理课程类型实验
实验名称有穷状态自动机
实验目的：
1，准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，为词法分析程序的自动构造寻找特殊的方法和工具；
2，掌握了有穷状态自动转换机的概念；
3，掌握DFA的存储表示；
4，掌握DFA与正则文法的联系
实验原理：
1，一个确定的有穷状态自动机DFA是五元组（K,∑,M,S,F,）,其中，K是有穷非空的状态集合；
∑是有穷非空的输入字母表；
M是从K×∑到K的映象。如果M（R,T）=Q，则输入字符为T时，当前状态R 将转换到状态Q，Q成为下一当前状态；
S是开始状态；
F是非空的终止状态集合。
输入任意的正则文法，输出相应的有穷状态自动机
要求：识别有穷状态自动转换机是非确定的还是确定的，以相应的五元组形式输出。
实验代码如下：
实验源代码：
#include
using namespace std;
const int maxsize=10;
class DFA
{
private:
int M[maxsize][maxsize];
char Vn[maxsize],Vt[maxsize];
int VnNum,VtNum;
public:
DFA();
~DFA(){}
void print();
int move(char start,char s[]);
};
int DFA::move(char start,char s[])
{
char t[10];char next=start;
int left=0,right=0,i=0,j=0;
while(s[i]!='\0'){t[i]=s[i++];}
t[i]='\0';
while(t[0]!='\0')
{
left=0;right=0;
while(next!=Vn[left]){left++;}
while(t[0]!=Vt[right]){right++;}
if(M[left][right]!=-1&&left { next=Vn[M[left][right]]; cout<<"M("< else return 0; i=1; while(t[i]!='\0'){t[i-1]=t[i++];} t[i-1]='\0'; } return 1; } DFA::DFA() { char grammar[maxsize],n[maxsize],t[maxsize]; int rule,left,right,final; int i=0,j=0,k=0; cout<<"rule=";cin>>rule; cout<<"Vn ";cin>>n; cout<<"Vt ";cin>>t; cout<<"grammar"; Vn[0]='S'; j=0; while(n[j]!='\0')Vn[j+1]=n[j++];VnNum=j+1; while(t[i]!='\0')Vt[i]=t[i++];VtNum=i; for(i=0;i for(j=0;j<=VtNum;j++)M[i][j]=-1; i=0; while(i!=rule) { j=0;k=0; cin>>grammar; while(Vn[k]!=grammar[0])k++; final=k; while(grammar[j]!='\0')j++; if(j==2) { k=0; while(Vt[k]!=grammar[1])k++; left=0; right=k; } else { k=0;while(Vn[k]!=grammar[1])k++;left=k; k=0;while(Vt[k]!=grammar[2])k++;right=k; } M[left][right]=final; i++; } } void DFA::print() { int i=0,j=0; cout<<"DFA ({"; while(i!=VnNum){cout< while(j!=VtNum){cout< i=0; while(i!=VnNum) { j=0; while(j!=VtNum) { if(M[i][j]!=-1) { cout<<"M("< cout<<","< } j++; } i++; } cout<<"},{"< }; int main() { char t[10]; int i; cout<<"------------------------------------------------"< cin>>i;DFA s; while(i<=3) { //system("color 1e"); if(i==2)s.print(); if(i==3) {cout<<"输入串"; cin>>t;if(s.move('S',t))cout<<"字符串"< else cout<<"字符串"< cout<<"\n输入操作"; cin>>i; } system("pause"); } 实验结果： 实验总结： 通过本次实验，对有穷状态自动转换机有了更进一步的了解，掌握了其存储表示与正则文法的联系，并且通过对整个程序的阅读，知道了任意的正则文法如何以五元组的形式输出。能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合.通过本次实验，对有穷状态自动机的概念、其存储表示及其正则文法的联系，有了进一步的理解和认识，增强了动手能力和编程能力。 实验成绩 教师签名 计算理论 字母表：一个有穷的符号集合。 字母表上的字符串是该字母表中的符号的有穷序列。 一个字符串的长度是它作为序列的长度。 连接反转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.wendangku.net/doc/9712886682.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。 编译原理》无符号数的有穷自动机的实现(2007-12-04 15:07:27) package test; import java.io.*; public class Test1 { public static void main(String args[]){ InputStream input=System.in; InputStreamReader reader=new InputStreamReader(input); BufferedReader buf=new BufferedReader(reader); char num[]=new char[10]; String line=null; int i,flag; char ch1,ch2; while(true){ System.out.println("Please Input Number:"); try{ line=buf.readLine(); }catch(Exception e){ e.printStackTrace(); } if(line.equals("exit")){ System.out.println("退出"); break; } line=line+"$"; num=line.toCharArray(); i=0; flag=0; while(num[i]!='$'){ ch1=num[i]; ch2=num[i+1]; if(ch1>='0'&&ch1<='9'){ if((ch2>='0'&&ch2<='9') || ch2=='.' || ch2=='e' || ch2=='$'){ flag=1; } else flag=0; } if(ch1=='.'){ 不确定有限状态自动机的确定化(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、写出无符号数词法分析的思想。 一．填空题 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题
不确定有限状态自动机的确定化
计算理论知识点
- (1) 词法分析与有穷自动机.
- 编译原理词法分析__有穷自动机_算法_DFA化简
- (1) 词法分析与有穷自动机.
- 编译原理词法分析习题集带答案
- 第三章 词法分析
- 编译原理 第3章 词法分析与有穷自动机(第5-8讲)
- 第3章 词法分析 (编译原理 陈火旺)
- 有穷自动机与词法分析器
- 第3章 词法分析与有穷自动机(2)
- 有穷自动机的化简与确定化
- 第三章 词法分析与有穷自动机
- 《编译原理实践及应用》第3章词法分析 (2)
- 词法分析器的设计
- 编译原理词法分析__有穷自动机_DFA
- 第三章 词法分析和有穷自动机
- (1) 词法分析与有穷自动机.
- 编译原理习题课(词法分析)
- 2-张延亮—正规文法和有穷自动机的等价性
- 《编译原理》第3章 词法分析与有穷自动机
- 词法分析器设计与实现