正则表达式6到12位字母和数字_0到100正则表达式「建议收藏」

正则表达式6到12位字母和数字_0到100正则表达式「建议收藏」复习有限自动机分为两种:不确定的有限自动机(NFA)和确定的有限自动机(DFA)

复习

有限自动机分为两种:不确定的有限自动机(NFA)和确定的有限自动机(DFA)。我们分别用一个五元组表示。不确定的有限自动机:

  1. 有限状态集合S.
  2. 输入符号集合Σ
  3. 转换函数move:Sx(Σ∪(ε)->p(s))
  4. 状态S0是唯一的开始状态
  5. F包含于S是接受状态集合

确定的有限状态自动机1、2、4、5与NFA一样。转换函数move:Sx(Σ)->p(s),两者区别在于:有限自动机任何状态下没有ε转换,一个符号标记离开同一状态只有一条边

MYT算法

规则如下:

1.st

不添加空串,添加一个状态不添加空串,添加一个节点
2.一个字符(可以是空字符)
添加一条边,一个状态
添加一条边,一个状态
3.s|t

添加四个空串,四个状态添加四个空串,四条边

4.s*添加四个空串、四条边、四个状态(图下面一条i到f的边被遮住了)添加四个空串四条边两个状态(图下面一条i到f的边被遮住了)

一些似乎不是很重要的性质:

  • N(s)的状态数最多是s的状态数的两倍。
  • N(s)的每一个状态有一个用Σ里的符号标记的指向其他节点的转换或者最多两个指向其他节点的ε转换。

MYT算法的分析

为了应付考试,我们可以说会手工建NFA就行。比较迅速的方法就是从嵌套多的地方入手,像搭积木一样搭建NFA。为了避免出错,建议时刻记住每个转换的添加的边数和空串数。
MYT算法的好处在于,任何字符串都能通过这个算法转换成NFA,它是沿着正则表达式的语法分析树自底向上递归处理的。不过我们可以发现,要添加的空串和边实在是太多了,这为我们后面继续转换成DFA带来了很多不少麻烦,因此这也是有代价的。

自顶向下算法

规则如下:
在这里插入图片描述
1.AB
添加一个状态
2.A|B
添加两条边,不添加空串和状态
3.A*
添加三条边、两个空串

自顶向下算法分析

和MYT算法同样,分块构建NFA。区别在于比较简单,引入空串、新边较少,之后化简就会容易。

今天的文章正则表达式6到12位字母和数字_0到100正则表达式「建议收藏」分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/86808.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注