我需要证明一种给定的语言不是规则的，这行得通吗？ 该语言是字母表= {a,b,c}的M={a^m a^l c b^(m+l)|m,l in N}。证明： Be n in N arbitrary but firm. We choose the word w=a^(2n)cb^(2n) with w in M and |w|>=n.
浏览 32提问于2019-01-18得票数 0
3回答
我已经在谷歌上搜索了上下文敏感的pumping lemma，它似乎只对上下文无关的语言产生了结果。知道怎么回事吗？
浏览 30提问于2011-11-30得票数 4
回答已采纳
我知道反之亦然，如果L是正则的，那么L*在闭包下也是正则的。
我想，如果L*是正则的，那么L也是正则的，因为L*的子集应该是正则的，而L是那个子集的一部分。
浏览 3提问于2014-10-03得票数 4
利用pumping引理证明下列语言不是正则语言L= {an bm |n= 2m}
浏览 17提问于2020-05-31得票数 1
回答已采纳
一个语言L满足正则语言的pumping引理，并且下列关于L的语句的上下文无关languages.Which的pumping引理是真的？B.L必然是非正则的。我会澄清我有疑问的地方。如果L满足正则语言的pumping引理，则它不一定是正则的。上下文无关也是如此。所以它可以是常规的，也可以是非常规的。CFL或
浏览 3提问于2011-12-07得票数 2
回答已采纳
我必须证明L满足CFL的pumping引理。语言L不是上下文无关的，但满足上下文无关语言的pumping引理。设L为:l= {a^j b^k c^k d^k: j，k≥1}∪{b^j c^k d^l : j，k，l≥0}
我以前曾尝试过通过pumping引理来做证明，但我总是搞砸了。我希望有人能给我解释一下如何解决这个问题。我挣扎了很多。
浏览 9提问于2021-03-10得票数 0
1回答
我应该使用pumping引理或常规语言闭包，但我就是想不出解决这两个问题的办法。任何有洞察力的人都会非常感激。谢谢。对于下面的每种语言，证明它是正规的或非正规的：当涉及到数字1时，我的假设是给定语言的反向也必须是规则的。然后，我可以使用pumping<em
浏览 41提问于2017-07-14得票数 1
回答已采纳
我有一个关于正则语言的pumping引理的小问题-它是否足够好地证明，如果属于语言L的特定字符串不能被pumping，那么该语言是不规则的？例如-如果我选择L1的形式是a^nb^n (ab，aabb，aaabb...)我证明了字符串aabb不能被抽出，并且仍然是L1的一部分，那么我是否可以立即得出L1是不规则的结论？
干杯。
浏览 0提问于2010-11-14得票数 1
回答已采纳
Pumping引理定义(来自wiki)|y|≥1；|xy|所有i≥0，xyiz∈L的≤p这个自动机的数量是3，p应该是>=，但是只有接受这个自动机的字符串是，所以我选择，作为w，我可以分解3部分？
浏览 32提问于2015-04-17得票数 0
我不明白这个语句的pumping引理，有人能帮我吗？这是常规的还是非常规的？如果是，为什么?如果不是，为什么？
感谢所有人！！
浏览 3提问于2016-01-11得票数 1
这是一个证明语言不是正则语言的pumping引理:如果L是正则语言，则存在一个常量N，使得对于L中的每个z，使用|z|>=N，可以将z划分为三个子串(uvw=z)，使得：2)N必须小于或等于接受L.So的DFA的最小状态数才能应用泵浦引理我需要知道有多少个状态会有接受L.Is的最小DFA有一种方法可以知道有多少个状态会有倒退，所以有可能在不构建最小DFA的情况下知道最小状态数吗
浏览 1提问于2012-02-11得票数 0
回答已采纳
在“理论计算机科学主题”中，我指的是规则语言与非规则语言、pumping引理和语法等。我熟悉有限自动机和正则表达式在现实世界中的应用，但像这些其他主题给我带来了更多问题，因为我没有看到任何现实世界的应用。
浏览 1提问于2009-01-20得票数 19
回答已采纳
2回答
我能找到的每个引用都使用了这个例子：来展示两者之间的区别。我可以找到一个使用常规引理的例子来“反驳”它。我的问题是，奥格登引理是如何改变这一策略的？“标记”是做什么的？
谢谢!
浏览 42提问于2012-09-27得票数 7
回答已采纳
字母表"a，b，c“上具有相同数量的子串"ab”和"ba“的所有字符串的语言是否都是规则的？你有什么想法来解决这个问题吗？
浏览 6提问于2011-08-14得票数 4
回答已采纳
例如，让我们证明L= {0^n1^n |n≥0}是不规则的。要证明一种语言是不规则的，请证明以下任意一种：(1) | uviw | >= n (2) |v|≤1 (3) for all i≥0: uviw∈L使得|uviw|uviw n 让我们假设L是正则的，然后通过Pumping引理来遵循上面给定的规则。因此，通过such引理，存在u，v，w使得(1) - (3)成立。 我们证明了对于所有的u，v，w，(1) - (3)都不成
浏览 8提问于2020-01-29得票数 1
回答已采纳
云服务器
ICP备案
对象存储
腾讯会议
云直播
腾讯云开发者
