1.有图灵机 M=(Q, ∑, Γ, δ,q0 , B , F) 接受语言{wtw│w∈{a,b}*}，按照下图说明其接受过程。（本题15分 ）
答：
2.简述《形式语言与自动机》课程的主要内容。 (本题10分)
答：语言的文法描述；RL（RG、 FA、RE、RL的性质 ）；CFL（CFG(CNF、GNF)、PDA、CFL的性质）；TM（基本TM断路器结构、构造技术、TM的修改）；CSL（CSG、LBA）。 3.简述《形式语言与自动机》课程的学习目的和基本要求。(本题10分)
答：
本专业人员4种基本的专业能力：计算思维能力、算法的设计与分析能力、程序设计和实现能力、计算机软硬件系统的认知、分析、设计与应用能力。其中计算思维能力包括：逻辑思维能力和抽象思维能力、构造模型对问题进行形式化描述、理解和处理形式模型。本课程应使学生掌握如下知识：正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。锻炼培养如下能力：形式化描述和抽象思维能力、了解和初步掌握“问题、形式化描述、自动化（计算机化）”这一最典型的计算机问题求解思路。 4.利用下图说明CFL泵引理的原理（物理意义）。（本题15分）
答：
（1） 用CNF作为CFL的描述工具。
（2） 对于任意的z∈L，当k是z的语法树的最大路长时，必 有|z|≤2k-1成立。仅当z的语法树为满二叉树时，才 有|z|=2k-1，其他时候均有|z|<2k-1。
（3） 取N=2|k|=2|k|+1-1 。
（4） 取z的语法树中的最长的一条路k，k中的非叶子结点 中必定有不同的结点标有相同的语法变量。
（5）S ⇒* uAy
⇒+ uvAxy
⇒+ uvwxy=z，
|vwx|≤2(|k|+1)-1=N
|vx|≥1
（6）对于任意非负整数i，
S ⇒* uAy
⇒+ uviAxiy
⇒+ uviwxiy。
5.按照文法的乔姆斯基体系，文法被分为几类？各有什么样的特点？（本题10分）
答：文法G=(V，T，P，S)，其中V为变量的非空有穷集，T为终极符的非空有穷集，V∩T=Φ，S∈V，为文法G的开始符号，P为产生式的非空有穷集合。P中的元素均具有形式αβ，其中α∈(V∪T)+，且α中至少有V中元素的一个出现，β∈(V∪T)*。 •0型文法：文法G=(V，T，P，S)叫做0型文法或短语结构文法。L(G)叫做0型语言。也可以叫做短语结构语言。识别系统为TM。
•1型文法：G是0型文法并且对于αβ∈P，均有|β|≥|α|成立，也叫上下文有关文法。L(G)叫做1型语言或者上下文有关语言。识别系统为LBA。中国管理
•2型文法：G是1型文法并且对于αβ∈P，均有|β|≥|α|，并且α∈V成立也叫上下文无关文法。L(G)叫做2型语言或者上下文无关语言。识别系统为PDA。
•3型文法：G是2型文法并且对于atp系统αβ∈P，αβ均具有形式Aw或AwB其中A，B∈V，w∈T+。L(G)叫做3型语言。识别系统为FA。
6.设文法G的产生式集如下，试给出句子000111222的至少两个不同的推导和至少两个不同的归约 (本题10分)
S→0BC|0SBC
0B→01
1B→11
CB→BC
1C→12
2C→22
推导一：
S=>0SBC=>00SBCBC=>000BCBCBC=>0001CBCBC=>0001BCCBC
=>00011CCBC=>00011CBCC=>00011BCCC=>000111CCC
=>0001112CC=>000111222
推导二：
S=>0SBC=>00SBCBC=>000BCBCBC=>000BBCCBC=>000BBCBCC=>000BBBCCC=>0001BBCCC=>00011BCCC=>000111CCC=>0001112CC=>00011122C=>000111222
归约一、归约二分别为推导一和推导二的逆过程
7.证明L={anbncn|n≥1}不是CFL（这个要配合泵引理看）
证明：利用反证法，假定L是CFL，N为泵引理所说的正整数，取z=aNbNcN∈L，并且有|aNbNcN|=3N。证不存在u，v，w，x，y z = uvwxy，使得对于i=0,1,2,3，...，
uviwxiy∈L。也就是说，对于u，v，w，x，y的任意取法，都能到一个特殊的i，使得uviwxiy∉L。 注意到影响uviwxiy是否为L的句子的因素是v和x，而u，w，y对uviwxiy来说是不变的，所以，证明将集中精力考察v和x的不同取法。再注意到|vwx|≤N，所以v，w和x并在一起不能同时有3种字符，也就是说，v和x不能同时分别为a和c组成的串。当然，也不可以取它们为形如ahbf（h，f≥1）的串，因为此时有uv2wx2y∉L恒成立。所以，还有如下两种情况需要讨论：
（1）v=ah，x=bf，h+f≥1。
此时有。当i≠1时，N+（i-1）h≠N和N+（i-1）f≠N中至少有一个成立，所以，当i≠1时，∉L。
（2）v=bh，x=cf，h+f≥1。
此时有当i≠1时N+（i-1）h≠N和N+（i-1）f≠N中至少有一个成立，所以，当i≠1时，∉L。
所以，L不是CFL。
8.将下列语法转换成CNF：（本题15分）
S→ASB|ε
A→0AS|0
B→S1S|A|11
a) 因为A和B都产生终结符号，所以S 也能产生终结符号，所以上述文法中没有无用符号。
b) 只有S 产生式中含有ε,所以将产生式右部中出现S 的，用ε替换后加到产生式中得到消除ε—产生式的文法为：
S -> ASB | AB A -> 0AS | 0A | 0 B -> S1S | 1S | S1 | 1 | A | 11
c) 单产生式是： B -> A.
因此，将A-产生式来代替A。结果是：S -> ASB | AB A -> 0AS | 0A | 0 和B -> S1S | 1S | S1 | 1 | 0AS | 0A | 0 | 11
d) 引入变量和产生式 C -> 0 和 D -> 1, 用C,D 来代换非终结符中的0 和1，得到结果：
S -> ASB | AB A -> CAS | CA | 0母神 B -> SDS | DS | SD | 1 | CAS | CA | 0 | DD C -> 0 D -> 1
最后，分别用E, F, 和 G 替换 SB,AS,DS 得到CNF 文法：
S -> AE | AB A -> CF | CA | 0
B -> SG | DS | SD | 1 | CF | CA | 0 | DD
C -> 0 D -> 1 E -> SB
F -> AS 节油剂G -> DS
9.设已有CNF： ①A→BC ②B→CA∣b ③C→AB∣a
将其变换为GNF。（本题15分）
解：⑴ 按其非终结符排列为A、B、C，A是低位，C是高位。
⑵ ∵ ①、②中，右部首符序号高于左部的非终结符,∴ 无需变换。
对③，需要变换，将①代入③得：C→BCB∣a ④
仍需变换，将②代入④得： C→CACB∣bCB∣a ⑤
⑶ 对上述变换后所得结果消直接左递归，对C→CACB∣bCB∣a变换为
C→bCB∣a∣bCBC’ ∣aC’ ⑥
C’→ACB∣ACBC’ ⑦
⑷ 回代:将C的生成式⑥回代入B的生成式②
B→CA∣b被变换为:B→bCBA∣aA∣bCBC’A∣aC’A∣b ⑧
将新的B生成式⑧回代入A的生成式①
A→BC 被变换为: A→bCBAC∣aAC∣bCBC’AC∣aC’AC∣bC⑨
再将新的A生成式⑨代入新引入的C’生成式⑦
C’→ACB∣ACBC’ 被变换为
C’→ bCBACCB∣aACCB∣bCBC’ACCB∣aC’ACCB∣bCCB∣ bCBACCBC’∣aACCBC’∣bCBC’ACCBC’∣aC’ACCBC’∣bCCBC’⑩
GNF中的产生式为： ⑨、⑧、⑥、⑩
10.正则语言有5种等价的描述模型：正则文法（RG）、确定的有穷状态自动机（DFA）、不确定的有穷状态自动机（NFA）、带空移动的有穷状态自动机（）、正则表达式（RE）。这5种等价模型的转换关系可以用下图表示：
整理这些不同模型间等价证明的思路。 (本题25分)
（1）
RG分为右线性文法和左线性文法。对于右线性文法，只需要采用模拟M的移动即可 ，
M的开始符号就是G的开始符号。而对于左线性文法，G用规约模拟M的移动：
新增加的符号Z为G的识别符号，也就是开始符号。
（2）
同上，分为右线性和左线性文法。对于右线性文法：
其中，G的开始符号为M的开始符号，新增的状态Z为M的终止状态。
对于左线性文法：增加Z为M的开始状态；对应形如的产生式，
定义；对应形如的产生式，
定义；G的开始符号为M的终止状态。
（3）
采用图上作业法：预处理、并弧、去状态、处 理：
（4）
由于NFA也是一个特殊的，则其转化可以参考钼电极
（5）
（6）：确定化
画图的解法：
11.设计PDA接受下列语言(注意:不要求为确定的) { 0m1n | m≤n };（本题15分）
设PDA M = ( Q,T,Г,δ,q0,Z0,F ),其中: Q = { q0,q1,qf } , T = { 0,1} ,
Г = { 0,1, Z0 } , F = { qf } ,
δ定义如下:
δ( q0, ε, Z0 ) = { ( q1, Z0 ) } , δ( q0,0, Z0 ) = { ( q0, 0Z0 ) } ,
δ( q0,0,0 ) = { ( q0, 00 ) } , δ( q0,1, Z0 ) = { ( qf,ε ) } ,
δ( q0,1, 0 ) = { ( q1,ε ) } , δ( q1,1, 0 ) = { ( q1,ε ) } ,
δ( q1,ε, Z0 ) = { ( qf,ε ) } δ( q1,1, Z0 ) = { ( qf,ε ) }
δ( qf,1, ε) = { ( qf,ε ) }
12.设计PDA接受下列语言：{ 0m1n0m | n和m任意}。 (本题10分)
0, 0/00 1, 0 / 0 0, 0/ε
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议