代码之家 › 专栏 › 技术社区 › user1501127

如果L={0^n1^n|n>0}是L^c(L的补码)正则的吗?

finite-automata theory computer-science

0

user1501127 · 技术社区 · 11 年前

我的老师说,如果L={0^n1^n|n>0},则补码是规则的。我认为不是。

有人能向我澄清吗?我认为如果L是不规则的,那么补码也是不规则的。

1 回复 | 直到 11 年前

1

3

templatetypedef 4 年前

非正规语言的补语从来都不是正规的。如果L是非正则的 ^c 则(L ^c ) ^c =L是规则的,是矛盾的。因此,L ^c 在你的例子中是不规则的。可以使用抽运引理或Myhill Nerode来证明这一点。

希望这有帮助!