结构推理
用正规式描述下列正规集:
(1)C语言的十六进制整数;
(2)C语言的八进制整数;
(3)一般高级语言的标识符(以字母开始的字母数字串);
(4)以ex开始或以ex结束的所有小写字母构成的符号串;
(5)十进制的偶数。
【正确答案】该题考察对正规式,正规式的基本运算及其含义的理解,在此基础上描述各类单词符号的构成规则。
(1)C语言十六进制整数以0x或者0X开头,所以一般形式应该为(+|-|ε)(0x|0X)AA*,其中前面括号表示符号,可以有正号、负号,也可以省略(用£表示)默认是正数,A表示有资格出现在十六进制整数数位上的数字,AA*表示一位或者多位(一个或者多个数字的串)。下面进一步确定A的取值,A应该为(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f|A|B|C|D|E|F),所以整个正规式应该为:(+|-|ε)(0x|0X)(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f|A|B|C|D|E|F)(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f|A|B|C|D|E|F)*
也可以写成:
A:0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f|A|B|C|D|E|F
(+|-|ε)(0x|0X)AA*
从上面看出,在用正规式描述正规集时,如本例题所示,采用自顶向下,逐步求精的方法,先描述正规集的一般规律,再对细节进行描述。
(2)与(1)类似,C语言八进制整数以0开头,所以可以描述为:
A:0|1|2|3|4|5|6|7
(+|-|ε)0AA*
(3)一般高级语言的标识符描述为:(字母)(字母|数字)*
(4)以ex开始的小写字母符号串应该为ex(小写字母)*,以ex结尾的小写字母符号串应该为(小写字母)*ex,所以整个正规集描述为:ex(小写字母)*|(小写字母)*ex。
(5)十进制偶数个位为0、2、4、6、8,前面其他数位为0、1、2、3、4、5、6、7、8、9,因此整个正规集表示为(+|-|ε)A*B,其中A表示(0|1|2|3|4|5|6|7|8|9),B表示(0|2|4|6|8),所以表示整个正规集的正规式为:
(+|-|ε)(0|1|2|3|4|5|6|7|8|9)*(0|2|4|6|8)
【答案解析】