regex - 常规语言(是或否)

Question

我的任务是检查这种语言是否是常规语言:

L = {w∈{a,b,c}* | where the number of a is less than the number of b+c.}

我既找不到正则表达式，也找不到确定性(或非)有限状态自动机。
另一方面，我没有找到任何方法来证明泵引理定理的相反情况。

有任何想法吗？

Answer 1

免责声明

我知道上面已经发布了使用抽水引理的正式证明。但是，我将寻求完全非正式的解释，因为我相信这通常有助于在寻求正式解决方案之前对问题有一些直觉。

一般直觉

一般来说，当一种语言依赖于某种计数时，它应该敲响它可能不规则的钟声。原因是计数可以变得任意大。您可以在示例中具体看到这一点。

为什么不正常？

想象一下尝试为您的语言创建 DFS。你关心的是a数量的区别和b个数的总和和 c (称之为 D_abc)。在 DFS 中，所有信息都在状态本身中捕获。例如，考虑连续读取 10 次后的状态 a和连续阅读100个后的一个a .这两个状态必须不同。现在，将此参数扩展为任意数量的 a (或等效的任何 D_abc )您可以得出结论，您需要无限数量的状态，即语言不是常规的。

奖励:为什么它是上下文无关的？

现在，考虑使用下推自动机。 PDA 允许您通过使用其(无限)堆栈来捕捉(无限)计数的难度。在您的示例中，您可以这样做:

如果堆栈为空(即 D_abc = 0 )，将遇到的任何符号压入堆栈(即，如果 a 出现 D_abc <- 1 ，否则如果 b 或 c 出现 |914|7)。

如果栈顶元素是 D_abc <- -1 (即 a > 0)，如果是 D_abc随之而来的是将其插入堆栈(即 a ，否则从堆栈中弹出顶部 D_abc <- D_abc + 1 (即 a )。

同样，如果顶部元素是 D_abc <- D_abc - 1或 b (即 c )，如果是 D_abc < 0或 b随之而来的是将其插入堆栈(即 c )，否则从堆栈中移除顶部元素(即 D_abc <- D_abc - 1 )。

使用上述规则，堆栈保持计数 D_abc <- D_abc + 1在每个时刻，这正是您需要接受或不接受字符串的内容。因此，您可以得出结论，该语言是上下文无关的。