“有限自动机和正规式”的版本间的差异
跳到导航
跳到搜索
Jihongchang（讨论 | 贡献） （→1）正规式） |
Jihongchang（讨论 | 贡献） |
||
| 第55行： | 第55行： | ||
|- | |- | ||
|a* | |a* | ||
| − | | | + | |由0个或多个a构成的符号串集合 |
|- | |- | ||
|<nowiki>(a|b)*</nowiki> | |<nowiki>(a|b)*</nowiki> | ||
2022年9月16日 (五) 07:58的版本
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* | 由0个或多个a构成的符号串集合 |
| (a|b)* | 所有由a和b构成的符号串集合 |
| (a|b)*abc | a和b构成的以abb结尾的符号串集合 |