如果语言 L 不规则,则为 L* 规则



假设L*不是规则是有意义的。但是,我找不到任何结论的证据。

假设 L 是字母 Σ 上的任何语言。如果 L 不是正则的,那么 L+Σ 也是正则的,但 (L+Σ(∗=Σ∗ 是正则的。所以你可以看到L*并不总是不规则的。

假设L={a^n , n=k! , k>=1} .如您所知,这种语言并不规则。但L*={a^m, m>=0} or L*(r)=a*,L*是一种常规语言。所以这个命题并不总是正确的。

如果 L 是非正则的,

L* 可以是正则的,也可以是非正则的,具体取决于语言 L。

设 L 为语言 {a^p | p 是质数}。L* 包含长度为 2 及以上的所有字符串,因为它包含字符串 aa 和 aaa 的所有线性组合。L* 是正则的,因为它是正则语言 a* 和 {a} 的集合差,而正则语言在集合差下闭合。

设 L = {a^n b^n | n> 0}。长度至少为 p 的 L* 字符串(其中 p 是抽水引理的抽水长度(是 a^p b^p。抽水只能改变 a 的数量,并且不能在语言中给我们另一个字符串,所以 L* 不是规则的。

注意一个有趣的事实:如果 L 是字母表上的一种语言,其中只有一个符号,则 L* 总是正则的。我举的第一个例子说明了为什么必须始终如此。

不一定,但有可能。假设 L 是 0、1、01、0011、000111、00001111等,L 不是规则的,但 L* 只是[01]*

最新更新