Общая длина ввода в автоматы выдвижения, которые принимают пустой стек, является верхней границей на состояниях числа и символы стека

Question

Я проходил через классический текст "введение в теорию, языки и вычисления в автоматах" (3-е издание) Джеффри Уллмана, Джон Хопкрофт, Раджеев Мотвани , где я столкнулся с несколькими заявлениями о Town Automata (PDA), которые принимают пустой стек, как:

1. $ n $ , общая длина входа, безусловно, является верхней границей на количестве состояний и символов стека.

2. Одно правило может разместить почти n символов на стеке.

Следующие утверждения были сделаны, пока авторы собирались сделать некоторые заметки о свойствах принятия решений CFLS (свободные языки контекста)

Теперь вот некоторые очки, по которым я могу противоречить претензию, а не доказывать это правильно.

1. Предположим, $ n $ , - общая длина входа, но согласно дизайну КПК, возможно, это может принять то, что принять вход String Все состояния КПК не участвуют, поэтому, мы не можем сказать, что $ n $ - верхняя граница на количестве состояний PDA.

2. Хотя КПК принимает пустой стек, это может так произойти, что функция перехода добавляет больше, чем $ n $ Элементы в верхней части стека, Но в конце потребления $ n $ входных символов мы можем оставаться в конкретном состоянии и использовать переходы EPSILON, чтобы просто остаться в том же состоянии и поп-элементы из Стек, пока он не станет пустым. Так как мы можем сказать, что $ n $ - верхняя граница на номерах элементов на стеке? Мы приходим к противоречию ...

Я не понимаю, где я делаю ошибку, потому что то же самое заявления написаны в 3-м издании книги без каких-либо изменений, изготовленных из второго издания, что делает его верным, что утверждение правильное.

Я приложил соответствующую часть текста ниже:

Answer 1

Этот раздел не говорит о разборе. Алгоритмы сослались на алгоритмы преобразования между CFGS и КПК различных типов. Вопрос в том, как обычно, «какова вычислительная сложность алгоритма», а ответ, как обычно, выраженный с точки зрения размера ввода - к алгоритму . .

Вход в алгоритм, который преобразует КПК на CFG, является КПК, а размер входа - метрическая палка для сложности алгоритма - это размер * КПК ". Это то, что авторы намерены n быть.

Как один измеряет размер PDA? Простое: Вы пишете PDA в виде строки в некотором языке определения PDA и подсчитайте символы в описании. Это совершенно справедливая процедура, поскольку для того, чтобы позвонить алгоритму преобразования на КПК, необходимо предоставить преобразователь вход, который представляет PDA.

Учитывая это определение, претензии вообще не удивительны. Каждое состояние и каждый символ алфавита должны присутствовать хотя бы один раз в описании PDA, поэтому размер, если это описание является верхним границей. Точно так же возможно, что большая часть описания КПК является описание единого правила, которое может выдвинуть почти генеракодицетагкод символы.