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).
Comment montrer qu'un langage est algébrique ?
Un langage est dit algébrique s'il peut être en- gendré par une grammaire, c'est-à-dire s'il est égal à LG(S) pour une variable S d'une grammaire G.
Exemple 2.7.
Soit G la grammaire donnée à l'exemple 2.2.
Le langage LG(S) est égal à {anbn n ≥ 0} qui est donc un langage algébrique.- 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.
Chapitre 2 : Langages réguliers et Automates détats finis
Chapitre 4 : Automate fini déterministe et non déterministe
Construire lautomate pour le motif AAB
Analyse dalgorithme et génération aléatoire
Analyse dalgorithmes langages et automates
TD n 8 Automates finis
Corrigé des exercices
1 Automates finis déterministes
Automates Automates à états finis
AutomatesLangages rationnelsThéorie des Langages FormelsChapitre 2 : AutomatesFlorence LevéFlorence.Leve@u-picardie.frAnnée 2014-20151/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :de tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :Une histoire de toto de plusde tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :Une histoire de toto de plusde tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :Unehistoire de toto de plus de tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :Une_histoire de toto de plusde tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :Uneh istoire de toto de plusde tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :Une histoire de toto de plusde tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :Une histoire de toto de plusde tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :Une histoire de toto de plusde tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :Une histoire de toto de plusde tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :Une histoire de toto de plusde tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :Une histoire de toto de plusde tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :Une histoirede toto de plus de tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :Une histoire_de toto de plusde tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :Une histoired e toto de plusde tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :Une histoire detoto de plus de tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :Une histoire de_toto de plusde tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :Une histoire det oto de plusde tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :Une histoire de toto de plusde tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :Une histoire de toto de plusde tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsUn exemple déjà vuTexte en entrée :Une histoire de totode plus de tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférente2/38AutomatesLangages rationnelsÉléments d"un automate : étatsde tt o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférenteLes ronds = les étatsNommons-les!L"ensemble d"états =f1;2;3;4;5g3/38AutomatesLangages rationnelsÉléments d"un automate : états5t o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférentede t1 2 3 4Les ronds = les étatsNommons-les!L"ensemble d"états =f1;2;3;4;5g3/38AutomatesLangages rationnelsÉléments d"un automate : états5t o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférentede t1 2 3 4Les ronds = les étatsNommons-les!L"ensemble d"états =f1;2;3;4;5g3/38AutomatesLangages rationnelsÉléments d"un automate : transitions5t o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférentede t1 2 3 4Flèche entre deux états : une transitionEnsemble de transitions =f(1, t, 2), (1, o, 1), (2, o, 3), (2, t,2), (3, t, 4), (3, o, 1), (4, o, 5), (4, t, 2), (5, t, 3),(5, o, 1)g [f(q;a;1)jq2 f1;2;3;4;5g;a62 ft;ogg4/38AutomatesLangages rationnelsÉléments d"un automate : transitions5t o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférentede t1 2 3 4Flèche entre deux états : une transitionEnsemble de transitions =f(1, t, 2), (1, o, 1), (2, o, 3), (2, t,2), (3, t, 4), (3, o, 1), (4, o, 5), (4, t, 2), (5, t, 3),(5, o, 1)g [f(q;a;1)jq2 f1;2;3;4;5g;a62 ft;ogg4/38AutomatesLangages rationnelsÉléments d"un automate : état initial5t o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférentede t1 2 3 4Rond précédé d"une flèche : état initialIl peut y en avoir plusieurs (ou aucun)Ensemble d"états initial =f1g5/38AutomatesLangages rationnelsÉléments d"un automate : état initial5t o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférentede t1 2 3 4Rond précédé d"une flèche : état initialIl peut y en avoir plusieurs (ou aucun)Ensemble d"états initial =f1g5/38AutomatesLangages rationnelsÉléments d"un automate : état terminal5t o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférentede t1 2 3 4Rond suivi d"une flèche : état terminal (final/acceptation)Il peut y en avoir plusieurs (ou aucun)Ensemble d"états terminaux =f5g6/38AutomatesLangages rationnelsÉléments d"un automate : état terminal5t o t otlettre différente de t lettre différentede o et de tttlettre différente de tlettre différentede o et de tlettredifférentede t1 2 3 4Rond suivi d"une flèche : état terminal (final/acceptation)Il peut y en avoir plusieurs (ou aucun)Ensemble d"états terminaux =f5g6/38AutomatesLangages rationnelsAutomates5-uplet