标签: kleene-star

我在一本关于可计算性的书中读过这篇文章:

(Kleene定理)当且仅当它可以通过应用三个运算联合,连接,重复有限次数从有限语言获得时,语言是规则的.

我正在与"有限语言"斗争.

考虑这种语言: L = a*

它不是有限的.它是一个{0, a, aa, aaa, ...}显然是无限集(0=空字符串)的集合.

所以这是一种无限的语言,对吗？也就是说,"无限集"意味着"无限语言",对吧？

显然,这a*是一种常规语言.它是一种无限的语言.因此,通过Kleene的定理,它不能成为常规语言.矛盾.

我糊涂了.我想我不知道"有限语言"是什么意思.

以下正则表达式有什么区别？（a U b）*和（ab）*

联合与串联之间的区别？上面的哪个正则表达式可以接受其中“ a”始终在“ b”之前的字符串？

请澄清..在此先感谢。

我读到每个非确定性有限自动机（NFA）都可以转换为确定性有限自动机（DFA）。这可以为 kleene star regex 完成吗，比如 a* ？

以上是 a* 的 NFA。

大多数来源,例如http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html,表明Kleene闭包由4个节点构成.

为什么不能只用2来构建,如下所示？

(aa)*和之间会有区别(a*a*)吗？

有分配财产吗？

我已经根据给定的正则表达式制作了DFA，以匹配测试字符串。在某些情况下.*会发生这种情况。（例如.*ab）。假设现在计算机处于状态1。在DFA中，.*是指所有字符到其自身的过渡， 是指从状态1到a的另一过渡。如果测试字符串包含“ a”，则可能是过渡，因为从状态1开始，计算机可以进入两种状态，这在DFA中是不可能的。