查看“有限自动机和正规式”的源代码

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

=== 1）正规式 ===
正规式：由正规文法转换而来，通常正规文法等价于正规式。
{| class="wikitable"
!
!文法产生式
!正规式
|-
!规则1
|A→xB,B→y
|A=xy
|-
!规则2
|<nowiki>A→xA|y</nowiki>
|A=x*y
|-
!规则3
|A→x,A→y
|<nowiki>A=x|y</nowiki>
|}
说明：

规则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次；



正规集：正规文法产生的集合是语言基本字符集上的字符串的一个子集。
{| class="wikitable"
|+
!正规式
!正规集
!
|-
|ab
|符号串ab构成的集合
|a、b
|-
|<nowiki>a|b</nowiki>
|符号串a、b构成的集合
|
|-
|a*
|由0个或多个a构成的符号串集合
|
|-
|<nowiki>(a|b)*</nowiki>
|所有由a和b构成的符号串集合
|<nowiki>(a|b)(a|b) aa、ab、ba、bb</nowiki>
|-
|<nowiki>a(a|b)*</nowiki>
|a为首字符的a和b构成的符号串集合
|
|-
|<nowiki>(a|b)*abc</nowiki>
|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）有限自动机 ===
[[文件:有限自动机.png|无|缩略图|600x600像素]]下图所示的有限自动机中，s<sub>0</sub>是初始状态，s<sub>3</sub>为终止状态，该自动机不能识别（）。
[[文件:有限自动机 题1.png|无|缩略图|600x600像素]]
A、abab

B、aaaa

C、babb

D、abba