Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >问答首页 >正则语言与pumping引理

正则语言与pumping引理
EN

Stack Overflow用户
提问于 2017-07-14 06:11:41
回答 1查看 362关注 0票数 1

我正在努力解决以下问题。我应该使用pumping引理或常规语言闭包,但我就是想不出解决这两个问题的办法。任何有洞察力的人都会非常感激。谢谢。

对于下面的每种语言,证明它是正规的或非正规的:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
1) {a^m b^n c^k: m>n>k}

2) {u that belong to {0,1}^* : u begins with 1001 and does not end with 0010}

当涉及到数字1时,我的假设是给定语言的反向也必须是规则的。然后,我可以使用pumping引理来证明它不是正则的,因此,原始语言是非正则的。这是一种有效的方法吗?

老实说,我不知道如何接近第二个。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2017-07-17 05:49:03

实际上2)是非常简单的。长度为8或更长的单词的正则表达式为

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
1001 · {0,1}^* · {all words of length 4 except 0010}

然后,你会想到所有符合定义的较短的单词,并使用联合。

对于1),如果你知道反转下的闭包,使用这个和泵浦引理。反转将c^k带到前面,如果你在这个块中执行,那么很明显你离开了语言。

否则,取补码并将其与b^+ c^+相交。你会得到

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
{a^m b^n c^k: m=1 AND (m<n OR n<k)}

这就是

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
{a b^n c^k: n<k }.

现在,您可以在b块内执行命令,以离开该语言。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/45095865

复制
相关文章
使数组唯一的最小增量
第一种:暴力解决 用数组统计每个数出现的次数,每次递增1,直到增加到一个没有重复出现过得数字位置。这种时间复杂度大,可以为 O(n^2)
木子星兮
2020/07/16
6600
使用oplog完成MongoDB增量备份
MongoDB是可以使用复制集的方式完成数据高可用,其实也不会丢数据,但是公司一般还是会要求有一个备份的库。而且在一些网络不能连通的情况(中间需要跨多个网络),就还需要实现手工的增量备份。本文介绍如何使用oplog完成MongoDB的增量备份。 数据准备 tenmao_mongo:PRIMARY> use blog switched to db blog tenmao_mongo:PRIMARY> db.article.insert({title:"one"}) WriteResult({ "nIns
十毛
2019/05/19
4.7K0
LeetCode 0945. 使数组唯一的最小增量
先对数组排序,之后对于每个元素,如果比前一个元素小,就一直加到比前一个元素大即可。每加一次,就是一次增量。
Yano_nankai
2021/02/24
3230
LeetCode 0945. 使数组唯一的最小增量
LeetCode 945. 使数组唯一的最小增量(贪心)
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/minimum-increment-to-make-array-unique 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
Michael阿明
2020/07/13
4910
9.下载ffmpeg、使QT支持同时编译32位和64位
进入http://ffmpeg.org/download.html,如果下载源码,则在右下方:
诺谦
2020/09/14
3.1K0
增量学习,,,
增量学习作为机器学习的一种方法,现阶段得到广泛的关注。在其中,输入数据不断被用于扩展现有模型的知识,即进一步训练模型,它代表了一种动态的学习的技术。对于满足以下条件的学习方法可以定义为增量学习方法:
狼啸风云
2022/06/08
6680
咔咔买房完成500万天使轮融资,域名竟然长这样
躲在树上的域小名
2017/12/25
8900
咔咔买房完成500万天使轮融资,域名竟然长这样
[NewLife.XCode]增量累加
NewLife.XCode是一个有10多年历史的开源数据中间件,支持nfx/netstandard,由新生命团队(2002~2019)开发完成并维护至今,以下简称XCode。
大石头
2019/05/24
1.7K0
TypeScript增量编译
我们在使用Node.js开发服务端时通常会使用TypeScript来开发大型项目,但是使用ts-node进行全量编译时经常遇到编译速度慢的问题,通常是修改一行代码编译两分钟。这时我们需要使用增量编译来优化编译速度,及其他的文件在项目启动时进行全量编译,开发时修改了哪个TS文件就编译成对应的JS文件。
用户6256742
2022/07/06
1.4K0
笑疯!外国小哥用ChatGPT完成80%工作,同时打4份工
---- 新智元报道   编辑:拉燕 【新智元导读】自从ChatGPT火了以后,办公室白领可真是爽翻了。甭管什么任务,交给ChatGPT,准没错。 不少白领在工作中都用上了ChatGPT,堪称如虎添翼。 毕竟,很多工作都是重复的、有章可循的。 既然有了科技力量的加持,用一用提升一下效率倒也不足为奇。 但有的打工人脑子更活泛,直接用ChatGPT在上班的时候接私活,一个人打两份工,疯狂「剥削」ChatGPT。 国外小哥Ben就表示,一个ChatGPT就能完成我本职工作80%的内容。剩下的精力接着薅GP
新智元
2023/05/09
2620
笑疯!外国小哥用ChatGPT完成80%工作,同时打4份工
MySQL实时增量备份
MySQL实时增量备份,采用binlog日志的好处   掌控所有更改操作,必要时可用于恢复数据 数据库主从复制的必要条件
星哥玩云
2022/08/18
2.7K0
java增量发布工具
有些公司由于没有使用maven作为构建工具,全量发布时没问题,而修改bug增量发布往往是将改动的代码手动编译后,从classes目录下拷贝到jar中然后再放到tomcat目录下发布,这种方法准确度不高,当修复bug时间跨度较大且文件较多时就不好提供了,下面介绍下一个增量打包工具 https://gitee.com/lpxs/ProjectPatch.git, 该工程是基于eclipse,针对文件的修改时间来拷贝增量class文件,可以配置时间范围以及输出目录,
一笠风雨任生平
2020/02/18
1K0
Debezium的增量快照
CDC(Change-Data-Capture)正被广泛应用于数据缓存、更新查询索引、创建派生视图、异构数据同步等场景,Debezium (https://debezium.io/) 作为 CDC 的代表项目之一,它收集数据库中的事务日志(变化事件)并以统一的事件流格式输出(支持「Kafka Connect」及「内嵌到程序中」两种应用形式)。
GreatSQL社区
2023/02/22
1K0
增量表全量表拉链表区别_hive 增量数据更新
2020-06-02首页和商详页又产生了2条访问数据,该两条即为2020-06-02新增的数据,表更新后,dt分区2020-06-02新增2条数据(标红),此时数据表如下:
全栈程序员站长
2022/11/03
2.6K0
增量表全量表拉链表区别_hive 增量数据更新
Debezium的增量快照
CDC(Change-Data-Capture)正被广泛应用于数据缓存、更新查询索引、创建派生视图、异构数据同步等场景,Debezium (https://debezium.io/) 作为 CDC 的代表项目之一,它收集数据库中的事务日志(变化事件)并以统一的事件流格式输出(支持「Kafka Connect」及「内嵌到程序中」两种应用形式)。
老叶茶馆
2023/02/18
1.5K0
Debezium的增量快照
Android Transform增量编译
这个文章的基础是你基本已经完成了简单的transfrom 的开发了,然后你碰到了编译速度慢的问题。 在Transform的抽象类中有一个isIncremental方法,这个方法就代表着是否开启增量编译。
逮虾户
2020/10/15
1.9K0
Android Transform增量编译
QEMU增量镜像制作
在服务器上,经常需要启动数十个或者几十个虚拟机,按照我们现有的方式是安装一个虚拟机,然后复制相应的份数。例如,一个虚机的镜像大小是4G,十个虚机的大小就需要占用40G空间。 事实上在目前为止里面还没有执行任何程序,这些空间都是分配,实际并不一定都要使用。那么是否能够实现用多少分配多少呢?分析下可以发现,每个虚拟机里面的内核都是一样的,大部分时候我们都不需要去修改里面的内核,是否能够共用内核? Copy-On-Write模式为我们提供了很好的解决方式,通过创建一个基础镜像(base image),里面把各个虚拟机都需要的环境都搭建好,然后基于这个镜像建立起一个个“增量镜像”(增量镜像的初始大小低于1M),每个“增量镜像”对应一个虚拟机,虚拟机对镜像中所有的改变都记录在“增量镜像”里面,基础镜像始终保持不变。这样我们建立十个虚拟机,需要的空间为:4G+10*1M=4G,一下节省了近36G的空间。
战神伽罗
2019/07/24
3.5K0
清华打造足球AI:首次实现同时控制10名球员完成比赛,胜率94.4%
观众朋友们大家好,您现在看到的是谷歌AI足球比赛的现场,场上身着黄色球衣的是来自清华大学的AI球员。
量子位
2021/11/16
5040
Facebook AI新架构:全景FPN,同时完成图像实例与语义分割 | 极客头条
实例分割和语义分割长期以来都是运用不同的神经网络架构来完成的,虽然最近出现了将语义和实例分割进行结合的“全景分割”,但经典方法仍将两者视为独立的任务。近日,Facebook AI 使用单一神经网络架构来同时完成实例分割(识别出图片前景中的人或者动物)和语义分割(对图片背景中的像素进行分类)。他们的研究则通过统一的神经网络架构来同时实现实例和语义分割,这一新架构实现了对内存和计算资源的高效利用,也可以作为全景分割任务的基准。
AI科技大本营
2019/05/07
6660
Facebook AI新架构:全景FPN,同时完成图像实例与语义分割 | 极客头条
html怎么使表格居中,html怎么使表格居中[通俗易懂]
margin 属性可以单独改变元素(元素可以是表格或者DIV)的上,下,左,右边距。也可以一次改变所有的属性。
全栈程序员站长
2022/11/04
11.9K0
html怎么使表格居中,html怎么使表格居中[通俗易懂]

相似问题

同时循环增量问题

32

增量和同时循环

30

Python同时变量增量

32

php增量同时循环

36

同时增加前增量和后增量或混合后增量

21
添加站长 进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

扫码加入开发者社群
关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

扫码关注腾讯云开发者公众号
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
查看详情【社区公告】 技术创作特训营有奖征文