编译原理复习---正则表达式+有穷自动机

适用于电子科技大学编译原理期末考试复习。

1. 正则表达式

正则表达式(Regular Expression,简称regex或regexp)是一种用于描述、匹配和操作文本模式的强大工具。它由一系列字符和特殊符号组成,这些字符和符号定义了一种搜索模式,可以用来检查一个字符串是否包含某个子串、将匹配的子串进行替换或者从字符串中提取符合条件的子串等。

总结来说,正则表达式就是通过特定字符与文法符号的组合来描述一种语言的方式。

正则语言 == 上下文无关文法 == 正则表达式,三者之间可以相互转换

编译原理这门课中,正则表达式所使用的符号与标准的定义好像不太相同,我只能凭借做题的经验列举出大致的用法:

  • (a_1|a_2|...|a_n):表示集合{a_1a_2,...,a_n}中的任意一个字符。

  • 每一个单元(正则表达式中的一个字符或用括号包围起来的一组符号)后可加上" * "(克林闭包)、" + "(正闭包)。

  • " . "表示字母表中的任意字符。

例如:a(a|b)^*(\varepsilon | (.|\_)(a|b)(a|b)^*)

2. 有穷自动机

有穷自动机(Finite Automaton, FA),也称为有限状态机,是一种计算模型,用于描述和识别特定类型的语言。它由以下几个基本组成部分构成:

  1. 状态集合(Q):有限个状态的集合。

  2. 字母表(Σ):有限个输入符号的集合。

  3. 转移函数(δ):定义了从一个状态和一个输入符号到另一个状态的映射,即 δ: Q × Σ → Q。

  4. 初始状态(q0):自动机开始处理输入前所在的状态,q0 ∈ Q。

  5. 接受状态集(F):状态集合的一个子集,表示当自动机停止时可以处于的状态,这些状态表明输入字符串被接受,F ⊆ Q。

通常,我们使用状态转换图来表示有穷自动机:

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

DFA的每一步操作都是确定的,即对于一个状态和一个输入符号,有唯一确定的下一个状态。

而NFA在某些状态下,对于一个输入符号可能有多个可能的下一个状态。

相对于DFA,NFA更加直观,但是对于计算机来说,DFA才方便其使用。

我们要将正则表达式转换为DFA并不好转换,可以先将其转换为更加直观的NFA,然后再将NFA转换为DFA。

3. 正则表达式转换为NFA

3.1 单个符号的NFA

3.2 (a|b)的NFA,并联

3.3 ab的NFA,串联

3.4 a*的NFA

通过以上四种方式,我们可以逐步将一个正则表达式转换为NFA。

4. NFA转化为DFA

  1. 初始状态在遇到某个输入符号时能进入的所有状态的集合定义为一个新的状态,在DFA的状态图中,初始状态指向该新状态。

  2. 对每个输入符号都进行检查,定义出一系列新的状态。

  3. 对于每个新状态,将其当作初始状态并重复上面两步,直到不再有新状态产生。

注意,当通过某个输入符号到达某一状态时,新到达的状态如果可以通过空边到达其他状态,那么也视为在遇到该输入符号时能到达这些状态。

如果初始状态可以通过空边到达其他状态,那么应该把这几个状态连同初始状态当作DFA中的初始状态。

举例子太费劲了,就不举了。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/494957.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

漏洞检测工具:HOST头部攻击

HOST头部攻击 漏洞定义 Host头部字段在HTTP协议中用于指定请求所针对的域名,以便服务器能够正确地将请求路由到相应的Web应用程序。攻击者通过篡改HTTP请求中的Host头部字段来执行恶意操作。 漏洞危害 Host头部攻击的危害在于它能导致敏感信息泄露、恶意内容执行…

ROS1入门教程6:复杂行为处理

一、新建项目 # 创建工作空间 mkdir -p demo6/src && cd demo6# 创建功能包 catkin_create_pkg demo roscpp rosmsg actionlib_msgs message_generation tf二、创建行为 # 创建行为文件夹 mkdir action && cd action# 创建行为文件 vim Move.action# 定义行为…

DL作业11 LSTM

习题6-4 推导LSTM网络中参数的梯度, 并分析其避免梯度消失的效果 LSTM(长短期记忆网络)是一种特殊的循环神经网络(RNN),旨在解决普通 RNN 在处理长序列时遇到的梯度消失和梯度爆炸问题。它通过设计多个门…

WWW23-多行为级联|级联图卷积网络的多行为推荐

论文:https://arxiv.org/abs/2303.15720 代码:https://github.com/SS-00-SS/MBCGCN 这篇论文MB-CGCN和上一篇CRGCN是同一个团队的,都是级联的方式。一个用了残差,一个用了特征转换,文章最后有discussion讨论了两者的不…

JAVA开发入门学习七- 数组

数组的概念 概念 数组: 是多个相同类型数据按照一定排列的集合,并使用一个名字命名,并通过编号的方式对这些数据进行统一管理 数组中的概念 数组名: 数组的名称,命名 下标: 从0开始 元素:…

【编辑器扩展】打开持久化路径/缓存路径/DataPath/StreamingAssetsPath文件夹

代码 [MenuItem("Assets/Open Explorer/PersistentDataPath")]public static void OpenPersistentDataPath(){Application.OpenURL(Application.persistentDataPath);}[MenuItem("Assets/Open Explorer/DataPath")]public static void OpenDataPath(){Appl…

链路聚合与GVRP的混合构建(eNSP)

目录 拓扑图: 前置操作: GVRP全局开启: 查询: 实验背景:前面依次搭建了交换机的链路聚合实验手册以及动态vlan GVRP,为了模拟真实环境,本次实验将两者结合。 拓扑图: 前置操作&…

由于这些关键原因,我总是手边有一台虚拟机

概括 虚拟机提供了一个安全的环境来测试有风险的设置或软件,而不会影响您的主系统。设置和保存虚拟机非常简单,无需更改主要设备即可方便地访问多个操作系统。运行虚拟机可能会占用大量资源,但现代 PC 可以很好地处理它,为实验和工作流程优化提供无限的可能性。如果您喜欢使…

华为ensp--BGP路由反射器

学习新思想、争做新青年,今天学习的是BGP路由反射器。 实验目的 理解BGP路由反射器的应用场景 理解BGP路由反射器的工作原理 掌握BGP路由反射器的基本配置方法 实验内容 本实验网络包含了两个AS,两个Cluster。R1、R2、R3属于Cluster 1&#xff0c…

使用idea创建JDK8的SpringBoot项目

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 使用idea创建JDK8的SpringBoot项目 前言我们经常在创建新的springboot项目,默认使用的是spring.io进行创建,但是它总是只会提供高版本的创建方式&…

初学stm32 --- 定时器中断

目录 时钟选择: 内部时钟选择​编辑 时钟计算方法: 计数器模式 向下计数模式(时钟分频因子1,ARR36) 向上计数模式(时钟分频因子1,ARR36) 中央对齐计数模式(时钟分频因…

windows下安装配置anaconda及常用的conda命令

Anaconda极大的简化了Python环境和库的管理,其最大的作用就是可以创建、管理多个不同python版本的虚拟环境,起到不同环境相互隔离、互不干扰、避免环境冲突的目的。如果使用本地Python安装多个包,经常会遇到包冲突,导致整个python…

安装CPU版的torch(清华源)

1、安装指令: pip3 install torch torchvision torchaudio -i https://pypi.tuna.tsinghua.edu.cn/simple2、验证torch是否安装成功 // 使用python验证 import torch print(torch.__version__)能正常打印版本即表示安装成功,如下图

ASP.NET Core Web API 控制器

文章目录 一、基类:ControllerBase二、API 控制器类属性三、使用 Get() 方法提供天气预报结果 在深入探讨如何编写自己的 PizzaController 类之前,让我们先看一下 WeatherController 示例中的代码,了解它的工作原理。 在本单元中&#xff0c…

【蓝桥杯——物联网设计与开发】基础模块8 - RTC

目录 一、RTC (1)资源介绍 🔅简介 🔅时钟与分频(十分重要‼️) (2)STM32CubeMX 软件配置 (3)代码编写 (4)实验现象 二、RTC接口…

k8s dashboard可视化操作界面的安装

一、官方安装方法 根据官网的安装配置可以选择如下安装: kubectl apply -f https://raw.githubusercontent.com/kubernetes/dashboard/v2.0.0/aio/deploy/recommended.yaml 二、添加阿里云加速进行安装 #修改recommended.yaml拉取镜像的链接 vim recommended.yam…

【目标跟踪综述及关键技术】

1.多目标跟踪任务介绍 定义 多目标跟踪旨在将视频序列中感兴趣的目标检测出来,并赋予每个目标单独的编号,在整个序列中形成目标的轨迹。 分类 online:算法在推理目标身份过程中,只能看见当前帧以及之前的帧(关联&a…

webrtc音频模块(三) windows Core Audio API及声音的播放

在前面介绍了ADM(Audio Device Module),它用于抽象音频设备管理和音频数据采集/播放接口。windows的实现是AudioDeviceWinowCode,它封装了Core Audio APIs实现了对音频设备的操作。 Core Audio APIs windows提供了多种音频操作API,比如最常…

在linux系统的docker中安装GitLab

一、安装GitLab: 在安装了docker之后就是下载安装GitLab了,在linux系统中输入命令:docker search gitlab就可以看到很多项目,一般安装第一个,它是英文版的,如果英文不好可以安装twang2218/gitlab-ce-zh。 …

uniapp跨平台开发---webview调用app方法

1.app端实现 注意:为了实现实时通信,app端页面是.nvue 代码实现 <template><view class"content"><view class"web-view"><web-view class"web-view" :src"url" ref"webview" onPostMessage"o…