在给定任何常规语言L的情况下,展示一种确定L = L*的算法

Question

我正在研究会员算法,我正在研究这个特殊问题,其中说明如下:

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

所以,我的第一个想法是,我们有L*是L的Kleene星并且确定L = L*,我们不能只是说因为L是常规的,我们知道L*是根据定义指出的常规语言系列在星光关闭下关闭.因此L总是等于L*？

我觉得肯定还有很多东西,可能还有我想念的东西.任何帮助,将不胜感激.再次感谢.

Answer 1

由于L是常规的,我们知道L*在定义中表明常规语言族在星形闭合下是封闭的.因此L总是等于L*？

号Regular(L) --> Regular(L*),但这并不意味着L == L*.仅仅因为两种语言都是常规语言并不意味着它们是相同的常规语言.例如,a*并且b*都是正规语言,但是这并不能让他们同日而语.

一个例子L != L*是语言L = a*b*,因此L* = (a*b*)*.该字符串abab是其中一部分L*但不是其一部分L.

就算法而言,让我提醒您,常规语言的概念是可以由DFA解析的概念 - 对于任何给定的DFA,该DFA都有一个最佳减少.