没有合适的资源？快使用搜索试试~ 我知道了~

文库首页人工智能深度学习形式语言与自动机：第六讲正规语言的性质与运算

形式语言与自动机：第六讲正规语言的性质与运算

1.该资源内容由用户上传，如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款（资源遇到问题，请及时私信上传者）

版权申诉

形式语言

0 下载量 85 浏览量 2022-05-09 23:03:55 上传评论收藏 532KB PDF 举报

温馨提示

试读

32页

形式语言与自动机：第六讲正规语言的性质与运算

资源推荐

资源详情

资源评论

FL&A

第六讲

 正规语言的性质与运算

FL&A

 针对正规语言的 Pumping 引理

正规语言的性质与运算

 有关正规语言的几个判定性质

 关于正规语言的封闭运算

FL&A

 正规语言应满足的一个必要条件

 可用于判定某些语言不是正规语言

针对正规语言的 Pumping 引理

FL&A

 DFA 的

“

Pumping”特性

设 DFA D = (Q, ,



, q

, F ), |Q|=n.

对于任一长度不小于 n 的字符串 w = a

…a

, 其

中 mn, a

 (1 k m), qQ , 考察如下状态序列



'(q, a

)



'(q, a

)

…



'(q, a

…a

)

n+1



'(q, a

…a

n+1

)

…



'(q, a

…a

)

由Pigeonhole 原理,

, p

,…,p

中至少有

两个状态是重复的，即存

在 i, j, 0ijn, p

 “pumping”特性：

任一长度不小于状态数目

的字符串所标记的路径上

，

必然出现重复的状态.

针对正规语言的 Pumping 引理

FL&A

 “pumping”特性：如前,设 DFA D = (Q, ,



, q

, F ),

|Q|=n, w = a

…a

(mn), 则存在 i, j, 0ijn, p

其中p



'(p

, a

…a

) , 0km.

 若假定p

, p

F, 即wL(D).

令 w = xyz, 其中：

x = a

…a

, y = a

i+1

i+2

…a

, z = a

j+1

j+2

…a

则对任何k  0，都有 xy

z L(D). (参考下图)

Start

x = a

…a

y = a

i+1

i+2

…a

z=a

j+1

j+2

…a

针对正规语言的 Pumping 引理

 DFA 的

“

Pumping”特性

剩余31页未读，继续阅读

评论收藏

内容反馈

1.该资源内容由用户上传，如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款（资源遇到问题，请及时私信上传者）

版权申诉

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

wxg520cxl

粉丝: 23
资源: 3万+

下载权益

C知道特权

VIP文章

课程特权

VIP享7折，此内容立减5.97元

开通VIP

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

形式语言与自动机：第六讲 正规语言的性质与运算

形式语言与自动机：第六讲 正规语言的性质与运算.pdf

形式语言与自动机理论--第五章 正则语言的性质1（第十一周）.ppt

形式语言与自动机：第十一讲 上下文无关语言的性质与运算.pdf

形式语言与自动机：第三讲 正规表达式与正规语言.pdf

形式语言与自动机：第三讲 正规表达式与正规语言

形式语言与自动机：第十讲 CFG 的简化及 Chomsky 范式.pdf

形式语言与自动机：第五讲 有限状态自动机 -正规表达式.pdf

形式语言与自动机：第五讲 有限状态自动机 -正规表达式

形式语言与自动机：第十一讲 上下文无关语言的性质与运算

形式语言与自动机：第七讲 下推自动机

形式语言与自动机：第四讲 有限状态自动机

形式语言与自动机：第七讲 下推自动机.pdf

形式语言与自动机：第四讲 有限状态自动机.pdf

形式语言与自动机：第二讲 上下文无关文法与上下文无关语言

形式语言与自动机：第十讲 CFG 的简化及 Chomsky 范式

形式语言与自动机：第八讲 上下文无关文法-下推自动机

形式语言与自动机：第二讲 上下文无关文法与上下文无关语言.pdf

形式语言与自动机：第八讲 上下文无关文法-下推自动机.pdf

形式语言与自动机：第十三讲 计算理论初步

形式语言与自动机：第十二讲 图灵机与递归可枚举语言

YOLOv8-deepsort 实现智能车辆目标检测+车辆跟踪+车辆计数

YOLOv8网络结构图，自制visio文件，yolov8.vsds，需要的自取，在原有的基础上直接改就行了

yolov8(2023年8月版本),已经下好yolov8s.pt和yolov8n.pt

Transformer模型实现长期预测并可视化结果（附代码+数据集+原理介绍）

社交平台上经济类话题的文章热度信息，数据是真实的，但不是真实日期

行人跌倒数据集（VOC格式）

YOLOV5 + 双目相机实现三维测距（新版本）

Unet眼底血管图像分割数据集+代码+模型+系统界面+教学视频.zip

最新资源

形式语言与自动机：第六讲正规语言的性质与运算

形式语言与自动机：第六讲正规语言的性质与运算.pdf

形式语言与自动机理论--第五章正则语言的性质1（第十一周）.ppt

形式语言与自动机：第十一讲上下文无关语言的性质与运算.pdf

形式语言与自动机：第三讲正规表达式与正规语言.pdf

形式语言与自动机：第三讲正规表达式与正规语言

形式语言与自动机：第五讲有限状态自动机 -正规表达式.pdf

形式语言与自动机：第五讲有限状态自动机 -正规表达式

形式语言与自动机：第十一讲上下文无关语言的性质与运算

形式语言与自动机：第七讲下推自动机

形式语言与自动机：第四讲有限状态自动机

形式语言与自动机：第七讲下推自动机.pdf

形式语言与自动机：第四讲有限状态自动机.pdf

形式语言与自动机：第二讲上下文无关文法与上下文无关语言

形式语言与自动机：第八讲上下文无关文法-下推自动机

形式语言与自动机：第二讲上下文无关文法与上下文无关语言.pdf

形式语言与自动机：第八讲上下文无关文法-下推自动机.pdf

形式语言与自动机：第十三讲计算理论初步

形式语言与自动机：第十二讲图灵机与递归可枚举语言