下载文档原格式
正规⽂法与正规式 3型⽂法也叫作正规⽂法，它对应于有限状态⾃动机，它是在2型⽂法的基础上满⾜：A->a|aB（右线性）或A->a|Ba（左线性）。
如果有A->a,A->aB,B->a,B->cB则符合3型⽂法的要求。
但是A->ab,A->aB,B->a,B->cB或A->a,A->Ba,B->a,B->cB则不符合3型⽂法的要求。
也就是说，不能够推导出两个终结符，⽽且左线性和右线性只能使⽤⼀种，不能够同时出现。
1.分别写出描述以下语⾔的正规⽂法和正规式：（1）L1={ab n a|n≥0}。
（2）L2={a m b n|n≥1,m ≥1}（3）L3={（ab）n|n≥1}答：（1） S → aA A → bA | a L1 = ab*a （2）S → aAA → aA | bB | b B → bB | b L2 = a*b* （3）S → aA A → bB B → aA | ε L3 = (ab)*2.将以下正规⽂法转换到正规式·Z→0A· A→0A|0B· B→1A|ε答：Z = 0A A = 0A + 0B B = 1A + ε A = 0A + 0(1A + ε) = 0A + 01A + 0 A = aA | b Z = 0(0 | 01)*0Z→U0|V1 U→Z1|1 V→Z0|0答：Z = U0 + V1 U = Z1 + 1 V = Z0 + 0 Z = (Z1+1)0 + V1 Z = (Z1+1)0 +(Z0+0)1 Z = Z10 + 10 +Z01 + 01 Z = Z(10+01)+10+01 Z = (10+01)*1001 Z = (10 | 01)*1001S→aA A→bA|aB|b B→aA答：S = aAA = bA + aB + b B = aA A = bA + a(aA) +b = (b + aa)A +b S = (b | aa)*bI→l|Il|Id答： I = l + Il + Id I = l + I(l +d) I = l(l | d)*。
正规文法与有限自动机的相互转换二零一五年十二月二十七日目录摘要 (1)关键词 (1)1课题综述 (1)1.1目的 (1)1.2设计内容 (1)1.3设计原则 (1)2系统分析 (2)2.1正规式 (2)2.2有限自动机（有穷自动机） (2)2.3NFA向DFA的转换 (3)2.4正规式与有限自动机之间的转换 (3)3系统设计 (4)3.1从正规文法到有限自动机 (4)3.11正规文法到有限自动机的等价性证明 (4)3.12 正规文法到有限自动机的构造方法 (5)3.2从有限自动机到正规文法 (6)3.21 有限自动机到正规文法的等价性证明 (6)3.22 有限自动机到正规文法的构造方法 (7)4 运行与测试 (7)总结 (9)参考文献 (9)附录 (10)摘要：正规文法包括左线性文法和右线性文法。
由于正规文法和正规表达式在描述语言的能力上是等价的，而正规表达式和有限自动机在描述语言的能力上也是等价的，因此，正规文法和有限自动机之间也存在着等价性。
通常，对于正规文法G和有限自动机M，G所定义的语言记作L(G)，M所能识别的语言记作L(M)，如果有L(G)=L(M),则称G和M是等价的。
关键词：正规文法；有限自动机；等价性；构造方法1课题综述1.1目的1.理解正规文法与有限自动机（FA）的本质联系；2.掌握正规文法与有限自动机之间相互转化的算法原理；3.学会使用Visual C++等编程工具实现正规文法与有限自动机之间的相互转化；1.2设计内容使用Visual C++/Visual C#等工具，设计软件MySoft_3，可以实现以下功能：1.根据用户输入的文本文件（*.txt）的名称，打开文件，并从文件中获取文法的产生式、非终结符、终结符、开始符等基本信息；2.判断该文法是否为正规文法，若是，则将其转化为有限自动机；3.根据用户输入的文本文件（*.txt）的名称，打开文件，并从文件中获取有限自动机的状态集、字母表、初态、终态集、转移函数等基本信息；4.判断该自动机是否合法，若合法，则将其转化为正规文法；1.3设计原则正规文法与有穷自动机有着特殊的关系，采用下面的规则可从正规文法G直接构造一个有穷自动机NFA M；使得L(M)=L(G)：（1）M的字母表与G的终结符相同；（2）为G中的每一个非终结符生成M的一个状态，G的开始符S是开始状态；（3）增加一个新状态Z，作为NFA的终态；（4）对G中的形如A->tB的规则（其中T为终结符或，A为非终结符的产生式），构造M的一个转换函数f(A,t)=B；（5）对G中形如A->t的产生式，构造M的一个转换函数f（A，t）=Z。
软件设计师-程序语言基础知识(二)1(总分：34.00，做题时间：90分钟)一、综合知识试题(总题数：34，分数：34.00)1.以下关于变量和常量的叙述中，错误的是______。
A．变量的取值在程序运行过程中可以改变，常量则不行B．变量具有类型属性，常量则没有C．变量具有对应的存储单元，常量则没有D．可以对变量赋值，不能对常量赋值（分数：1.00）A.B. √C.D.解析：[解析] 常量是在程序运行过程中值不可以改变的数据。
根据数组的组织类型的不同，可以将数据分为基本数据类型、用户自定义数据类型、构造类型等。
变量具有类型属性，常量也有数据类型，如整数常量、字符串常量等。
2.编译程序分析源程序的阶段依次是______。
A．词法分析、语法分析、语义分析 B．语法分析、词法分析、语义分析C．语义分析、语法分析、词法分析 D．语义分析、词法分析、语法分析（分数：1.00）A. √B.C.D.解析：[解析] 词法分析是编译过程的第一个阶段，其任务是对源程序从前到后(从左到右)逐个字符地扫描，从中识别出一个个“单词”符号。
语法分析的任务是在词法分析的基础上，根据语言的语法规则将单词符号序列分解成各类语法单位。
如果源程序中没有语法错误，语法分析后就能正确地构造其语法树。
语义分析阶段的主要任务是检查源程序是否包含静态语义错误，并收集类型信息供后面的代码生成阶段使用。
3.下图所示的有限自动机中，0是初始状态，3是终止状态，该自动机可以识别______。
A．abab B．aaaa C．bbbb D．abba（分数：1.00）A.B. √C.D.解析：[解析] 从初始状态到终止状态有多条路径。
在状态0输入a到达状态2；在状态2可输入a或b，输入a到达状态1，输入b到达状态3；状态3下输入a还回到状态3；在状态1可输入a或b，输入a到达状态3，输入b到达状态2。
4.下图所示为两个有限自动机M1和M2(A是初态、C是终态)，______。
第2章程序语⾔基础知识（⽂法-正规式-有限⾃动机第2章程序语⾔基础知识编译原理2-781.⽂法认识终结符（不可拆分，⼩写）和⾮终结符（可拆分，⼤写）终结符不可单独置前eg:有⽂法G2[S]为：S->ApS->BqA->aA->cAB->bB->dB则：S为开始符，S,A,B为⾮终结符，p,q,a,b,c,d为终结符⽂法的类型0型⽂法（限制最少的⼀个）设G=（V N，V T ，P，S），如果它的每个产⽣式α---→β是这样结构：α属于（V N并V T）*（闭包）且⾄少含有⼀个⾮终结符，⽽β属于（V N并V T）*，则G是⼀个0型⽂法。
0型⽂法也称短语⽂法。
⼀个⾮常重要的理论结果是：0型⽂法的能⼒相当于图灵机（Turing）。
或者说，任何0型语⾔都是递归可枚举的，反之，递归可枚举集必定是⼀个0型语⾔。
1型⽂法也叫上下⽂有关⽂法，此⽂发对应于线性有界⾃动机。
它是在0型⽂法的基础上每⼀个α---→β,都有|β|>=|α|。
这⾥的|α|表⽰的是α的长度。
注意：虽然要求|β|>=|α|，但有⼀特例：α---->空也满⾜1型⽂法。
如有A->Ba 则|β|=2，|α|=1 符合1型⽂法要求。
反之，如aA->a,则不符合1型⽂法要求。
2型⽂法也叫上下⽂⽆关⽂法，它对应于下推⾃动机。
2型⽂法是在1型⽂法的基础上，再满⾜每⼀个α-→β都有α是⾮终结符。
如A->Ba,符合2型⽂法要求。
如Ab->Bab虽然符合1型⽂法要求，但是不符合2型⽂法要求，其中α=Ab,Ab 不是⼀个⾮终结符。
3型⽂法也叫正规⽂法，它对应于有限状态⾃动机。
它是在2型⽂法满⾜的基础上满⾜：A->α|αB（右线性）或A->α|Bα(左线性)如：A->a,A->aB,B->a,B->cB,则符合3型⽂法的要求。
但如果推导为：A->ab,A->aB,B->a,B->cB或：A->a,A->Ba,B->a,B->cB则不符合3型⽂法的要求。
正规式与有限自动机正规式与有限自动机之间的转换1）有限自动机转换为正规式对于S上的NFAA/,可以构造一个S上的正规式/?,使得切⑷。
拓广状态转换图的概念，令每条弧可用一个正规式作标记。
为S上的NFA Af构造相应的正规式及，分为如下两步。
（1）在M的状态转换图中加两个节点，一个x节点，一个y节点。
从x节点到NFAM 的初始状态节点引一条弧并用e标记，从NFAM的所有终态节点到y节点引一条弧并用e 标记。
形成一个与A/等价的MS AT只有一个初态jc和一个终态少。
（2）按下面的方法逐步消去中除x和；；的所有节点。
在消除节点的过程中，用正规式来标记弧，最后节点jc和；；之间弧上的标记就是所求的正规式。
消除节点的规则如图2-12所示。
2）正规式转换为有限自动机同样地，对于S上的每个正规式/?,可以构造一个S上的NFAAf,使得L（A0=Z（及）。
（1）对于正规式i,可用图>13所示的拓广状态图表示。
R o（1）通过对正规式/?进行分裂并加入新的节点，逐步把图转变成每条弧上的标记是E上的一个字符或e,转换规则如图2-14所示。
最后所得的图即为一个NFAM,JC为初态节点，少为终态节点。
显然，L（A0=I（及）。
【试题2-24】2011年11月真题48下图所示为一个有限自动机（其中，A是初态、C是终态），该自动机识别的语言可用正规式（48）表示。
A. (0|1)*01B. 1*0*10*1C. 1*(0)*01D. 1*(0|10)*1*分析：在正规式中，符号*表示重复若干次（包括0次），符号|表示“或”。
在状态A，可以输入1或0，如果输入1还可以回到状态A，如果输入0直接到达状态B；在状态B，可以输入0或1，如果输入0则还回到状态B，而输入1，则进入到状态C；在状态C可以输入0或1，输入0到达状态B，输入1到达状态A，但由于C是终态，自动机可识别的语言是由0、1构成的字符串的集合，但该集合必须以01结果，因此选项A正确。
第2章程序语言基础知识
编译原理2-78
1.文法
认识终结符（不可拆分，小写）和非终结符（可拆分，大写）
终结符不可单独置前
eg:有文法G2[S]为：
S->Ap
S->Bq
A->a
A->cA
B->b
B->dB
则：S为开始符，S,A,B为非终结符，p,q,a,b,c,d为终结符
文法的类型
0型文法（限制最少的一个）
设G=（V N，V T ，P，S），如果它的每个产生式α---→β是这样结构：
α属于（V N并V T）*（闭包）且至少含有一个非终结符，而β属于（V N并V T）*，则G是一个0型文法。
0型文法也称短语文法。
一个非常重要的理论结果是：0型文法的能力相当于图灵机（Turing）。
或者说，任何0型语言都是递归可枚举的，反之，递归可枚举集必定是一个0型语言。
1型文法
也叫上下文有关文法，此文发对应于线性有界自动机。
它是在0型文法的基础上每一个α---→β,都有|β|>=|α|。
这里的|α|表示的是α的长度。
注意：虽然要求|β|>=|α|，但有一特例：α---->空也满足1型文法。
如有A->Ba 则|β|=2，|α|=1 符合1型文法要求。
反之，如aA->a,则不符合1型文法要求。
2型文法
也叫上下文无关文法，它对应于下推自动机。
2型文法是在1型文法的基础上，再满足每一个α-→β
都有α是非终结符。
如A->Ba,符合2型文法要求。
如Ab->Bab虽然符合1型文法要求，但是不符合2型文法要求，其中α=Ab,Ab不是一个非终结符。
3型文法
也叫正规文法，它对应于有限状态自动机。
它是在2型文法满足的基础上满足：
A->α|αB（右线性）或A->α|Bα(左线性)
如：A->a,A->aB,B->a,B->cB,则符合3型文法的要求。
但如果推导为：A->ab,A->aB,B->a,B->cB
或：A->a,A->Ba,B->a,B->cB则不符合3型文法的要求。
如何判断一个串是否为某个文法的句型
Eg1：已知文法G[S ] : S->A0|B1 ,A->S1|1 ,B->S0|0 :该文法属于桥穆斯定义的___( 1 )___文法，它不能产生串___( 2 )__。
(1) A.0型 B.1型 C.2型 D.3型
(2) A.0011 B.1010 C.1001 D.0101
S->A0 S->B1
A->S1 A-> 1
B->S0 B->0
S->A0->S10->A010->1010
S->A0->S10->B110->0110
S->B1->S01->A001->1001
S->B1->S01->B101->0101
S
/ \
A 0
/ \
S 1
/ \
A 0
/ \
1
2.正规式
正规式与正规文法之间的转换
文法G[S] :S->xSx|y 所描述的语言是_______(n>=0)
A.(xyx)n
B. xyx n
C.xy n x
D. x n yx n
Eg:
对于以下编号为1，2，3的正规式，正确的说法是____正则式2,3等价______。
1.（aa*|ab）* b
2.(a|b) * b
3.((a|b) * |aa) * b
(a|b) * 与((a|b) * |aa) *都是a与b的任意组合。
Eg:
语言L={a m b m|m>=0,n>=1}的正规表达式是_______。
A.a*bb*
B.aa*bb*
C.aa*b*
D.a*b*
L=am(m>=0)的正规表达式是a*
3.有限自动机（有穷自动机）
NFA（不确定的有限自动机）与DFA（确定的有限自动机）
确定的有限自动机（DFA）的定义：
一个确定的有限状态自动机M（记做DFAM）是个五元组： M={S，∑，f，S0，Z}
其中：
1）S是一个有限状态集合
2）∑是一个字母表，它的每个元素称为一个输入字符
3）f是一个从S*∑值S的单值部分映射。
f (s，a)=s` 意味着：当现行状态为s，输入字符为a时，将转换到下一个状态s`。
我们称s` 为s 的
一个后继状态。
4）S0属于S，是唯一的初态
5）Z 包含于S，是一个终态集
Eg:
有限状态自动机可以形象地用状态转换图来表示，设有限状态自动机：
DFA=（{S，A，B，C，f }，{1,0}，F，S，{ f }），其中：
K（S，0）=B，K（S，1）=A，K（A，0）= f ，K(A ，1)=C，K(B，0)=C，
K（B，1）=f，K(C，0)=f ，K(C，1)=f ，画出对应的状态转换图：
不确定的有限自动机（NFA）的定义：
S0包含于S，是一个非空初态集
Z 包含于S，是一个终态集
NFA转化为DFA
Eg：
已知一不确定的有限自动机（NFA）如图所示，采用自己发将其确定为DFA的过程如下所示：
状态集T1中不包括编号为______（1）_____的状态，状态集T2中的成员有
______（2）_____，状态集T3等于______（3）_____。
1）A. 2 B. 4 C. 3 D. 5
2）A. 1，3，4，5，Z B. 2，3 C. 6 D.4，5，Z
4个中只有T1 ，{4，5，Z}可在下排，股T2={4，5，Z}
.将输入数得出结果不同的非空集合编号
1
2 3
3 4
正规式与有限自动机之间的转化
Eg：
把下面的正规式转换成有限自动机：表示符，a(字母)，d(数字) ( _ | a ) ( _ | a | d )
*
Eg:
某一非确定性有限自动机（NFA）的状态转换图如图所示，该NFA等价的正规式是______。
q0即是初态，也是终态
A．0* | ( 0 | 1 ) 0 B．（0|10）* C. 0*((0|1)0)*
D．0*(10)*
C、D 0100表现不出
4.语法推导树
一棵语法树应具有一下特征：
1）每个节点都有一个标记，此标记是V的一个符号V终结符Vt与非终结符Vn 的集合
2）根的标记是S
3）若一节点n至少有一个它自己除外的子孙，并且有标记A，则A肯定在Vn中4）如果节点n的直接子孙，从左到右的次序是节点n1,n2,….nk, 其标记分别是：A1，A2，..Ak,那么
A->A1A2..Ak,一定是P中的一个产生式。
Eg:
文法G=（{a，b}，{S，A}，S，P），其中S->aAS|a A->SbA|SS|ba
请构造句型aabAa的推导树。
S->aAS
S->a
A->SbA
A->SS
A->ba
短语、简单短语、句柄
令G是一文法，S是文法的开始符号，abc是文法G的一个句型。
如果有
，则称b是句型abc相对于非终结符A的短语。
特别是，如有A=>b，则称b 是句型abc相对于规则
A->b的直接短语（也称简单短语）。
一个句型的最左直接短语成为该句型的句柄。
Eg:
一个上下文无关文法生成句子abbaa的推导树如图所示。
5.算符优先***
难（可放弃）。
