收藏 分销(赏)

正规语言的泵引理.ppt

上传人:精*** 文档编号:14507061 上传时间:2026-10-02 格式:PPT 页数:7 大小:441.54KB 下载积分:10 金币
下载 相关
正规语言的泵引理.ppt_第1页
第1页 / 共7页
正规语言的泵引理.ppt_第2页
第2页 / 共7页


点击查看更多>>
资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,正规语言的泵引理,正规语言的泵引理,Pumping,引理揭示了正规语言普遍具有的这样一个,封闭,性质:如果,L,是一个正规语言,那么,存在一个正整数,k,L,中那些长度,k,的句子中,都含有这样的一段子串,把这个子串重复任意多次后形成的句子仍然是,L,中,的,语句,。,Pumping,引理,设,L,为一个正规语言,那么存在,正整数,n,,,使得,zL,,,当,|z|,n,时,都可写成,z=uvw,的形式,其中,|uv|,n,|v|0,并且对任何非负整数,i,,都有,uv,i,wL,Pumping引理揭示了正规语言普遍具有的这样一个封闭性质:如果L是一个正规语言,那么存在一个正整数k,L中那些长度 k的句子中,都含有这样的一段子串,把这个子串重复任意多次后形成的句子仍然是L中的语句。,用泵引理找出习题中的非正规语言。,Pumping引理揭示了正规语言普遍具有的这样一个封闭性质:如果L是一个正规语言,那么存在一个正整数k,L中那些长度 k的句子中,都含有这样的一段子串,把这个子串重复任意多次后形成的句子仍然是L中的语句。,例1 0n1n|n0,例2 0n|n是平方数,算术表达式构成的集合不是正规语言。,用泵引理找出习题中的非正规语言。,Pumping引理揭示了正规语言普遍具有的这样一个封闭性质:如果L是一个正规语言,那么存在一个正整数k,L中那些长度 k的句子中,都含有这样的一段子串,把这个子串重复任意多次后形成的句子仍然是L中的语句。,用泵引理找出习题中的非正规语言。,算术表达式构成的集合不是正规语言。,Pumping引理揭示了正规语言普遍具有的这样一个封闭性质:如果L是一个正规语言,那么存在一个正整数k,L中那些长度 k的句子中,都含有这样的一段子串,把这个子串重复任意多次后形成的句子仍然是L中的语句。,z=uvw,算术表达式构成的集合不是正规语言。,例2 0n|n是平方数,uviwL,的形式,其中|uv|n,|v|0,并且对任何非负整数 i,都有,Pumping引理 设L为一个正规语言,那么存在正整数 n,使得zL,当|z|n时,都可写成,的形式,其中|uv|n,|v|0,并且对任何非负整数 i,都有,算术表达式构成的集合不是正规语言。,Pumping引理揭示了正规语言普遍具有的这样一个封闭性质:如果L是一个正规语言,那么存在一个正整数k,L中那些长度 k的句子中,都含有这样的一段子串,把这个子串重复任意多次后形成的句子仍然是L中的语句。,应用上述泵引理可以辨别出非正规语言。,Pumping引理揭示了正规语言普遍具有的这样一个封闭性质:如果L是一个正规语言,那么存在一个正整数k,L中那些长度 k的句子中,都含有这样的一段子串,把这个子串重复任意多次后形成的句子仍然是L中的语句。,用泵引理找出习题中的非正规语言。,算术表达式构成的集合不是正规语言。,用泵引理找出习题中的非正规语言。,应用上述泵引理可以辨别出非正规语言。,用泵引理找出习题中的非正规语言。,Pumping引理揭示了正规语言普遍具有的这样一个封闭性质:如果L是一个正规语言,那么存在一个正整数k,L中那些长度 k的句子中,都含有这样的一段子串,把这个子串重复任意多次后形成的句子仍然是L中的语句。,uviwL,例1 0n1n|n0,z=uvw,泵引理的应用,应用上述泵引理可以辨别出非正规语言。,例,1,0,n,1,n,|n0,例,2,0,n,|n,是平方数,练习,算术表达式构成的集合不是正规语言。,用泵引理找出习题中的非正规语言。,作 业,习题的,1)4),题。,
展开阅读全文

开通  VIP、SVIP  下载更划算
下载10份以上建议开通 VIP 会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 包罗万象 > 大杂烩

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        关注我们

©2010-2026 宁波自信网络信息技术有限公司  版权所有

客服电话:0574-28810668  投诉电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服