regular-language - 语言的补语 L={a^nb^n | n!=100}

Question

我不需要证明，因为这是一个客观的考试问题，只允许 2 分钟。选项是regular或cfl或csl。我不明白如何解决这个问题。

如果我们把它写成

(a^n b^n | n<100) UNION (a^n b^n | n>100)

现在调用第一部分 L1 和第二部分 L2，然后尝试使用，

De-morgons 定律 L'= L1' INTERSECTION L2'

考虑到我们只需要花 2-3 分钟的时间，我认为这不是正确的方法或快速的方法。有更好的方法吗？

Answer 1

这是正确的做法，L = {a^nb^n | n<100} 联合 {a^nb^n | n>100}

第一部分是常规的，第二部分是 DCFL。现在，L' = COMP({a^nb^n | n<100}) 相交 COMP({a^nb^n | n>100})

正则补码始终是正则补码，而 DCFL 补码始终是 DCFL，因此也是 CFL。

因此，Regular intersect CFL 给出 CFL。