automata - PDA 接受 a 多于 b 和 c 的语言

Question

我的问题类似于this一。我想知道是否存在一个 PDA，它以随机顺序接受包含 a、b 和 c 的任何单词，其中 a 的总量高于 b 的总量并高于 c 的总量，例如单词“abcacba”将被接受。

Answer 1

这不是上下文无关的语言。证明是通过上下文无关语言的泵引理来实现的。假设该语言是上下文无关的。然后，长度大于 p 的语言中的每个字符串都可以重写为 uvxyz，使得 |vxy| 0 并且对于每个自然数 k，u(v^k)x(y^k)z 也是语言中的字符串。现在，考虑字符串 [a^(p+1)][b^p][c^p]。有几种方法可以将其写为 uvxyz。让我们考虑子字符串 vxy 的所有可能情况:

1. vxy 的可泵送部分仅由 a 组成。向上抽气有效，但 k = 0 是一个有效的选择，向下抽气会失败，因为向下抽气会减少 a 的数量至少 1。
2. vxy 的可泵送部分由 a 和 b 组成:泵送会减少 a，但不会减少 c，这违反了要求。
3. vxy 的可泵送部分仅由 b 组成:泵送会使 b 的数量增加到高于 a 的固定数量，从而违反了要求。
4. vxy 的可泵送部分由 b 和 c 组成:泵送会增加 b 和 c 的数量，而不会改变 a 的数量，这违反了要求。
5. vxy 的可泵送部分仅由 c 组成:泵送会增加 c 的数量，而不改变 a 的数量，这违反了要求。

因此，无法将我们的单词写为 uvxyz，同时满足泵引理的要求，这是一个矛盾。因此，我们关于语言是上下文无关的假设被驳斥了。