Théorie des Langages, Analyse Lexicale, Analyse Syntaxique

3.2 Automates non déterministes 5q0 q1q 2100;1 FI G . 3.1 – Automate déterministe reconnaissant les entiers naturels en numération binaire. q0 q1q 2 ?100;10; 10; 1 FI G . 3.2 – Automate déterministe complet reconnaissant les entiers naturels en numération binaire.On notera par AFi le quintuplet(Vt; Q; i; F; T), ou plus simplement Asiiet F sont donnés sansambiguité dans le contexte.Un mot west reconnu par l’automate AFi s’il existe un calcul ditréussiissu de l’état initial iet terminant en état acceptant après avoir lu le mot w. On note par Lang (A )le langage des motsreconnus par l’automate A.Un langage reconnu par un automate est dit reconnaissable. On note parRec l’ensemble deslangages reconnaissables.Il est clair que l’ajout d’une poubelle ne change pas les mots reconnus.On a l’habitude de dessiner les automates, en gurant les états par des cercles, en indiquant l’étatinitial par une èche entrante, les états acceptants par un double cercle ou une èche sortante, et latransition de l’état qà l’état q0en lisant la lettre par une èche allant de qvers q0et étiquetée par . La gure 3.1 représente un automate (incomplet) reconnaissant le langage des entiers naturels enreprésentation binaire.L’automate obtenu reconnaît exactement le même langage si l’on convient que le nouvel étatpoubelle n’est pas acceptant. Ainsi, la gure 3.2 présente un automate complet reconnaissant lelangage des entiers naturels en représentation binaire.Si l’automate Aest complet, on pourra donc étendre l’application Taux mots, en posantT (q; u ) = q02 Q tel que qu! q0. On peut donc dans ce cas reformuler la condition d’acceptationdes mots comme u2 L ang(A )ssi T(i; u )2 F.3.2 Automates non déterministesDénition 3.5 Unautomate non-déterministe Aest un triplet (Vt; Q; T)où1. Vt est levocabulaire de l’automate ; J.-P. Jouannaud Université Paris Sud