我正在努力解决以下问题。我应该使用pumping引理或常规语言闭包,但我就是想不出解决这两个问题的办法。任何有洞察力的人都会非常感激。谢谢。
对于下面的每种语言,证明它是正规的或非正规的:
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引理来证明它不是正则的,因此,原始语言是非正则的。这是一种有效的方法吗?
老实说,我不知道如何接近第二个。
发布于 2017-07-17 05:49:03
实际上2)是非常简单的。长度为8或更长的单词的正则表达式为
1001 · {0,1}^* · {all words of length 4 except 0010}
然后,你会想到所有符合定义的较短的单词,并使用联合。
对于1),如果你知道反转下的闭包,使用这个和泵浦引理。反转将c^k带到前面,如果你在这个块中执行,那么很明显你离开了语言。
否则,取补码并将其与b^+ c^+相交。你会得到
{a^m b^n c^k: m=1 AND (m<n OR n<k)}
这就是
{a b^n c^k: n<k }.
现在,您可以在b块内执行命令,以离开该语言。
https://stackoverflow.com/questions/45095865
复制相似问题