由空堆栈接受的推动自动机的输入的总长度是数字状态和堆栈符号的上限

Question

我正在经典的文本“介绍自动化的自动化理论，语言和计算”（第3版），Jeffrey Ullman，John Hopcroft，Rajeev Motwani ，我遇到了一些关于a的陈述按空堆栈接受的推动自动机（PDA），如：

1。 $ n $ ，输入的总长度肯定是状态和堆栈符号数的上限。

2。一个规则可以在堆栈上放置几乎n个符号。

提出以下陈述，而作者即将作出关于CFL的决策属性的注意事项（上下文免费语言）

现在这里有一些要点，我可能能够违反索赔，而不是证明它是正确的。

1. 假设 $ n $ ，是输入的总长度，但根据PDA的设计，它可能会发生接受输入字符串未涉及PDA的所有状态，因此我们不能说 $ n $ 是PDA具有的状态数量的上限。

2. 虽然PDA由空堆栈接受，但可能因此发生转换函数在堆栈顶部的转换函数添加超过 $ n $ 元素，但是在消耗 $ n $ 输入符号时，我们可以留在特定状态，并使用epsilon转换只能保持在同一个状态并从中弹出元素堆栈直到它变空。那么我们如何说 $ n $ 是堆栈上数字元素的上限吗？我们达到矛盾...

我不明白我在哪里犯了错误，因为在第3版的书中写了相同的陈述，没有任何来自第二版的变化，这使得该陈述是正确的。

我已附上下面的文本的相应部分：

Answer 1

那部分不是在谈论解析。该算法称为用于在不同类型的CFGS和PDA之间转换的算法。正如往常一样，问题是“算法的计算复杂性是什么”，并且像往常一样，以输入 - 对算法的大小表示。

将PDA转换为CFG的算法的输入是PDA，并且输入的大小 - 用于算法的复杂性的度量标准棒 - 是* PDA的大小“。这就是作者打算的意图 n 。

如何测量PDA的大小？简单：在某些PDA定义语言中将PDA输出写为字符串，并在说明中计算符号。这是一个完全公平的程序，因为为了调用PDA上的转换算法，必须为转换器提供代表PDA的输入。

鉴于该定义，索赔并不令人惊讶。每个状态和每个字母符号必须至少在PDA描述中存在一次，因此如果该描述是上限的大小。类似地，PDA的大多数描述是单个规则的描述，它可以推动几乎是n符号。