有限自动机和正规式

https://www.bilibili.com/video/BV1hg411V7Bm?p=50

1）正规式

正规式：由正规文法转换而来，通常正规文法等价于正规式。

	文法产生式	正规式
规则1	A→xB,B→y	A=xy
规则2	A→xA|y	A=x*y
规则3	A→x,A→y	A=x|y

说明：

规则1不难理解，由A可以推导出xB，又由B可以推导出y，那么就可以根据前面两点推导出A=xy；

规则2：A=x*y中的“*”表示出现0次或任意次

A→xA|y表示——由A可以推导出xA，也可以由A推导出y

由A→y，则x出现0次；

又由A→xA和A→y，可以得到A→xy，则x出现了1次；

又由A→xA和A→xy，可以得到A→xxy，则x出现了2次；

...

又由A→x...A和A→xy，可以得到A→xx...y，则x出现了N次；

正规集：正规文法产生的集合是语言基本字符集上的字符串的一个子集。

正规式	正规集
ab	符号串ab构成的集合	a、b
a|b	符号串a、b构成的集合
a*	由0个或多个a构成的符号串集合
(a|b)*	所有由a和b构成的符号串集合	(a|b)(a|b) aa、ab、ba、bb
a(a|b)*	a为首字符的a和b构成的符号串集合
(a|b)*abc	a和b构成的以abb结尾的符号串集合

表示“以字符a开头且仅由字符a、b构成的所有字符串”的正规式为（）。

A、a*b*

B、(a|b)*a

C、a(a|b)* √

D、(ab)*

题解：

因为“*”表示出现0次或多次，

那么对于选项A，如果a出现0次就变成了以字符b开头；

对于选项B，也可以是以字符b开头，

选项D，会是ab、abab、ababab，所以选C

2）有限自动机

下图所示的有限自动机中，s₀是初始状态，s₃为终止状态，该自动机不能识别（）。

A、abab

B、aaaa

C、babb

D、abba