精品文档
32是非判断，对下面的陈述，正确的在陈述后的括号内写T，否则写F。1有穷自动机接受的语言是正则语言。（）2若r1和r2是Σ上的正规式，则r1r2也是。（）3设M是一个NFA，并且LM＝xyz，则M的状态数至少为4个。（）
4令Σ＝ab，则Σ上所有以b为首的字构成的正规集的正规式为bab。（）5对任何一个NFAM，都存在一个DFAM，使得LMLM。（）6对一个右线性文法G，必存在一个左线性文法G，使得LGLG，反之亦然。（）
答案1T2T3F4F5T6T
33描述下列各正规表达式所表示的语言。100102ε013010010140101010500110110001101100011
答案1以0开头并且以0结尾的，由0和1组成的符号串。2αα∈013由0和1组成的符号串，且从右边开始数第3位为0。4含3个1的由0和1组成的符号串。αα∈01，且α中含有3个15αα∈01α中0和1为偶数
34对于下列语言分别写出它们的正规表达式。1英文字母组成的所有符号串，要求符号串中顺序包含五个元音。2英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。3Σ01上的含偶数个1的所有串。4Σ01上的含奇数个1的所有串。5具有偶数个0和奇数个1的有0和1组成的符号串的全体。6不包含子串011的由0和1组成的符号串的全体。7由0和1组成的符号串把它看成二进制数，能被3整除的符号串的全体。
答案
1令Letter表示除这五个元音外的其它字母。
letterAletterEletterIletterOletterUletter
2ABZ
30101
401011
精品文档
f精品文档5分析设S是符合要求的串，S2k1k≥0）。则S→S10S21，S12kk0），S22kk≥0）。且S1是01上的串，含有奇数个0和奇数个1。S2是01上的串，含有偶数个0和偶数个1。考虑有一个自动机M1接受S1，那么自动机M1如下：
和LM1等价的正规表达式，即S1为：001101100011011001100011类似的考虑有一个自动机M2接受S2，那么自动机M2如下：
和LM2等价的正规表达式，即S2为：0011011000110110因此，S为：00110110001101100110001100011011000110110161100101ε7接受w的自动机如下：
对应的正规表达式：101010
36给出接受下列在字母表01上的语言的DFA。1所有以00结束的符号串的集合。2所有具有3个0的符号串的集合。
精品文档
f精品文档
答案aDFAM0，1，q0，q1，q2，q0，q2，δ其中δr