点此查看全部文字教程、视频教程、源代码

1. 概念

正规式与正规集是编译原理里面的概念。

正规式用来描述一类单词。

正规集是正规式描述的单词的集合。

注意此处的单词，其实就是一个符号串，可以是数字、字母或者其他字符的组合。

2. 方法

如果我们有两个字符a、b，那么有以下几种常用正规式写法。

正规式a，表示单一字符a，对应的正规集{a}。正规式a|b，表示单一字符a或者b，对应有2个元素的正规集{a,b}。正规式ab，表示由两个字符ab的元素，对应只有1个元素的正规集{ab}。正规式ab(a|b)，ab是确定的部分，然后再添加a或b，对应正规集{aba,abb}。正规式a*，*表示任意个，对应正规集{Φ,a,aa,aaa,...}。正规式(a|b)*，可以表示任意由a、b组成的串的集合，对应正规集{Φ,a,b,ab,aa,bb...}。

3. 刷题

题目：由a、b构造且仅包含偶数个a的串的集合，用正规式表示为()。

A:(a*a)*b*

B:(b*(ab*a)*)*

C:(a*(ba*)*b)*

D:(a|b)*(aa)*

解析：

对于A，如果第一个星号执行0次，第二个星号执行1次，第三个星号执行1次，结果为：ab，a不是偶数个，错误。

对于B，由于中间括号中两个aa必然成对出现，所以是偶数个a，正确！

对于C，第一个星号执行1次，第二、三个星号执行0次，第四个星号执行1次，结果为：ab，a不是偶数个，错误。

对于D，如果(a|b)执行为a，且第一个星号执行1次，第二个星号执行1次，结果为：aaa，a不是偶数个，错误。

如果觉得《[软考考点解析]软件设计师--正规式与正规集》对你有帮助，请点赞、收藏，并留下你的观点哦！