编译原理第二周

李有才 13331130
编译原理

一、下列正则表达式定义了什么语言(用尽可能简短的自然语言描述)?

1. $((ε|a)b^*)^*$

   空串或所有由a，b组成的字符串

2. $(((ε|a)b)^*)^*$

   空串或由任意个b构成的字符串或由a后面紧跟任意多个b组成的字符串

3. $b^*(ab^*ab^*)^*$

   由偶数个a和任意个b组成的字符串

4. $c^*a(a|c)^*b(a|b|c)^*\ |\ c^*b(b|c)^*a(a|b|c)^*$

   由a，b， c组成的至少包含一个a和一个b的字符串

5. $(00|11)^*((01|10)(00|11)^*(01|10)(00|11)^*)^*$

   由偶数个0和偶数个1组成的字符串

二、按以下自然语言描述,写出正则表达式

1. 写出一个和第一题第五小题等价的且更简短的正则表达式

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

2. 利用第一题第五小题的结果,写出“由偶数个 0 和奇数个 1 构成的所有只含 0
   和 1 的字符串”

   $even\_0\_even\_1 \rightarrow (00|11)^*((01|10)(00|11)^*(01|10)(00|11)^*)^*$
   $even\_0\_odd\_1 \rightarrow (1|0(00|11)^*(01|10)even\_0\_even\_1$

三、非空数字串只由 0-9 这十个数字组成,回答:

1. 设 no_0-8 表示不含 0-8 的无重复数字的串,试用 no_0-8 表示 no_0-7(这里的无重复应该指的是相邻的数字不相同吧？否则递推不下去）

   $no_{0-7} \rightarrow (8|no_{0-8}8)|(no_{0-8}8)^*(no_{0-8}|ε)|no_{0-8}$

2. 试用 no_0-1 表示 no_0

   $no_{0} \rightarrow (1|no_{0-1}1)|(no_{0-1}1)^*(no_{0-1}|ε)|no_{0-1}$

3. 利用前两问的结果,试表示所有相邻数字都不相同的非空数字串.

   $no \rightarrow (0|no_{0}0)|(no_{0}0)^*(no_{0}|0)|no_{0}$