Automates Automates à états finis

AutomatesAutomates à états fnisDamien NouvelLicence Informatique -L1Damien NouvelAutomates2 / 30Automates à états fnisPlan●Représentation des automates (FSA)●Défnition formelle (DFA)●Déterminisme du FSA (DFA / NFA / ε-NFA)●Équivalence DFA / NFA / ε-NFALicence Informatique -L1Damien NouvelAutomates3 / 30Automates à états fnisPlan●Représentation des automates (FSA)●Défnition formelle (DFA)●Déterminisme du FSA (DFA / NFA / ε-NFA)●Équivalence DFA / NFA / ε-NFALicence Informatique -L1Damien NouvelAutomates4 / 30Automates à états fnisReprésentation des automates (FSA)●Automate à états fnis●Finite State Automaton (FSA)●Machine abstraite, issue des travaux de A.

Turing●Éléments de l'automate●Une ensemble fni d'états possibles●Un ensemble fni de symboles en entrées●Une fonction de transition entre états●Représentations●Diagrammes de transition●Tables de transition●Notations formellesLicence Informatique -L1Damien NouvelAutomates5 / 30Automates à états fnisReprésentation des automates (FSA)●Diagrammes de transition●Représentation " graphique »●Graphe orienté étiqueté :-Noeuds : états de l'automate●Étiqueté par les noms des états (généralement qx : q1, q2, q3, )●État fnal : double cercle-Arcs orientés : transitions de l'automate●Étiqueté par les symboles (a, b, c, d, )●État initial : marqué par un arc sans noeud d'origineq1q2q3cdbaq4Licence Informatique -L1Damien NouvelAutomates6 / 30Automates à états fnisReprésentation des automates (FSA)●Diagrammes de transition (suite)●Pour la lisibilité, lorsque deux arcs de même orientation sont possibles entre deux noeuds, ils sont fusionnés (disjonction) :●Un arc peut " boucler » un état sur lui-même :●Des transitions peuvent partir de l'état fnal :aaba,bLicence Informatique -L1Damien NouvelAutomates7 / 30Automates à états fnisReprésentation des automates (FSA)●Diagrammes de transition (suite)●Les transitions correspondent à la concaténation●On " suit » les arcs pour voir quel langage est accepté :●Le langage n'est pas forcément fni :q1q2q3c,edbaq4aq1q2q3c,edaq4L = {ac, ae, bd, aad }baL = {ac, ae, aad, aabac, aabae, aabaad, aabaabac, aabaabae, aabaabaad }Licence Informatique -L1Damien NouvelAutomates8 / 30Automates à états fnisReprésentation des automates (FSA)●Diagrammes de transition (suite)●Peuvent être mis intuitivement (formellement aussi) en correspondance avec des expressions régulièresbdcaR = ab+cdR = ababR = ab*cacbR = a+ba,bLicence Informatique -L1Damien NouvelAutomates9 / 30Automates à états fnisReprésentation des automates (FSA)●Table de transitions●Équivalente à la représentation par diagramme de transitions●États en lignes, symboles en colonnes-Ligne de l'état initial marqué par une fèche →-Ligne de l'état fnal marqué par une étoile *●Contenu décrit les transitions depuis un état / symboleq1q3cdaq4baq2babcd→q1q2ØØØq2q3q2q4Øq3Øq1Øq4*q4ØØØØLicence Informatique -L1Damien NouvelAutomates10 / 30Automates à états fnisPlan●Représentation des automates (FSA)●Défnition formelle (DFA)●Déterminisme du FSA (DFA / NFA / ε-NFA)●Équivalence DFA / NFA / ε-NFALicence Informatique -L1Damien NouvelAutomates11 / 30Automates à états fnisDéfnition formelle (DFA)●Notations pour un automate " déterministe » (DFA)●Un ensemble fni d'états-Notation : Q = {q1, q2, q3 }●Un ensemble fni de symboles (alphabet)-Notation : Σ = {a, b, c, d }●Une fonction de transition qui prend en paramètre un état et un symbole et qui renvoie un état-Notation : δ(qi, a) = qj (" signature » δ : Q × Σ → Q)●Un état initial -Notation : q0 ∈ Q●Un ensemble d'états fnaux-Notation : F ⊆ QLicence Informatique -L1Damien NouvelAutomates12 / 30Automates à états fnisDéfnition formelle (DFA)●Automate à états fnis●Défni comme le quintuplet : A = (Q, Σ, δ, q0, F)●Défnition équivalente aux diagrammes et tables de transition●Repose sur la défnition de la fonction de transition δ, souvent défnie par extension (en listant les cas possibles)-La fonction peut renvoyer Ø (par ex. δ(q1, d) = Ø)●Défnition de la fonction de transition " étendue »-Fonction qui prend un mot en entrée et utilise δ de l'automate-Notation (α ∈ Σ*) : δ(qi, α) = qj (" signature » δ : Q × Σ* → Q)-Défnie récursivement par décomposition du mot w :●Si w = ε alors δ(qi, ε) = { qi }●Si w = x.a tels que et x ∈ Σ* et a ∈ Σ alors δ(qi, w) = δ( δ(qi, x) , a)Licence Informatique -L1Damien NouvelAutomates13 / 30Automates à états fnisDéfnition formelle (DFA)●Langage reconnu par un automate déterministe●Ensemble des mots tels que la fonction de transition étendue appliquée à l 'état initial et au mot conduit à un état fnal :-L(A) = { w ∈ Σ* | δ(q0, w) ∈ F }●Théorème de Kleene : par défnition, le langage reconnu par un automate à états fnis (NFA) est régulier (ou rationnel)●Avantages et limites des automates à états fnis (FSA)●Algorithmes rapides pour implémenter les FSA●Impossible de " compter » dans le cas général-Pas d'automate qui décrive un mot ayant autant de a que de b-Pas d'automate pour reconnaître une expression arithmétique bien formée (nécessité de recourir à des grammaires)Licence Informatique -L1Damien NouvelAutomates14 / 30Automates à états fnisPlan●Représentation des automates (FSA)●Défnition formelle (DFA)●Déterminisme du FSA (DFA / NFA / ε-NFA)●Équivalence DFA / NFA / ε-NFALicence Informatique -L1Damien NouvelAutomates15 / 30Automates à états fnisDéterminisme du FSA (DFA / NFA / ε-NFA)●Types d'automates●Automates à états fnis-FSA : Finite State Automata●Automates à états fnis déterministes-DFA : Determinist Finite state Automata●Automates à états fnis non-déterministes-NFA : Non-determinist Finite state Automata●Automates à états fnis non-déterministes avec possiblité de transitions ε (mot vide)-ε-NFA : Non-determinist Finite state Automata with ε transitions●Tous peuvent être représentés à l'aide des diagrammes de transition, tables de transition, notations formellesLicence Informatique -L1Damien NouvelAutomates16 / 30Automates à états fnisDéterminisme du FSA (DFA / NFA / ε-NFA)●Déterminisme : requiert que l'automate soit dans un état unique (" déterminé ») après avoir lu n symboles●Automates non-déterministes (NFA)●Non-déterminisme : l'automate peut-être dans plusieurs états, " simultanément » après avoir lu n symboles-Attention : un automate non-déterministe n'implique pas que l'on ne " sache » pas dans quels états il est (au contraire)●Particulièrement utile lorsque l'on ne sait pas " à l'avance » quel état fnal l'automate atteindra (hypothèses)-Facilité de représentation / programmation●GPS : une voiture se dirige vers Paris, mais on ne connaît pas la destination fnale (Orléans, Strasbourg)●Prédiction SMS : un utilisateur tape le début d'un mot, mais plusieurs hypothèses sont possibles pour le mot qu'il veut écrireLicence Informatique -L1Damien NouvelAutomates17 / 30Automates à états fnisDéterminisme du FSA (DFA / NFA / ε-NFA)●Fonction de transition d'un NFA●A partir d'un état et d'un symbole : plusieurs états possibles-Notation : δ(qi, a) = R ⊆ Q (" signature » δ : Q × Σ → Q*)●Par ex. δ(qi, a) = { qj, qk, ql }-Peut aussi être l'ensemble vide : δ(qi, a) = Ø●Diférence de représentations DFA / NFADFANFADiagramme de transitionsPour chaque paire (état, symbole), au maximum un arc sortantPossibilité de plusieurs arcs sortant par paire (état, symboles)Table de transitionsLes cases de la table contiennent un état ou ØLes cases de la table contiennent un ensemble d'étatsNotation formelleLa fonction de transition renvoie au maximum un étatLa fonction de transition peut renvoyer plusieurs étatsLicence Informatique -L1Damien NouvelAutomates18 / 30Automates à états fnisDéterminisme du FSA (DFA / NFA / ε-NFA)●Diférence de représentations DFA / NFA (suite)●Soit Σ = { a, b }, comment représenter un automate qui reconnaît tous les mots se terminant par ab ?q2aq0a,bq2aq0bbabbDFANFAab→q0q1q0q1q1q2*q2q1q0ab→q0{ q0, q1 }{ q0 }q1{ a }{ q2 }*q2ØØq1aq1aLicence Informatique -L1Damien NouvelAutomates19 / 30Automates à états fnisDéterminisme du FSA (DFA / NFA / ε-NFA)●Fonction de transition étendue d'un NFA●A partir d'un état et d'un mot, plusieurs états possibles-Fonction qui prend un mot en entrée et utilise δ du NFA-Notation (α ∈ Σ*) : δ(qi, α) = R ⊆ Q (" signature » δ : Q × Σ* → Q*)-De même, défnition récursive par décomposition du mot w :●Si w = ε alors δ(qi, ε) = { qi }●Si w = x.a tels que x ∈ Σ*, a ∈ Σ et R = δ(qi, x) alorsδ(qi, w) = ∪r ∈ R δ(r, a)ou (équivalent) : δ(qi, w) = ∪qj ∈ δ(qi, x) δ(qj, a)●Langage reconnu par un NFA●Mots w tels que δ(q0, w) contienne au moins un état fnal●L(A) = { w ∈ Σ* | δ(q0, w) ∩ F ≠ Ø }Licence Informatique -L1Damien NouvelAutomates20 / 30Automates à états fnisDéterminisme du FSA (DFA / NFA / ε-NFA)●Par ex. soit l'automate ci-dessous et w = baababbbabδ(q0, b) = {q0}δ(q0, ba) = ∪p ∈ {q0} δ(p, a) = δ(q0, a) = {q0, q1}δ(q0, baa) = ∪p ∈ {q0, q1} δ(p, a) = δ(q0, a) ∪ δ(q1, a) = {q0, q1}δ(q0, baab) = ∪p ∈ {q0, q1} δ(p, b) = δ(q0, b) ∪ δ(q1, b) = {q0, q2}δ(q0, baaba) = ∪p ∈ {q0, q2} δ(p, a) = δ(q0, a) ∪ δ(q2, a) = {q0, q1} δ(q0, baababbbab) = {q0, q2}donc δ(q0, baababbbab) ∩ F = {q2} ≠ Ø et w ∈ L(A)q2aq0a,bq1bab→q0{ q0, q1 }{ q0 }q1Ø{ q2 }*q2ØØLicence Informatique -L1Damien NouvelAutomates21 / 30Automates à états fnisDéterminisme du FSA (DFA / NFA / ε-NFA)●Automates avec transitions ε (ε-NFA)●Transition ε : transitions sur le mot vide → aucun symbole-La transition se réalise systématiquement●Facilité supplémentaire de représentation / programmation-Lorsque des parties sont " optionnelles »●Tout automate qui comporte une transition ε est non-déterministe (peut-être dans plusieurs états simultanément)●Par ex., les mots abc ou c :q3q0aq1q2cbεq3q0aq1q2cbcNFAε-NFALicence Informatique -L1Damien NouvelAutomates22 / 30Automates à états fnisDéterminisme du FSA (DFA / NFA / ε-NFA)●Fonction de transition d'un ε-NFA●Identique à celle du NFA, mais en tenant compte des transitions ε comme élément pour réaliser une transition-Le mot-vide ε n'est pas nécessairement un élément de l'alphabet Σ-Notation : δ(qi, a) = R ⊆ Q (" signature » δ : Q × Σ ∪ {ε} → Q*)●Fermeture (transitive) par transition ε●Fermeture transitive (clôture, algèbre) ≃ éléments que l'on peut atteindre en utilisant un opérateur donné récursivement●Défnition d'une fonction récursive " epsClos » :-Pour tout qi ∈ Q, qi ∈ epsClos(qi)-Pour tout qi ∈ Q, si δ(qi, ε) = R ⊆ Q alors R ⊂ epsClos(qi)●On " suit » toutes les transitions ε possibles, récursivementLicence Informatique -L1Damien NouvelAutomates23 / 30Automates à états fnisDéterminisme du FSA (DFA / NFA / ε-NFA)●Par ex. :●epsilonClosure(q0) = {q0}●epsilonClosure(q1) = {q1, q3}●epsilonClosure(q2) = {q2, q1, q3}●epsilonClosure(q3) = {q3}●epsilonClosure(q4) = {q4, q2, q1, q3}●epsilonClosure(q5) = {q5}q5q0aq2q1εbq3εq4aεabLicence Informatique -L1Damien NouvelAutomates24 / 30Automates à états fnisDéterminisme du FSA (DFA / NFA / ε-NFA)●Fonction de transition étendue d'un ε-NFA●Même approche que pour un NFA-Fonction qui prend un mot en entrée et utilise δ du ε-NFA-Notation (α ∈ Σ*) : δ(qi, α) = R ⊆ Q (" signature » δ : Q × Σ* → Q*)-Transitions tiennent compte des transitions ε avec epsClos-De même, défnition récursive par décomposition du mot w :●Si w = ε alors δ(qi, w) = epsClos(qi)●Si w = x.a tels que x ∈ Σ*, a ∈ Σ et R = δ(qi, x) alorsδ(qi, w) = ∪r ∈ R ∪ s ∈ δ(r, a) epsClos(s)ou (équivalent) : δ(qi, w) = ∪qj ∈ δ(qi, x) ∪ qk ∈ δ(qj, a) epsClos(qk)●Langage reconnu par un ε-NFA (comme pour NFA)●L(A) = { w ∈ Σ* | δ(q0, w) ∩ F ≠ Ø }Licence Informatique -L1Damien NouvelAutomates25 / 30Automates à états fnisDéterminisme du FSA (DFA / NFA / ε-NFA)●Par ex. :●δ(q0, a) = {q2, q1, q3}●δ(q0, b) = {q1, q3}●δ(q0, aa) = {q5, q4, q2, q1, q3} = δ(q0, ba) = δ(q0, aaa)●δ(q0, bb) = Ø●δ(q0, bab) = {q5} = δ(q0, baab) = δ(q0, aab) = δ(q0, aaab)q5q0aq2q1εbq3εq4aεabLicence Informatique -L1Damien NouvelAutomates26 / 30Automates à états fnisPlan●Représentation des automates (FSA)●Défnition formelle (DFA)●Déterminisme du FSA (DFA / NFA / ε-NFA)●Équivalence DFA / NFA / ε-NFALicence Informatique -L1Damien NouvelAutomates27 / 30Automates à états fnisÉquivalence DFA / NFA / ε-NFA●Les automates reconnaissent des langages●Représentation de l'automate plus ou moins " dense »●Distinction entre DFA, NFA et NFA-Fonctions de transitions-Nombre d'états atteints depuis un état en consommant un symbole●Le langage reconnu par un automate ne dépend pas des états de l'automate-Plusieurs automates possibles pour un même langage●Équivalence des automates (langages reconnus)●Automates DFA et NFA●Automates NFA et ε-NFALicence Informatique -L1Damien NouvelAutomates28 / 30Automates à états fnisÉquivalence DFA / NFA / ε-NFA●Équivalence DFA / NFA●Tout DFA peut-être considéré comme un NFA●Soit un NFA, N = (QN, ΣN, δN , qN0, FN)-Il existe un DFA, D = (QD, ΣD, δD, qD0 , FD) tel que L(D) = L(N)●Même alphabet (ΣD = ΣN), même état initial (qD0 = qN0)●On construit QD comme l'ensemble des sous-ensemble de QN-Par ex. si QN = {q0, q1} alors QD = {{q0}, {q1}, {q0q1} }●États fnaux FD : ceux qui sont construits avec un état fnal de FNFD = {qDi ∈ QD | {qNi ∈ qDi } ∩ FN ≠ Ø}●Fonction de transition δD de D qui, à partir d'un état de QD comme construction de QN renvoie vers une autre construction de QN :δD(qDi, a) = { ∪qNj ∈ qDi δN(qNj, a) }Licence Informatique -L1Damien NouvelAutomates29 / 30Automates à états fnisÉquivalence DFA / NFA / ε-NFA●Équivalence DFA / NFA (suite)●Preuve sur la longueur du mot w = x.a-Supposons que : δD(qD0, x) = δN(qN0, x) = Q-Par défnition du NFA :●δN(qN0, x.a) = ∪qNj ∈ δ(qN0, x) δ(qNj, a) = ∪qNj ∈ Q δN(qNj, a)-Et par construction du DFA :●δD(qDi, a) = { ∪qNj ∈ qDi δN(qNj, a) }●δD(qD0, x.a) = δD(δD(qD0, x), a) = δD(Q, a) = { ∪qNj ∈ Q δN(qNj, a) }-Alors δN(qN0, x.a) = ∪qNj ∈ Q δN(qNj, a) = δD(qD0, x.a)●Récursivité : le DFA et le NFA aboutissent aux mêmes états, mais dans le cas du DFA c'est " par construction »●Pour tout NFA, il est possible de construire un DFA qui reconnaîtra le même langage.Licence Informatique -L1Damien NouvelAutomates30 / 30Automates à états fnisÉquivalence DFA / NFA / ε-NFA●Équivalence NFA / ε-NFA●Tout NFA peut-être considéré comme un ε-NFA●Soit un ε-NFA, E = (QE, ΣE, δE , qE0, FE)-Il existe un NFA, N = (QN, ΣN, δN , qN0, FN) tel que L(N) = L(E)●Même alphabet (ΣN = ΣE)●On construit QN comme l'ensemble des sous-ensemble de QE●État initial construit qN0 = {epsClos(qE0)}●États fnaux FN : construits avec un état fnal de FEFN = {qNi ∈ QN | {qEi ∈ qNi } ∩ FE ≠ Ø}●Fonction de transition δN de N qui, à partir d'un état de QN comme construction de QE renvoie vers une autre construction de QE :δN(qNi, a) = { ∪qEj ∈ qNi ∪qNk ∈ δE(qNi, a) epsClos(qNk) }