La lunghezza totale dell'input a un'automota a pressione che accetta mediante stack vuota è un limite superiore sui simboli del numero e dei simboli dello stack

Question

Stavo attraversando il testo classico "Introduzione alla teoria automatica, alle lingue e al calcolo" (3a edizione) di Jeffrey Ullman, John Hopcroft, Rajeev Motwani , dove mi sono imbattuto in poche affermazioni su A Pushdown Automata (PDA) che accetta da una pila vuota, come:

1. $ N $ , la lunghezza totale dell'ingresso, è sicuramente un limite superiore sul numero di stati e simboli di stack.

2. Una regola potrebbe posizionare quasi n simboli sullo stack.

Le seguenti affermazioni sono state fatte mentre gli autori stavano per fare alcune note sulle proprietà decisionali dei CFL (linguaggi gratis context)

Ora qui ci sono alcuni punti con cui sono forse in grado di contraddire il reclamo piuttosto che dimostrarlo corretto.

.

1. Supponiamo $ N $ , è la lunghezza totale dell'input, ma secondo la progettazione del PDA potrebbe quindi accadere per accettare l'input Stringa Tutti gli stati del PDA non sono coinvolti, così da questo non possiamo dire che $ N $ è un limite superiore del numero di Stati che il PDA.

2. Anche se il PDA accetta mediante pila vuota, potrebbe quindi accadere che una funzione di transizione aggiunga più di $ N $ elementi sulla parte superiore dello stack, Ma alla fine di consumare la $ N $ simboli di ingresso possiamo rimanere sul particolare stato e utilizzare le transizioni epsilon per rimanere solo nello stesso stato e pop gli elementi dal Pila finché non diventa vuoto. Quindi, come possiamo dire che $ N $ è un limite superiore sugli elementi del numero sulla pila? Arriviamo ad una contraddizione ...

Non capisco dove sto commettendo l'errore, perché le stesse dichiarazioni sono scritte nella terza edizione del libro senza modifiche apportate dalla seconda edizione che lo rende probabile che la dichiarazione sia corretta. Ho allegato la parte corrispondente del testo qui sotto:

Answer 1

Quella sezione non sta parlando di analizzare. Gli algoritmi riferiti sono algoritmi per la conversione tra CFG e PDA di diversi tipi. La domanda è, come al solito, "Qual è la complessità computazionale dell'algoritmo", e la risposta è, come al solito, espressa in termini di dimensioni dell'ingresso - all'algoritmo . .

L'ingresso a un algoritmo che converte un PDA in un CFG è il PDA e la dimensione dell'ingresso - la metrica per la complessità dell'algoritmo - è la dimensione del * PDA ". Questo è ciò che gli autori intendono n per essere.

Come si misura la dimensione di un PDA? Semplice: scrivi il PDA come una stringa in qualche lingua di definizione PDA e conta i simboli nella descrizione. Questa è una procedura completamente equa, perché per chiamare l'algoritmo di conversione sul PDA, è necessario dare al convertitore un input che rappresenta il PDA.

Dato che la definizione, le affermazioni non sono affatto sorprendenti. Ogni stato e ogni simbolo dell'alfabeto deve essere presente almeno una volta nella descrizione PDA, quindi la dimensione se tale descrizione è un limite superiore. Allo stesso modo, è possibile che la maggior parte della descrizione del PDA sia la descrizione di una singola regola, che potrebbe spingere quasi i simboli di n.