正则到NFA的转换

作者: Yinvoker | 来源:发表于2019-04-12 09:24 被阅读2次

有穷自动机

作用:将输入的序列转换成一个状态图,方便之后的处理。通常被用在词法分析器中。
1)有穷自动机是一个识别器,对每个可能的的输入串简单的回答“是”或“否”。
2)有穷自动机分为两类:
a)不确定的有穷自动机(NFA)对其边上的标号没有任何限制。一个符号标记离开同一状态的多条变,并且空串ε也可以作为标号。
b)确定的有穷自动机(DFA)有且只有一条离开该状态,以该符号位标号的边。

不确定的有穷自动机

定义

NFA组成

正则式转NFA

这里看一个示例,下图为正则表达式 (a | b) * abb转换为NFA
不懂正则表达式的同学可以看这里

一个示例

然后我们来具体看看是正则式怎么完成这个转换的:
先一起来看几个简单的小例子,应该就懂了。


1
2
3
4
5

看到这,基本就懂了NFA的构建了。其实并不难,很简单。
这里再提一点,抛砖引玉一下,就是对于计算机来讲,构建NFA时通常采用的是自底向上的组合法,而人的逻辑通常是自顶向下的分解法。略微有些差异,感兴趣的同学可以研究讨论一下这一点,这里不做过多的提及。
做完转换图后,我们还是要把他变成一个表,因为只有变成一个表,才能有效的将数据录入的计算机内进行运算与处理。还是用之前的例子吧。


转换表
找出所有可以被匹配的字符即符号集合∑作为每一列的字段名,然后从起始态开始
1)状态0可以匹配a,匹配后可以到状态0或状态1,记为∅。匹配b只能得到状态0,记为{0}。
2)状态1可以匹配a,没有匹配到,记为∅。匹配b得到状态2,记为{2}。
3)状态0可以匹配a,没有匹配到,记为∅。匹配b得到状态3,记为{3}。
4)状态0可以匹配a,没有匹配到,记为∅。匹配b没有匹配到,记为∅。

至此,状态表建立完成。正则式(RE)转不确定型有穷自动机(NFA)完成。

相关文章

  • 正则到NFA的转换

    有穷自动机 作用:将输入的序列转换成一个状态图,方便之后的处理。通常被用在词法分析器中。1)有穷自动机是一个识别器...

  • NFA到DFA的转换及DFA的简化

    还不太了解有穷自动机或是NFA的同学可以先看我的上一篇文章:正则到NFA的转换 确定型有穷自动机 确定型有穷自动机...

  • 正则匹配

    正则 正则表达式引擎匹配 正则引擎大体上可分为不同的两类:DFA和NFA,而NFA又基本上可以分为传统型NFA和P...

  • 正则表达式快速入门

    正则表达式的引擎分为三种:NFA、DFA、POSIX NFAJavaScript 使用的是 NFA 的正则表达式引...

  • 《算法》笔记 16 - 正则表达式

    使用正则表达式描述模式 非确定有限状态自动机NFA 模拟NFA的运行NFA的表示构造与正则表达式相对应的NFANF...

  • DFA确定化和最小化

    从正规式开始 一、先将正规式转换成NFA 通过下面的对应法则将正规式转换成NFA 例如: 二、再将NFA转成DFA...

  • 编译原理随记

    NFA的模拟:算法第四版上面的正则表达式篇,下载地址正则表达式转NFA算法:Thompson's construc...

  • 第二章第6节 从 NFA 到 DFA 的转换

    从NFA 到 DFA 的转换 image.png image.png 子集构造法 subset construct...

  • 用 Java 实现一个正则表达式引擎

    实现一个正则表达式需要几步? 就三步: 分析正则表达式并构建出NFA 根据NFA得出DFA 根据DFA匹配字符串当...

  • 第四章:表达式的匹配原理

    正则表达式匹配引擎的两种技术: 表达式主导的NFA(非确定性有穷自动机)传统型NFAPOSIX NFA 文本主导的...

网友评论

    本文标题:正则到NFA的转换

    本文链接:https://www.haomeiwen.com/subject/owrqwqtx.html