我觉得在这里发布如此简单的问题就像一个白痴,但这个网站的知识库真是太棒了。感谢您的理解。
关于寻找正则表达式的最小泵送长度(关于正则语言的泵送引理)的问题:
正则表达式 R = 1011(在字母表 {0,1} 上)
不是这个字符串 ε(空字符串)和 1011 的唯一匹配项吗?
编辑-我一直在盯着太多的 kleene 明星。空字符串 ε 不是这种语言。
正则语言的属性表明,如果一种语言可以用有限自动机(或正则表达式)表示,那么它就是正则的,当然这个语言也可以用两者来表示。(而且这个问题显然让我相信语言是正常的)
但另一方面,抽水引理(非正式地)指出,所有常规语言都具有抽水长度,因此至少该长度的所有字符串都可以拆分为 xyz,其中 y 可以重复而不会影响结果。ε 不能按定义泵送,并且 1011 不能泵送(我不认为,这是问题)因为没有其他字符串匹配它,因此删除或添加 y 的实例将导致字符串不被接受/匹配。
我的逻辑错误在哪里?
第二次编辑-任何 p>4 的答案是否可以通过将 x 或 y 或 z 设置为 φ (空集)来抽取语言,当与任何东西连接时会导致空集?