1

我觉得在这里发布如此简单的问题就像一个白痴,但这个网站的知识库真是太棒了。感谢您的理解。

关于寻找正则表达式的最小泵送长度(关于正则语言的泵送引理)的问题:

正则表达式 R = 1011(在字母表 {0,1} 上)

不是这个字符串 ε(空字符串)和 1011 的唯一匹配项吗?

编辑-我一直在盯着太多的 kleene 明星。空字符串 ε 不是这种语言。

正则语言的属性表明,如果一种语言可以用有限自动机(或正则表达式)表示,那么它就是正则的,当然这个语言也可以用两者来表示。(而且这个问题显然让我相信语言是正常的)

但另一方面,抽水引理(非正式地)指出,所有常规语言都具有抽水长度,因此至少该长度的所有字符串都可以拆分为 xyz,其中 y 可以重复而不会影响结果。ε 不能按定义泵送,并且 1011 不能泵送(我不认为,这是问题)因为没有其他字符串匹配它,因此删除或添加 y 的实例将导致字符串不被接受/匹配。

我的逻辑错误在哪里?

第二次编辑-任何 p>4 的答案是否可以通过将 x 或 y 或 z 设置为 φ (空集)来抽取语言,当与任何东西连接时会导致空集?

4

1 回答 1

1

抽水引理对有限语言来说并不太有用。所有最终语言都是常规的-例如,在您的情况下,您可以将“泵送长度”设置为 4。在空洞的意义上,所有超过该长度的单词都可以被泵送:)

于 2010-09-15T16:33:36.877 回答