Embed Size (px)
Citation preview
I.A. Session 2009/2010
E.P.S.I. Bordeaux – C.S.I.I – 2ème Année – Cours n°3
Définition• Un automate est un dispositif se comportant
de manière automatique, c’est-à-dire sans nécessiter d’intervention humaine.
• Un automate se défini par :– Un ensemble d’états,– Un système de transition entre les états.
Concrètement• Exemples d’automates:
– Une cafetière– Machine de Turing– Un tamagotchi– Un compilateur
Implémentation• Il existe plusieurs façons d’implémenter un
automate. Les plus courantes sont :– une matrice : l’automate est représenté par la
matrice d’adjacence de ses états. On multiplie une matrice des états actifs par cette dernière pour transiter entre les états.
– un graphe : Les sommets représentent les états, et les arcs les transitions. Cette solution permet de modéliser des automates plus complexes.
Classes d’automates• Automates à états finis :
– Déterministes : Chaque état dispose au plus d’une transition par symbole, i.e. on peut savoir quel était l’état précédent quel que soit l’état actuel de l’automate.
– Non déterministes : on peut transiter entre les états de plusieurs façons.
Classes d’automates• Automates à pile (Push Down Automata): il s’agit
d’automates à état fini auxquels on a adjoint de la mémoire sous la forme d’une pile (stack).
• Machines de Turing (Cf. Cours précédent).• Automates cellulaires : grille de cellules chacune
définie par un ensemble d’états qui évolue en fonction de l’état des cellules voisines. A chaque nouvelle unité de temps la même règle de transition est appliquée à toutes les cellules de la grille.
Optimisation• Optimiser ou minimiser un automate à états
finis consiste à calculer l’automate de fonctionnement identique avec le plus petit nombre d’état possible .
• Un automate optimisé est dit « sous forme canonique ».
• L’optimisation permet ainsi de déterminer l’égalité entre deux automates.
Langage et grammaire formels• Un langage formel (par opposition au langage
naturel) est mode d’expression défini par :– Un ensemble de mots… – …obéissant à des règles logiques strictes.
• Cet ensemble de règles est appelé grammaire formelle ou syntaxe.
• Une grammaire peut être représentée par un automate.
Exemple : le cadavre exquis
Vocabulaire• Symbole (ou Atome) : unité de sens qui a un effet
sur la machine.• Mot : chaine finie qui consiste en une
concaténation de symboles.• Alphabet : ensemble fini de symboles.• Langage : ensemble de mots formés de symboles
d’un alphabet donné. Un langage peut ou non être fini.
• Etoile de Kleene (*) : représente l’ensemble de toutes les chaînes possibles.
“We are continually faced with a series of great opportunities brilliantly disguised as insoluble problems.”
John W. Gardner
Authors:Ophir Paz ([email protected] )Geoffroy Vincens ([email protected])
