形式语言与自动机理论试题

形式语言与自动机理论试题

一、按要求完成下列填空

1. 给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集 （2x4'） 2. 设∑={0,1},请给出∑上的下列语言的文法 （2x5'） (1)所有包含子串01011的串

(2)所有既没有一对连续的0，也没有一对连续的1的串 1. 构造识别下列语言的DFA (2x6) (1) {x|x?{0，1}+且x以0开头以1结尾}

(2) {x|x?{0，1}

+

且x的第十个字符为1}

二、判断（正确的写T，错误的写F） 5x2'

1.设R1和R2是集合{a,b,c,d,e}上的二元关系，则

(R1?R2)R3?R1R3?R2R3

A 2.对于任一非空集合A，Φ?2

3.文法G：S A|AS A a|b|c|d|e|f|g 是RG 4.3型语言

2型语言

1型语言

0型语言

?? 5.s（rs+s）*r=rr*s（rr*s）*

三、设文法G的产生式集如下，试给出句子aaabbbccc的至少两个不同的推导（12分）。

S?aBC|aSBC aB?ab

bB→bb

?

CB→BC bC→bc cC→cc

四、判断语言{0n1n0n|n>=1}是否为RL，如果是，请构造出它的有穷描述(FA,RG或者RL）；如果不是，请证明你的结论（12分）

五、构造等价于下图所示DFA的正则表达式。(12分)

q0 S 1 0 q1 1 0 1 1 0

q3 q2 0 六、设M=（{q0,q1,q2}，{0,1}，{0,1，B}，{δ}，q0,B,{q2}）,其中δ的定义如下：

δ（q0，0）=（q0，0，R） δ（q0，1）=（q1，1，R） δ（q1，0）=（q1，0，R） δ（q1，B）=（q2，B，R）

请根据此定义，给出M处理字符串00001000,10000的过程中ID的变化。（10分）

七、根据给定的NFA，构造与之等价的DFA。（14分）

NFA M的状态转移函数如下表 状态说明 状态 0 开始状态 输入字符 1 {q0,q2} 2 {q0,q2} {q2} {q2,q1} { q0} q0 q1 q2 q3 {q0,q1} {q3,q0} ? ? {q3,q1} {q3 } 终止状态 {q3,q2}

本文来源：https://www.bwwdw.com/article/i7w2.html