25 févr. 2011

rappels d'Automates et Langages

Je poste ici un petit rappel de ce qu'on à vu au semestre 5 au sujet des Automates et plus particulièrement les automates...
Voici le graphe de résolution pour passer d'une forme à l'autre: Rappels al
astuce: on peut aussi utiliser Brzozowski pour minimiser un automate ! (càd renverser->déterminiser->renverser->déterminiser->tada !)
Qu'est ce qu'un automate ? c'est le quintuplet A = (Epsilon, Q, Lambda, q0, F) avec:
  • Epsilon l'alphabet
  • Q l'ensemble fini des états
  • Lambda l'ensemble des transitions
  • q0 l'état initial
  • F l'ensemble des états finaux
Qu'est ce qu'une grammaire ? c'est le quadruplet G = (N, T, P, A) avec:
  • N l'ensemble des symboles non terminaux
  • T l'ensemble des symboles terminaux
  • P l'ensemble fini des productions (ou règles)
  • A l'axiome (de départ)

Aucun commentaire: