文档库

最新最全的文档下载
当前位置:文档库 > 编译原理平时作业-答案

编译原理平时作业-答案

平时作业

1 对于下列语言分别写出它们的正规表达式。

(1) 英文字母组成的所有符号串,要求符号串中顺序包含五个元音。

答:令Letter表示除这五个元音外的其它字母。

((letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter))*

(2) 英文字母组成的所有符号串,要求符号串中的字母依照词典顺序排列。答:A*B*....Z*

(3) Σ={0,1}上的含偶数个1的所有串。

答: (0|10*1)*

(4) Σ={0,1}上的含奇数个1的所有串。

答:(0|10*1)*1

(5) 具有偶数个0和奇数个1的有0和1组成的符号串的全体。

答:设S是符合要求的串,|S|=2k+1 (k≥0)。

则S→S10|S21,|S1|=2k (k>0),|S2|=2k (k≥0)。

且S1是{0,1}上的串,含有奇数个0和奇数个1。

S2是{0,1}上的串,含有偶数个0和偶数个1。

考虑有一个自动机M1接受S1,那么自动机M1如下:

编译原理平时作业-答案

和L(M1)等价的正规表达式,即S1为:

((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*

类似的考虑有一个自动机M2接受S2,那么自动机M2如下:

编译原理平时作业-答案

和L(M2)等价的正规表达式,即S2为:

((00|11)|(01|10)(00|11)*(01|10))*

因此,S为:

((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*0|

((00|11)|(01|10)(00|11)*(01|10))*1

(6) 不包含子串011的由0和1组成的符号串的全体。

答:1*|1*0(0|10)*(1|ε)

(7) 由0和1组成的符号串,把它看成二进制数,能被3整除的符号串的全体。答:假设w的自动机如下:

编译原理平时作业-答案

对应的正规表达式:(1(01*0)1|0)*

2 给出接受下列在字母表{0,1}上的语言的DFA。