学习编译原理Time09 ~ 正则表达式转化为有穷自动机
小浩笔记
共 767字,需浏览 2分钟
· 2021-04-27
在说从正则表达式到有穷自动机之前,想提一下不确定的有穷自动机,因为正则表达式转化为确定的有穷自动机(DFA)是比较困难,而正则表达式转化为不确定的有穷自动机(NFA)是比较好实现的,本文就记录这个,下一篇笔记再谈谈NFA转化为DFA。
首先简单说一下,不确定的有穷自动机(NFA)
M=(S , ∑ , δ , s0, F )
S:有穷状态集
∑:输入字母表,即输入符号集合。假设 ε 不是∑中的元素
δ:将S X ∑映射到2^S的转换函数。 s ∈S ,a∈∑,δ(s,a)表示从状态s出发,沿着标号为a的边所能到达的状态集合(与DFA唯一区别的点)
s0:开始状态(或初始状态),s0∈S
F:接收状态(或终止状态)集合,FS
示例一个不确定的有穷自动机如下:
根据转换图可以看出,状态0遇到符号a的时候,就进入状态集合中,集合包含状态1和状态0;状态0遇到符号b的时候,就进入状态集合中,只包含状态0,同理,状态1遇到符号b的时候,就进入状态集合中,只包含状态2,...
接下来的就是根据正则表达式构造NFA
直接举一个例子:
r=(a | b)*abb
第一步:首先确定初始状态和终止状态,然后将有向边上的表达式进行分解
第二步:然后确定后缀部分abb,已经不能分解了
第三步:分解(a|b)*,因为带*是克林闭包
第四步:再分解,最终转化成NFA
小浩笔记
评论
【深度学习】人人都能看懂的LSTM
熟悉深度学习的朋友知道,LSTM是一种RNN模型,可以方便地处理时间序列数据,在NLP等领域有广泛应用。在看了台大李宏毅教授的深度学习视频后,特别是介绍的第一部分RNN以及LSTM,整个人醍醐灌顶。本文就是对视频的记录加上了一些个人的思考。0. 从RNN说起循环神经网络(Recurrent Neur
机器学习初学者
0
科普:深度学习训练,不同预算GPU选购指南
以下文章来源于微信公众号:DeepHub IMBA作者:Mike Clayton本文仅用于学术分享,如有侵权,请联系后台作删文处理导读购买显卡第一个要考虑的问题是什么?当然是预算。本文提供了不同预算的显卡选购指南,希望能对各位读者有所帮助。在进行机器学习项目时,特别是在处理深度学习和神经网络时,最好
机器学习初学者
0
学习开放日:开放复杂科学、AI+X 海量学习资源!
Datawhale干货 学习开放日:4月27-28日1. 什么是学习开放日?以AI为代表的技术突飞猛进,人类知识森林快速扩张,仅凭一人之力不仅难以覆盖,更是难以串联知识线索。唯有像蚂蚁探索最优路径一样,我们才能在信息爆炸的知识森林中探索出更好的方向!因此,今年集智斑图联合国内最
Datawhale
1
【深度学习】图解自注意力机制(Self-Attention)
一、注意力机制和自注意力机制的区别Attention机制与Self-Attention机制的区别传统的Attention机制发生在Target的元素和Source中的所有元素之间。简单讲就是说Attention机制中的权重的计算需要Target来参与。即在Encoder-Decoder 模型中,At
机器学习初学者
0
文末送书 | 大模型时代下如何学习云原生
《containerd 原理剖析与实战》新书内购中,点击阅读原文,限时 69.9 元购买。文末免费赠书大模型与云原生近年来,大语言模型的热度可谓是愈发高涨,尤其是今年年初 Sora 的出现,更是让全球再次看到了AIGC 的巨大威力。Sora 生成实例视频---几头巨大的长毛猛犸踏着积雪的草地而来在当
云原生实验室
10
轻松学习C#:百度行驶证C++离线SDK接入详解
效果 先看最终效果SDK 拿到完整包如图,687M解压后看看内容发现有个readme.txt,那就先看看内容1:用vs2015打开sln工程,最好用vs2015 comunity版本,可微软官网下载。2:sdk的doc目录有pdf接口文档。3:工程总入口main.cpp、请参考示例实现您的功能。4:
DotNet NB
9
日语五十音图学习难吗?
学习日语的初学者们都知道,我们学习日语最初就必须要接触日语五十音图,虽然相对其他语言来说,五十音图挺不是很难学,但是很多初学者可能会记不住,别担心,老师为大家带来了学习经验分享,一起来看看吧!五十音图就是日语最基础的基础,也就是地基。由于日语的元音比较单调,只有a/i/u/e/o这五种,再和各种辅音
python教程
0
每天骑的共享单车是什么通信原理,有人了解过吗?
转自:网络我们经常骑的共享单车到底是什么通信原理,有人了解过吗?现在就带大家了解下。一、智能车锁共享单车最核心的硬件是智能车锁,主要用于实现控制和定位功能。车锁内集成了嵌入式芯片(通信模块),GPS模块和物联网SIM卡。智能锁制造商通过在锁内集成带有独立号码的SIM卡,通过2G、3G、4G网络,与云
菜鸟学Python
1