[PDF] Automates Automates à états finis

View - Download Automates Automates à états finis

Previous PDF

Next PDF

Automates

Automates à états fnis

Damien Nouvel

Licence Informatique -L1

Damien NouvelAutomates

2 / 30Automates à états fnis

Plan ●Représentation des automates (FSA) ●Défnition formelle (DFA) ●Déterminisme du FSA (DFA / NFA / ε-NFA) ●Équivalence DFA / NFA / ε-NFA

Licence Informatique -L1

Damien NouvelAutomates

3 / 30Automates à états fnis

Plan ●Représentation des automates (FSA) ●Défnition formelle (DFA) ●Déterminisme du FSA (DFA / NFA / ε-NFA) ●Équivalence DFA / NFA / ε-NFA

Licence Informatique -L1

Damien NouvelAutomates

4 / 30Automates à états fnis

Repré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 formelles

Licence Informatique -L1

Damien NouvelAutomates

5 / 30Automates à états fnis

Repré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'origine q1q2 q3c db aq4

Licence Informatique -L1

Damien NouvelAutomates

6 / 30Automates à états fnis

Repré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 :aa ba,b

Licence Informatique -L1

Damien NouvelAutomates

7 / 30Automates à états fnis

Repré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 :q1q2 q3c,e db aq4 aq1q2 q3 c,e d aq4L = {ac, ae, bd, aad } b aL = {ac, ae, aad, aabac, aabae, aabaad, aabaabac, aabaabae, aabaabaad ... }

Licence Informatique -L1

Damien NouvelAutomates

8 / 30Automates à états fnis

Représentation des automates (FSA)

●Diagrammes de transition (suite) ●Peuvent être mis intuitivement (formellement aussi) en correspondance avec des expressions régulièresb dc aR = ab+cdR = abab

R = ab*cacbR = a+ba,b

Licence Informatique -L1

Damien NouvelAutomates

9 / 30Automates à états fnis

Repré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 / symbole q1 q3c d aq4 b aq2babcd →q1q2ØØØ q2q3q2q4Ø q3Øq1Øq4 *q4ØØØØ

Licence Informatique -L1

Damien NouvelAutomates

10 / 30Automates à états fnis

Plan ●Représentation des automates (FSA) ●Défnition formelle (DFA) ●Déterminisme du FSA (DFA / NFA / ε-NFA) ●Équivalence DFA / NFA / ε-NFA

Licence Informatique -L1

Damien NouvelAutomates

11 / 30Automates à états fnis

Dé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 ⊆ Q

Licence Informatique -L1

Damien NouvelAutomates

12 / 30Automates à états fnis

Dé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 -L1

Damien NouvelAutomates

13 / 30Automates à états fnis

Dé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 -L1

Damien NouvelAutomates

14 / 30Automates à états fnis

Plan ●Représentation des automates (FSA) ●Défnition formelle (DFA) ●Déterminisme du FSA (DFA / NFA / ε-NFA) ●Équivalence DFA / NFA / ε-NFA

Licence Informatique -L1

Damien NouvelAutomates

15 / 30Automates à états fnis

Dé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 formelles

Licence Informatique -L1

Damien NouvelAutomates

quotesdbs_dbs2.pdfusesText_2

[PDF] diagramme d'état transition exemple

[PDF] diagramme d'état transition exercice corrigé pdf

[PDF] diagramme d'état transition uml

[PDF] diagramme d'etat transition uml exercices corrigés

[PDF] diagramme d'état transition uml pdf

[PDF] diagramme détat transition exercice corrigé

[PDF] diagramme de clapeyron

[PDF] diagramme de gantt en ligne

[PDF] diagramme de gantt en ligne gratuit

[PDF] diagramme de gantt exemple

[PDF] diagramme de gantt exercice corrigé 3eme

[PDF] diagramme de gantt exercice et corrigé

[PDF] diagramme de gantt gratuit

[PDF] diagramme de gantt online

[PDF] diagramme de gantt pdf