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

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

finite-automata theory computer-science

user1501127 · 技术社区 · 11 年前

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

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

1 回复 | 直到 11 年前

templatetypedef 3 年前

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

希望这有帮助!

推荐文章

asdhkjahjsdjkhjklasdhjhasDKJhl · 有没有办法检测c#中的鼠标侧键按下?

3 年前

Okonjo Mitchel · CS50凯撒:分段故障问题

3 年前

Baraa · 而我在java中得到无限的while循环

3 年前

Techy · 两个二维数组求和

3 年前

saas1990 · Python while循环和超时-寻找更好的解决方案

3 年前

Ashwani Sharma · 如果每种语言都是用其他语言写的,那么哪种语言位于最下面?[已关闭]

7 年前

deficiencyOn · 用DP求解“背包”

7 年前

Robbie · 使用嵌套的if-else语句理解Do-While循环

7 年前

Andrei · 查找两个数组中的差异[重复]

7 年前

Shkarik · 为什么我在Scala中的二进制搜索实现如此缓慢?

7 年前