A duração total da entrada para um autômato Pushdown que aceita por pilha vazia é um limite superior nos estados do número e símbolos de pilha

Question

Eu estava passando pelo texto clássico "Introdução à teoria de autômatos, idiomas e computação" (3ª edição) por Jeffrey Ullman, John Hopcroft, Rajeev Motwani , onde me deparei com algumas declarações sobre Pushdown AutomatA (PDA) que aceita por pilha vazia, como:

1. $ N $ , o comprimento total da entrada, é certamente um limite superior no número de estados e símbolos de pilha.

2. Uma regra poderia colocar quase n símbolos na pilha.

As seguintes afirmações foram feitas enquanto os autores estavam prestes a fazer algumas notas sobre as propriedades de decisão dos CFLs (contexto livre idiomas)

Agora aqui estão alguns pontos pelos quais eu possivelmente sou capaz de contradizer a reivindicação em vez de comprá-lo correto.

.

1. suponha $ n $ , é o comprimento total da entrada, mas conforme o desenho do PDA pode acontecer que aceite a entrada String Todos os estados do PDA não estão envolvidos, por isso, por isso não podemos dizer que $ n $ é um limite superior no número de estados que o PDA possui.

2. embora o PDA aceite por pilha vazia, pode acontecer que uma função de transição adicione mais do que $ n $ elementos no topo da pilha, Mas no final em consome a $ n $ Símbolos de entrada, podemos ficar no estado específico e usar as transições de Epsilon para permanecer no mesmo estado e pop dos elementos do pilha até ficar vazia. Então, como podemos dizer que $ n $ é um limite superior nos elementos numéricos na pilha? Chegamos a uma contradição ...

Eu não entendo onde estou cometendo o erro, porque as mesmas declarações são escritas na 3ª edição do livro sem quaisquer alterações feitas a partir da segunda edição, o que torna provável que a declaração esteja correta.

Anexei a parte correspondente do texto abaixo:

Answer 1

Essa seção não está falando sobre a análise. Os algoritmos referidos são algoritmos para conversão entre CFGs e PDAs de diferentes tipos. A questão é, como de costume, "qual é a complexidade computacional do algoritmo", e a resposta é, como de costume, expressa em termos do tamanho da entrada - para o algoritmo . .

A entrada para um algoritmo que converte um PDA para um CFG é o PDA, e o tamanho da entrada - a vara métrica para a complexidade do algoritmo - é o tamanho do * PDA ". Isso é o que os autores pretendem n para ser.

Como se mostra o tamanho de um PDA? Simples: você escreve o PDA como uma string em algum idioma de definição do PDA e contam símbolos na descrição. Isso é um procedimento completamente justo, porque para chamar o algoritmo de conversão no PDA, é necessário dar ao conversor uma entrada que representa o PDA.

Dada a definição, as reivindicações não são de todo surpreendente. Todo estado e cada símbolo do alfabeto deve estar presente pelo menos uma vez na descrição do PDA, então o tamanho se essa descrição for um limite superior. Da mesma forma, é possível que a maior parte da descrição do PDA seja a descrição de uma única regra, que poderia empurrar símbolos quase n.