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

Question

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

标签： automataformal-languagespushdown-automaton

Answer 1

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

1. vxy 的可泵送部分仅由 a 组成。抽气有效，但 k = 0 是一个有效的选择，并且抽气失败，因为抽气会将 a 的数量减少至少一个。
2. vxy 的可泵送部分由 a's 和 b's 组成：泵送会减少 a's 而不会减少 c's，违反要求。
3. vxy 的可泵送部分仅由 b 组成：泵送会使 b 的数量增加至高于 a 的固定数量，违反要求。
4. vxy的pumpable部分由b和c组成：pump up会增加b和c的数量而不改变a的数量，违反要求。
5. vxy 的可泵送部分仅由 c 组成：泵送会增加 c 的数量而不改变 a 的数量，违反要求。

因此，在满足抽水引理的要求的同时，没有办法把我们的词写成 uvxyz，这是一个矛盾。因此，我们关于语言是上下文无关的假设被驳斥了。