正规文法、正规式、确定的有穷自动机DFA、不确定的有穷自动机NFA 的概念、区分以及等价性转换【我直接拿下!】

本文主要是介绍正规文法、正规式、确定的有穷自动机DFA、不确定的有穷自动机NFA 的概念、区分以及等价性转换【我直接拿下!】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

      • 正规文法
      • 正规式
      • 有穷自动机
        • 确定的有穷自动机——DFA
        • 不确定的有穷自动机——NFA
        • DFA 与 NFA 的区分
      • 正规式转换为正规文法
      • 正规文法转换为正规式
      • NFA 转换为 DFA
        • NFA 最小化
      • NFA 转换为正规式
      • 正规式转换为 NFA
      • 正规文法转换为 NFA
      • NFA 转换为正规文法

前言:

在学习正规文法之前,需要先了解一下什么是文法,具体可以查看这篇文章,总结的比较好 —— 编译原理–四种文法的理解

正规文法

设有 G=(VN,VT,P,S),若 P 中的每一个产生式的形式都是 A ——> aBA——>a,其中 AB 都是非终结符,a 属于 VT*,则称 G3 型文法,又称正规文法。

正规式

正规式也称正则表达式,也是表示正规集的工具。是一种用于匹配文本模式的字符序列。由普通字符(如字母、数字)和特殊字符(如元字符)组成的表达式。

在正规式中,常见的元字符包括:

  • 通配符(如 . 表示匹配任意字符)

  • 字符类(如 [0-9] 表示匹配数字 09 之间的任意一个字符)

  • 量词(如 * 表示匹配前面的字符 0 次或多次)

  • 锚点(如 ^ 表示匹配字符串的开头、$ 表示匹配字符串的结尾)

有穷自动机

有穷自动机(Finite State Machine,FSM)是一种抽象的识别装置,用于描述具有有限个状态并在输入序列驱动下进行状态转换的系统,能准确地识别正规集。

一个有穷自动机由以下几个要素组成:

1. 状态集合(States): 有穷自动机的所有可能状态的集合。每个状态代表系统的某种特定情况或条件。

2. 输入字母表(Input Alphabet): 有穷自动机接受的输入符号的集合。例如,二进制数的有穷自动机的输入字母表可以是{0, 1}。

3. 转移函数(Transition Function): 描述从一个状态到另一个状态的转移规则。该函数接受当前状态和输入符号,并返回下一个状态。转移函数可以用图形表示,其中状态是节点,输入符号是边。

4. 初始状态(Initial State): 有穷自动机开始运行时的起始状态。

5. 终止状态(Accepting States): 有穷自动机在运行过程中达到的特殊状态。当有穷自动机达到终止状态时,它可以接受或拒绝输入序列。

有穷自动机分为确定性有穷自动机(Deterministic Finite Automaton,DFA)和非确定性有穷自动机(Nondeterministic Finite Automaton,NFA)。

在确定性有穷自动机(DFA)中,每个状态都有唯一的转移路径,而在非确定性有穷自动机(NFA)中,一个状态可以有多个转移路径。

确定的有穷自动机——DFA

一个确定的有穷自动机 DFA 由一个五元组组成,可以用以下公式表示:

M = (K, Σ, f, S, Z)

其中:

  • K 表示一个有穷集,它的每个元素称为一个状态。

  • Σ 表示有穷字母表,Σ = {a₁, a₂, ..., aₘ},每个字母代表有穷自动机接受的输入符号,也成为输入符号表。

  • f 表示转移函数,K × Σ → K,它描述从一个状态到另一个状态的转移规则。对于给定的状态 Kᵢ 和输入符号 a,则经过 f 转换函数后,会返回下一个状态 Kⱼ,转换规则如:f(Kᵢ,a) = Kⱼ

  • S 表示初态集,S ∈ K,它是唯一的一个初态。

  • Z 表示终态集,Z ⊆ K,当有穷自动机达到终止状态时,它可以接受或拒绝输入序列,也称为可接受状态或结束状态。

不确定的有穷自动机——NFA

一个不确定的有穷自动机 NFA 同样也是由一个五元组组成,可以用以下公式表示:

M = (K, Σ, f, S, Z)

其中:

  • K 表示一个有穷集,它的每个元素称为一个状态。

  • Σ 表示有穷字母表,Σ = {a₁, a₂, ..., aₘ},每个字母代表有穷自动机接受的输入符号,也成为输入符号表。

  • f 表示转移函数,K × Σ* → K,表示 K 的全体子集的映像,即 K × Σ* → 2K,其中 2K 表示 K 的幂集。

  • S 表示初态集,S ⊆ K,表示一个非空初态集。

  • Z 表示终态集,Z ⊆ K,表示一个终态集。

当有穷字母表 Σ 中存在 ε 空串时,那么该有穷自动机为 NFA。

DFA 与 NFA 的区分

DFA 和 NFA 的主要区别在于它们的转移函数和转移规则:

转移函数不同

DFA 的转移函数是唯一的,即每个状态和输入符号只对应唯一的下一个状态(同一路径中输入符号必须唯一)。

NFA 的转移函数可以有多个下一个状态,也就是说一个状态可以按照多种选择进行转移。


转移规则不同

DFA 的转移规则相对简单,每个状态在接收到输入符号后只能转移到唯一的下一个状态,从而形成确定的转移路径。

NFA 的转移规则更加复杂,一个状态可以按照多种选择进行转移,从而形成多条可能的转移路径。


因此,DFA 模型的缺点是其在某些情况下需要更多的状态来表示相同的语言,并且难以处理一些复杂的语言。然而,DFA 的优势在于其转移函数和转移规则都明确,因此可以直接实现,易于编程实现和模拟执行。

正规式转换为正规文法

在开始转换之前,我们先来了解一下正规式转换正规文法的公式,一共有三个,如下所示:

当存在正规式产生式 A → xy,则有正规文法:

A → xB
B →   y

当存在正规式产生式 A → x*y,则有正规文法:

A → xB
A →   y
B → xB
B →   y

当存在正规式产生式 A → x|y,则有正规文法

A   →   x
B   →   y

转换示例:

将正规式 r = a(a|d)* 转换为相应的正规文法,转换过程如下所示:

正规文法转换为正规式

正规文法转换为正规式同样有三个公式,如下所示:

当存在正规文法 A → xBB → y,则有正规式 A = xy

当存在正规文法 A → xA|y,则有正规式 A = x*y

当存在正规文法 A → xB → y,则有正规式 A = x|y


转换示例:

现有文法 G[S],其所有产生式如下所示:

S → aA
S →    a
A → aA
A → dA
A →    a
A →    d

将文法 G[S] 转换为正规式:

NFA 转换为 DFA

这里先来了解将 NFA 转化为接受同样语言的 DFA 的算法,称为子集法

子集法是一种用于将不确定的有穷自动机(NFA)转换为具有等价性的确定的有穷自动机(DFA)的算法。

在子集法中,我们将每个 DFA 状态表示为 NFA 状态的子集。具体步骤如下:

  1. 创建 DFA 的初始状态。这个初始状态是由 NFA 的初始状态以及通过 ε转移可以到达的其他状态组成的子集。可以表达为 ε-closure(I),其中 I 为初态,也就是求从初态 I 开始,经过 ε 所到达的状态形成的闭包集合。

  2. 对于新创建的 DFA 状态,遍历每个输入符号(除去 ε 空串)。对于每个输入符号,找出从当前 DFA 状态中的任意一个 NFA 状态通过该输入符号可以达到的所有 NFA 状态,并将它们作为新的 DFA 状态的部分。可以表示为 move(I,a),从初态 I 开始,经过 a 弧所到达状态。

重复第 2 步,直到无法再创建新的 DFA 状态为止。最终得到的每个 DFA 状态都与 NFA 的某个状态集合相对应。

转换示例:

将给出的 NFA-N 状态图,转换为等价的 DFA。

NFA 最小化

在进行最小化(简化)前,需要先进行多余状态检查。检查从该自动机的开始状态出发,任何输入串也不能到达的那个状态,或者从这个状态没有通路到达终态。

在确定有限自动机(DFA)中,最小化是指将给定的 DFA 转换为等价且具有最少状态数量的 DFA。

最小化的目的是简化自动机的结构,减少状态数量,从而提高处理效率和性能。

下面是最小化 DFA 的一种常见方法,称为 Hopcroft 算法:

1.初始化分区: 将 DFA 的状态划分为两个初始分区,即接受状态(终态)和非接受状态(非终态)。

2.对于每个划分:

  • a. 对于每个输入符号,检查该划分中的状态在该输入符号下是否具有相同的转移目标。如果不是,则根据该输入符号将状态进行划分。

  • b. 如果对于某个输入符号的划分发生了变化,重新开始对所有划分进行遍历。

重复步骤 2,直到没有新的划分发生,最终得到的划分即为最小化 DFA 的状态集合。

在 Hopcroft 算法中,通过不断比较状态的转移目标,将具有相同转移目标的状态划分在同一个分区。这样可以逐步减少分区的数量,直至无法再进行划分为止。

最小化示例

对上方转换的 DFA 状态图进行最小化处理。

NFA 转换为正规式

将 NFA 转换为具有等价性的正规式公式如下:

转换示例:

正规式转换为 NFA

将正规式转换为具有等价性的 NFA 公式如下:

转换示例:

正规文法转换为 NFA

将正规文法转换为具有等价性的 NFA 十分简单,只需要根据正规文法产生式一步步描述出来即可,但是需要增加一个终态产生式

假设当前存在正规文法 G[S]:S—>aA A—>b,转换为等价性的 NFA 过程如下所示:

转换示例:

将正规文法 G[S] 转换为具有等价性的 NFA。

NFA 转换为正规文法

将 NFA 转换为正规文法同样简单,根据状态图直接可以的出结果,但是需要注意结果的格式书写。

正规文法结果由四部分组成,分别为:有穷集 K、有穷字母表 Σ、产生式 P 以及初态组成。

转换示例:

将下图所示的 NFA 转换为具有等价性的正规文法。




希望这篇文章对你有所帮助。

这篇关于正规文法、正规式、确定的有穷自动机DFA、不确定的有穷自动机NFA 的概念、区分以及等价性转换【我直接拿下!】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/264250

相关文章

hdu 3065 AC自动机 匹配串编号以及出现次数

题意: 仍旧是天朝语题。 Input 第一行,一个整数N(1<=N<=1000),表示病毒特征码的个数。 接下来N行,每行表示一个病毒特征码,特征码字符串长度在1—50之间,并且只包含“英文大写字符”。任意两个病毒特征码,不会完全相同。 在这之后一行,表示“万恶之源”网站源码,源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符(不包括回车)。

POJ 1625 自动机

给出包含n个可见字符的字符集,以下所提字符串均由该字符集中的字符构成。给出p个长度不超过10的字符串,求长为m且不包含上述p个字符串的字符串有多少个。 g++提交 int mat[108][108] ;int matn ;int N ;map<char ,int> to ;//ACconst int maxm = 108 ;const int kin

zoj 3228 ac自动机

给出一个字符串和若干个单词,问这些单词在字符串里面出现了多少次。单词前面为0表示这个单词可重叠出现,1为不可重叠出现。 Sample Input ab 2 0 ab 1 ab abababac 2 0 aba 1 aba abcdefghijklmnopqrstuvwxyz 3 0 abc 1 def 1 jmn Sample Output Case 1 1 1 Case 2

【VUE】跨域问题的概念,以及解决方法。

目录 1.跨域概念 2.解决方法 2.1 配置网络请求代理 2.2 使用@CrossOrigin 注解 2.3 通过配置文件实现跨域 2.4 添加 CorsWebFilter 来解决跨域问题 1.跨域概念 跨域问题是由于浏览器实施了同源策略,该策略要求请求的域名、协议和端口必须与提供资源的服务相同。如果不相同,则需要服务器显式地允许这种跨域请求。一般在springbo

如何确定 Go 语言中 HTTP 连接池的最佳参数?

确定 Go 语言中 HTTP 连接池的最佳参数可以通过以下几种方式: 一、分析应用场景和需求 并发请求量: 确定应用程序在特定时间段内可能同时发起的 HTTP 请求数量。如果并发请求量很高,需要设置较大的连接池参数以满足需求。例如,对于一个高并发的 Web 服务,可能同时有数百个请求在处理,此时需要较大的连接池大小。可以通过压力测试工具模拟高并发场景,观察系统在不同并发请求下的性能表现,从而

PDF 软件如何帮助您编辑、转换和保护文件。

如何找到最好的 PDF 编辑器。 无论您是在为您的企业寻找更高效的 PDF 解决方案,还是尝试组织和编辑主文档,PDF 编辑器都可以在一个地方提供您需要的所有工具。市面上有很多 PDF 编辑器 — 在决定哪个最适合您时,请考虑这些因素。 1. 确定您的 PDF 文档软件需求。 不同的 PDF 文档软件程序可以具有不同的功能,因此在决定哪个是最适合您的 PDF 软件之前,请花点时间评估您的

【MRI基础】TR 和 TE 时间概念

重复时间 (TR) 磁共振成像 (MRI) 中的 TR(重复时间,repetition time)是施加于同一切片的连续脉冲序列之间的时间间隔。具体而言,TR 是施加一个 RF(射频)脉冲与施加下一个 RF 脉冲之间的持续时间。TR 以毫秒 (ms) 为单位,主要控制后续脉冲之前的纵向弛豫程度(T1 弛豫),使其成为显著影响 MRI 中的图像对比度和信号特性的重要参数。 回声时间 (TE)

C# double[] 和Matlab数组MWArray[]转换

C# double[] 转换成MWArray[], 直接赋值就行             MWNumericArray[] ma = new MWNumericArray[4];             double[] dT = new double[] { 0 };             double[] dT1 = new double[] { 0,2 };

计算机网络基础概念 交换机、路由器、网关、TBOX

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、VLAN是什么?二 、交换机三、路由器四、网关五、TBOXTelematics BOX,简称车载T-BOX,车联网系统包含四部分,主机、车载T-BOX、手机APP及后台系统。主机主要用于车内的影音娱乐,以及车辆信息显示;车载T-BOX主要用于和后台系统/手机APP通信,实现手机APP的车辆信息显示与控

01 Docker概念和部署

目录 1.1 Docker 概述 1.1.1 Docker 的优势 1.1.2 镜像 1.1.3 容器 1.1.4 仓库 1.2 安装 Docker 1.2.1 配置和安装依赖环境 1.3镜像操作 1.3.1 搜索镜像 1.3.2 获取镜像 1.3.3 查看镜像 1.3.4 给镜像重命名 1.3.5 存储,载入镜像和删除镜像 1.4 Doecker容器操作 1.4