^{PDFprof.com Search Engine}

Théorie des Langages Formels Chapitre 5 : Automates minimaux

Comment savoir si un automate est minimal ?
Proposition : Un automate déterministe complet est minimal si et seulement si pour tout couple d'états (p,q) il existe un mot qui sépare p et q.
Conséquence : Le résultat précédent donne un moyen de montrer qu'un automate est minimal.
Il suffit d'exhiber pour chaque couple d'état (p,q) un mot qui les sépare.
Quel est le langage accepté par l'automate ?
L'automate A×B accepte le langage L ∩ M.
Lors de la construction de l'automate produit il n'est pas nécessaire de considérer tous les états (tout le produit cartésien).
On peut se restreindre `a l'ensemble des états accessibles (voir l'exemple ci-dessous).
Quelle est la hiérarchie des automates ?
La hiérarchie de Chomsky connaît quatre types de grammaires et de langages : récursivement énumérable (type 0), contextuel (type 1), algébrique (type 2), rationnel (type 3).
La théorie des langages fournit une base conceptuelle et éventuellement des outils de production qui réduisent considérablement les coûts de production des modules « analyseur syntaxique » et « décompilateur ».
La définition rigoureuse des arbres abstraits manipulés facilite la conception du « cœur » de l'application.

Comment savoir si un automate est minimal ?