La longueur totale de l'entrée dans un automate déroulant qui accepte par pile vide est une limite supérieure des états numériques et des symboles de pile.

Question

Je parcourais le texte classique "Introduction à la théorie, aux langages et au calcul des automates" (3e édition) par Jeffrey Ullman, John Hopcroft, Rajeev Motwani, où je suis tombé sur quelques déclarations sur un automate pushdown (PDA) qui accepte par pile vide, comme :

1. $n$, la longueur totale de l'entrée, est sûrement une limite supérieure du nombre d'états et de symboles de pile.

2.Une règle pourrait placer près de n symboles sur la pile.

Les déclarations suivantes ont été faites alors que les auteurs étaient sur le point de prendre quelques notes sur les propriétés de décision des CFL (Context Free Languages).

Voici maintenant quelques points par lesquels je suis éventuellement en mesure de contredire cette affirmation plutôt que de la prouver.

1. Supposer $n$, est la longueur totale de l'entrée, mais selon la conception du PDA, il se peut que l'acceptation de la chaîne d'entrée n'implique pas tous les états du PDA, nous ne pouvons donc pas dire que $n$ est une limite supérieure du nombre d’états du PDA.

2. Bien que le PDA accepte par pile vide, il peut arriver qu'une fonction de transition ajoute plus que $n$ éléments en haut de la pile, mais à la fin en consommant le $n$ symboles d'entrée, nous pouvons rester sur l'état particulier et utiliser les transitions epsilon pour rester simplement dans le même état et extraire les éléments de la pile jusqu'à ce qu'elle devienne vide.Alors comment pouvons-nous dire ça $n$ y a-t-il une limite supérieure sur les éléments numériques de la pile ?On arrive à une contradiction...

Je ne comprends pas où je fais l'erreur, car les mêmes déclarations sont écrites dans la 3ème édition du livre sans qu'aucune modification ne soit apportée par rapport à la deuxième édition, ce qui rend probable que la déclaration soit correcte.

J'ai joint la partie correspondante du texte ci-dessous :

Answer 1

Cette section ne parle pas d'analyse.Les algorithmes mentionnés sont des algorithmes de conversion entre CFG et PDA de différents types.La question est, comme d'habitude, "quelle est la complexité de calcul de l'algorithme", et la réponse est, comme d'habitude, exprimée en termes de taille de l'entrée -- à l'algorithme.

L'entrée d'un algorithme qui convertit un PDA en CFG est le PDA, et la taille de l'entrée -- la mesure de la complexité de l'algorithme -- est la taille du *PDA".C'est ce que veulent les auteurs n être.

Comment mesurer la taille d'un PDA ?Simple:vous écrivez le PDA sous forme de chaîne dans un langage de définition de PDA et comptez les symboles dans la description.C'est une procédure tout à fait juste, car pour appeler l'algorithme de conversion sur le PDA, il faut donner au convertisseur une entrée qui représente le PDA.

Compte tenu de cette définition, ces affirmations ne sont pas du tout surprenantes.Chaque état et chaque symbole alphabétique doivent être présents au moins une fois dans la description du PDA, donc la taille de cette description est une limite supérieure.De même, il est possible que la majeure partie de la description du PDA soit la description d'une seule règle, ce qui pourrait pousser presque n symboles.