Comment savoir si un automate est fini ?
Un automate est déterministe si et seulement si les deux conditions suivantes sont vérifiées : 1.
L'automate possède un et un seul état initial ; 2.
Pour chaque état q et pour chaque lettre α, il existe au plus une transition issue de q d'étiquette α.Comment compléter un automate ?
Un automate fini et déterministe est complet si et seulement si δ est une application de Q × Σ sur Q.
De chaque état, il part alors exactement un arc étiqueté par chacune des lettres de l'alphabet Σ.
Quand la fonction n'est pas une application, l'automate fini peut se trouver bloqué.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.10.4.
1A = A1 ∪ A22Q = Q1 ∪ Q23I = I1 ∪ I24F = F1 ∪ F25μ = μ1 ∪ μ2
1 Automates finis déterministes
Automates Automates à états finis
AUTOMATES À ÉTATS FINIS
CH1 Automates finis
Cours : Théorie des Automates / Chapitre I Mots et Langages
Théorie des Langages Formels Chapitre 1
Théorie des langages
LIF15 – Théorie des langages formels
Langages formels
Université de Nice - Sophia Antipolis Licence Informatique 2Outils Formels pour l"Informatique 2012-2013TD n8Automates finis1 EchauffementExercice 1)Un automate déterministe est la donnée d"un quintupletfA;Q;I;T;goùAdésigne un alpha-bet,Ql"ensemble des états,Il"état initial,Tl"ensemble des états finaux (ou terminaux) et:QA7!Ala fonction de transition.
Préciser le quintuplet qui définit l"automate ci dessous.Comment compléter cetautomate avec un état puits, quel est le quintuplet correspondant à l"automate complet ?01243abbaababExercice 2)Même question que précèdemment avec l"automate suivant.
Déterminisez cet automate etdécrivez les quintuplets correspondants.01243abbaabaaExercice 3)Décrire un automate qui reconnait le langageLades mots sur l"alphabetfa;bgqui commen-cent paraet un automate qui reconnait le langageLbdes mots sur l"alphabetfa;bgqui terminent parb, enprenant soin de définir précisément les fonctions de transitions.1.Décrire un automate qui reconnait la réunion des lang agesLaetLb.2.Décrire un automate qui reconnait le lang ageLa.Exercice 4)Décrire un automate qui reconnait le langage des mots sur l"alphabetfa;bgqui sont delongueur strictement plus petite que4.Exercice 5)Construire, si possible, un automate fini reconnaissant chacun des langages suivants :11.les représentations binaires des nombres pairs (sans 0 inutile en tête) ; 2.les mots de longueur impaire ; 3.les mots de longueur congrue à 1modulo4;4.les représentations décimales des multiples de 3;5.les mots binaires qui ont un 1de plus que de0.
2) Exercices d"entrainementExercice 6)Pour chacun des langages réguliers suivants sur l"alphabetA=f0;1g, donner une expressionrégulière le décrivant puis construire un automate non-déterministe l"acceptant.
Enfin, déterminiser lesautomates obtenus, soit directement, soit en utilisant l"algorithme de déterminisation.1.les mots dont l"a vant-dernièrelettre est 1.2.les mots contenant le f acteur101.3.les mots qui commencent et se terminent par la même lettre.
Exercice 7)SoitLle langage des mots binaires se terminant par0ou bien ayant un nombre pair de1.1.T rouvezun automate non-déterminist equi accept eles mots de L, tel qu"il comporte un état finalpour chacune des deux variétés de mots.2.Appliquez-lui l"algorithme de déterminisation. 3.Donnez une e xpressionrégulière qui décri vece lang age.Exercice 8)Soit l"expression régulière suivanteEdécrivant le langage régulierL:(0 + 1)(00 + 11)(0 + 1)1.T rouverun automate fini reconnaissant le complémentaire du lang ageL, régulier lui aussi, en com-plétant un automate reconnaissant le langageLpuis en inversant les états finaux et non-finaux del"automate.2.T rouverun automate fini reconnaissant l"ensemble Pref(L)des préfixes deL, langage régulier égale-ment, à partir de celui reconnaissantL.
3) Pour aller plus loinExercice 9)SoitAun alphabet fini.L"ensemble des automates finis sur l"alphabetAvous parait-il dénom-brable ou pas, et pourquoi ?Exercice 10)Pour chacun des exemples d"expressions régulières de la feuille de TD 7, décrire l"automate(le cas échéant non déterministe puis déterministe) correspondant.2