我正在研究会员算法，我正在研究这个特定的问题，它说以下内容：
展示一个算法，给定任何常规语言 L，确定 L = L*
所以，我的第一个想法是，我们有 L*，它是 L 的 Kleene 星，并且要确定 L = L*，我们不能只说因为 L 是规则的，我们知道 L* 是根据定义说明常规语言家族在星闭合下是闭合的。因此 L 将始终等于 L*？
我觉得肯定还有很多东西，我可能缺少一些东西。任何帮助，将不胜感激。再次感谢。
问问题
1630 次
2 回答
6
因为 L 是正则的，所以我们知道 L* 是根据定义，它表明正则语言的家族在星闭包下是封闭的。因此 L 将始终等于 L*？
不Regular(L) --> Regular(L*)，但这并不意味着L == L*。仅仅因为两种语言都是常规语言并不意味着它们是相同的常规语言。例如，a*andb*都是常规语言，但这并不能使它们成为相同的语言。
的一个例子L != L*是语言L = a*b*，因此L* = (a*b*)*。该字符串abab是 的一部分，L*但不是 的一部分L。
就算法而言，让我提醒您，正则语言的概念是可以由 DFA 解析的 - 对于任何给定的 DFA，该 DFA 都有一个最佳缩减。
于 2010-10-13T06:02:50.313 回答
1
你所说的暗示是错误的。Kleene 星下的封闭性仅意味着 L* 再次是规则的，如果 L 是规则的。检查是否 L = L* 的一种可能性是计算两者的最小自动机，然后检查等价性。
于 2010-10-13T06:03:43.697 回答