5

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

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

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

有任何想法吗？

4

1 回答 1

3

免责声明

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

一般直觉

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

为什么不规律？

想象一下尝试为您的语言创建 DFS。你关心的是 and 的数量和数量之a和b之间的差异c（调用 this D_abc）。在 DFS 中，所有信息都在状态本身中捕获。例如，考虑连续阅读 10 次后的状态a和连续阅读 100 次后的状态a。这两种状态必须不同。现在，将此论点扩展到任意数量a（或等效地 any D_abc），您可以得出结论，您需要无限数量的状态，即语言不是规则的。

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

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

  • 如果堆栈为空（即D_abc = 0），则将遇到的任何符号压入堆栈（即，如果a出现D_abc <- 1a ，否则如果出现or b）。cD_abc <- -1

  • 如果堆栈的顶部元素是a（即D_abc> 0），如果a出现将其压入堆栈（即D_abc <- D_abc + 1，否则从堆栈中弹出顶部a（即D_abc <- D_abc - 1）。

  • 类似地，如果顶部元素是bor c（即D_abc < 0），如果出现borc将其压入堆栈（即D_abc <- D_abc - 1），否则从堆栈中移除顶部元素（即D_abc <- D_abc + 1）。

使用上述规则，堆栈会D_abc在每一刻保持计数，这正是您需要接受或不接受字符串的情况。因此，您可以得出该语言是上下文无关的结论。

于 2011-12-10T13:08:03.713 回答