2008—2009第一学期形式语言与自动机考查试卷(A)
参考答案及评分标准
（院系：计算机科学技术 专业：计算机科学技术  年级：2006  考核形式：开卷）
（一）填空题（本大题共10个空，每空3分，总计30分）
(3) 设r=1*Φ，则L(r)=  Φ。
解答：步骤不清或中间步骤出错者可酌情扣去1分
(1)分析语言的特点：----------------------------------------------------------------------4
语言L可分为两个子语言，即L1={0n1n|n≥0}和L2={1n0n|n≥0}，且L=L1⋃L2。因此，为了构造产生L的文法，可分别先构造产生子语言L1和L2的文法，然后利用L= L1⋃L2两个文法合在一起即可。
(2)构造产生子语言L1={0n1n|n≥0}的文法G1：A→0A1|ε；-------------------------3
(3)构造产生子语言L2={1n0n|n≥0}的文法G2：B→1B0|ε；-------------------------3
(4)由于L=L1⋃L2，因此在G1和G2基础上引入产生式S→A|B，即得到产生
L的文法G：------------------------------------------------------------------------------4
S→A|B
A→0A1|ε
B→0B1|ε
四、等价转换题(本大题共1小题，每小题12分，总计12分)
将下列CFG G 等价转化为乔姆斯基范式（要求给出具体步骤）
G: S→ASA|aB
A→B|S
B→b|ε
解答：步骤不清或中间步骤出错时可酌情扣1分
(1) 化简：删除B→ε后得------------------------------------------------------------------2
S→ASA|aB|a
A→B|S|ε
B→b
(2) 化简：删除A→ε后得------------------------------------------------------------------2
S→ASA|aB|a|AS|SA|S
A→B|S
B→b
(3) 化简：删除S→S和A→B后得-------------------------------------------------------1
S→ASA|aB|a|AS|SA
A→b|S
B→b
(4) 化简：删除A→S后得-----------------------------------------------------------------1
S→ASA|aB|a|AS|SA
A→b| ASA|aB|a|AS|SA
B→b
(5) 转化为CNF：A→B1B2…B m和A→a-----------------------------------------------3
引入变量A a和产生式A a→a将(4)中产生式转化为
S→ASA|A a B|a|AS|SA
A→b| ASA|A a B|a|AS|SA
B→b
A a→a
正则匹配后缀后(6)转化为CNF：A→BC和A→a形式---------------------------------------------------3
引入变量A1和产生式A1→SA将(5)中产生式转化为
S→AA1|A a B|a|AS|SA
A→b| AA1|A a B|a|AS|SA
A1→SA
B→b
A a→a
五、构造题（本大题共1小题，每小题14分，总计14分）
构造确定型下推自动机 M，使得L(M)={0n1m0n|m≥0,n≥1}。
(要求给出具体构造步骤)
解答：(无步骤、中间步骤不清或出错时可酌情扣1-2分)
(1)分析----------------------------------------------------------------------------------------6
根据题意，L(M)={0n1m0n|m≥0,n≥1}={0n1m0n|m>0,n≥1}∪{0n1m0n|m=0,n≥1}
={0n1m0n|m>0,n≥1}∪{0n0n|n≥1}
设L1={0n1m0n|m>0,n≥1}，其构造思路如下：
∙当读到1之前为记录0的阶段：每读到一个0，就在栈中作一次相应的记载；
∙连续读入输入中1，直到0为止；由于L1句子中1的个数不限，所以不用作进一步的操作；
∙当读完1以后，再读到0时，就应该进入匹配阶段：用栈顶符号0逐一地与输入字符匹配，以检查1子串前后的0的个数是否相等。
设L2={0n0n|n≥1}={02n|n≥1}，显然L2的句子由偶数个0组成，其构造思路如下：∙M启动后假设输入中含有1的子串，并进入记载0的状态。当输入完全由0组成时，整个输入将先全部压入栈中；
∙因此，在处理L2时，只须将栈中的0成对弹出即可。
(注意：只考虑m>0的情况即L1的处理可得满分)
(2)识别L1的PDA构造----------------------------------------------------------------------8
∙取M=(Q, {0, 1}, {0, 1, Z0}, δ, q0, Z0, {q f})-----------------------------------------2 ∙状态设计或定义：Q=({q0, q1, q2, q3, q f, q t}---------------------------------------3  q0---开始状态：等待输入；当输入为0，将状态变为q1。
q1---记录状态：将输入存到栈中，状态不变，直到看到字符1；当输入为ε(即输入全部读完)没有发现字符1时，进入L2的处理。
q2---读1状态：当输入为1时，状态和栈顶符号不变，直到看到字符0。
q3---匹配状态：将输入与下推栈匹配，状态不变，退栈，直至栈空；

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。