“有限自动机和正规式”的版本间的差异

来自姬鸿昌的知识库
跳到导航 跳到搜索
第47行： 第47行：
 
!正规式
 
!正规式
 
!正规集
 
!正规集
 +
!
 
|-
 
|-
 
|ab
 
|ab
 
|符号串ab构成的集合
 
|符号串ab构成的集合
 +
|a、b
 
|-
 
|-
 
|<nowiki>a|b</nowiki>
 
|<nowiki>a|b</nowiki>
 
|符号串a、b构成的集合
 
|符号串a、b构成的集合
 +
|
 
|-
 
|-
 
|a*
 
|a*
 
|由0个或多个a构成的符号串集合
 
|由0个或多个a构成的符号串集合
 +
|
 
|-
 
|-
 
|<nowiki>(a|b)*</nowiki>
 
|<nowiki>(a|b)*</nowiki>
 
|所有由a和b构成的符号串集合
 
|所有由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>
 
|<nowiki>(a|b)*abc</nowiki>
 
|a和b构成的以abb结尾的符号串集合
 
|a和b构成的以abb结尾的符号串集合
 +
|
 
|}
 
|}

2022年9月16日 (五) 08:03的版本

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结尾的符号串集合
取自“https://www.jihongchang.top/index.php?title=有限自动机和正规式&oldid=1882”