algorithm - 展示一种算法，确定是否 L = L*，给定任何常规语言 L

Question

我正在研究成员资格算法，我正在研究这个特定问题，该问题说明如下:

展示一种算法，给定任何常规语言 L，确定 L 是否 = L*

所以，我的第一个想法是，我们有 L*，它是 L 的 Kleene 星并确定是否 L = L*，我们不能只说因为 L 是正则的，所以我们根据定义知道 L* 是声明常规语言家族在星形闭合下是闭合的。因此 L 将始终等于 L*？

我觉得肯定还有很多东西，可能还有一些我遗漏的东西。任何帮助，将不胜感激。再次感谢。

Answer 1

since L is regular, we know L* is by definition which states that the family of regular languages is closed under star-closure. Therefore L will always be equal to L*?

没有。 Regular(L) --> Regular(L*)，但这并不意味着 L == L*。仅仅因为两种语言都是常规语言并不意味着它们是相同常规语言。例如，a* 和 b* 都是常规语言，但这并不意味着它们是同一种语言。

L != L* 的一个例子是语言 L = a*b*，因此 L* = (a*b*) *。字符串 abab 是 L* 的一部分，但不是 L 的一部分。

就算法而言，让我提醒您，常规语言的概念是一种可以由 DFA 解析的语言 - 对于任何给定的 DFA，存在该 DFA 的单一最优缩减。