Scribd
Importer
21 vues2 pages

Document Ally

Les automates à piles déterministes (APD) sont un modèle de calcul qui utilise une pile pour stocker des informations, permettant de reconnaître certains langages contextuels. Ils se distinguent par leur déterminisme, où chaque état et symbole d'entrée n'ont qu'une seule transition possible. Les APD ont des applications dans la compilation et le traitement des langages de programmation, bien qu'ils aient des limitations par rapport aux automates non déterministes.

Transféré par

djuma.1215
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
21 vues2 pages

Document Ally

Les automates à piles déterministes (APD) sont un modèle de calcul qui utilise une pile pour stocker des informations, permettant de reconnaître certains langages contextuels. Ils se distinguent par leur déterminisme, où chaque état et symbole d'entrée n'ont qu'une seule transition possible. Les APD ont des applications dans la compilation et le traitement des langages de programmation, bien qu'ils aient des limitations par rapport aux automates non déterministes.

Transféré par

djuma.1215
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Les automates à piles déterministes (APD) sont un modèle de calcul utilisé en théorie des

automates et en informatique théorique. Ils sont une généralisation des automates finis qui,
en plus de leur état, utilisent une pile pour stocker des informations. Voici quelques
caractéristiques et concepts clés liés aux automates à piles déterministes :

### Caractéristiques des Automates à Piles Déterministes :

1. **État** : Un automate à piles déterministe a un ensemble d'états, dont un est l'état initial
et un ou plusieurs peuvent être des états finaux.

2. **Alphabet** : L'automate est défini sur un alphabet, qui est un ensemble de symboles
que l'automate peut lire.

3. **Pile** : L'automate dispose d'une structure de données appelée pile, qui permet de
stocker et de récupérer des informations de manière LIFO (Last In, First Out).

4. **Transitions** : Les transitions de l'automate déterminent comment il passe d'un état à un


autre en fonction du symbole lu et du symbole au sommet de la pile. Pour les APD, les
transitions sont déterministes, ce qui signifie qu'il n'y a qu'une seule action possible pour
chaque symbole et état donné.

5. **Détérminisme** : Dans un automate à piles déterministe, pour chaque état, symbole


d'entrée et symbole au sommet de la pile, il ne peut y avoir qu'une seule transition possible.
Cela le distingue des automates à piles non déterministes.

### Fonctionnement :

Un automate à piles déterministes fonctionne en lisant une chaîne de symboles (entrée), en


effectuant des transitions d'état basées sur l'état actuel, le symbole d'entrée et le contenu de
la pile, et en manipulant la pile (ajout ou suppression de symboles) tout au long du
processus.

### Langages Reconnaissables :

Les automates à piles déterministes sont capables de reconnaître un sous-ensemble de


langages contextuels, en particulier les langages qui peuvent être décrits par des
grammaires sans contexte (CFG) déterministes. Cependant, tous les langages contextuels
ne peuvent pas être reconnus par des APD. Par exemple, le langage {a^n b^n | n ≥ 0} peut
être reconnu par un APD, mais le langage {a^n b^n c^n | n ≥ 0} ne peut pas l'être.

### Applications :

Les automates à piles déterministes ont des applications en compilation, en traitement de


langages de programmation, et dans d'autres domaines où une structure de hiérarchie est
nécessaire.
En résumé, les automates à piles déterministes sont un modèle puissant pour le traitement
et l'analyse des langages, bien qu'ils aient des limitations par rapport à leurs homologues
non déterministes

Vous aimerez peut-être aussi