Théorie des langages : Cours automates finis non déterministes
Télécharger PDFAutomates Finis Non Déterministes
M. Adil KENZI
1Théorie des langagesPlan Introduction Définition des Automates Non Déterministes
Transformation des automates non déterministes en des Automates Finis Déterministes
2Théorie des langages
Introduction Il est difficile de définir des automates finis déterministes reconnaissant des langages donnés, les automates non-déterministes simplifient cette tâche
Pour certains langages, on peut trouver un automate non-déterministe qui les reconnait et qui est plus petitque tout automate déterministe qui les reconnait.
3Théorie des langages
Automates finis non-déterministes NFA : NondeterministicFiniteAutomata
Définition
Un automate non-déterministe (NFA-
NondeterministicFiniteAutomata) A = <Q, , , q0 , F > est un automate qui présente la particularité suivante: Il possède une Fonction de transition étendue
: Q(Q)
Plus concrètement, plusieurs arcs reconnaissant le même caractère peuvent «sortir» du même état
4Théorie des langages
Définition
Un mot est accepté s’il est possible, en partant de l’état initial, d’atteindre un état final
en lisant le mot ; même s’il y a, en plus, des chemins qui mènent à des états non finaux, le mot est accepté.
C’est la même notion d’acceptation que pour
les automates finis déterministes. Sauf que pour
un automate non déterministe on peut trouver
plusieurs chemins avec le même mot (à cause de l’ambiguïté). 5Théorie des langages
Définition
Plus formellement, Soit M un automate fini non déterministe M = <Q, , , q0 , F >. soit w= xutel que x etu*
M accepte(ou reconnaît) le mot w= xussi(q 0
, xu) = ((q0 , x), u) F
Dans le cas contraire, on dit que l’automate refuse ou rejette la séquence.
6Théorie des langages
Définition
On dénote par L(M) l’ensemble des mots acceptés par M.
L(M) = { w */(q0 , w)F } On dit que L(M) est le langage reconnu (ou accepté) par M.
7Théorie des langagesExemple Soit l’automate non déterministe M décrit par le diagramme de transitions suivant:b s4 s0 s2 s3 s1 s5 s3 aa aa aa bb b
8Théorie des langages
Voici une suite de transition de l’automate non déterministe M décrivant l’acceptation du mot abbbaa. Les ensembles d’états contiennent tous les états accessibles à une étape donnée.
abbbaa{s0}
abbbaa{s1, s2}
abbbaa{s3, s5}
abbbaa{s4, s5}
abbbaa{s5}
abbbaa{s6}
abbbaa_{s2, s6}b s4 s0 s2 s6 s1 s5 s3 aa aa aa bb b
Mots acceptés par un NFA
Théorie des langages9
On peut aussi décrire l’acceptation de ce mot comme suit: {s0 } a {s1 , s2 } b {s3 , s5 } b {s4 , s5 } b {s5 } a {s6 } a {s2 , s6 }
Le mot est accepté car il existe une suite de transitions menant de l’état initial s0 à l’état final s6 . Une telle suite de transitions est s0 a s2 b s5 b s5 b s5 a s6 a s6 . Même si l’automate peut atteindre l’état non final s2 , en suivant un autre chemin, la séquence est acceptée. 10Théorie des langages
Mots acceptés par un NFA
La suite ci-dessous décrit du mot abbbbpar le même automate. Ce mot est rejeté car il n’y a pas
de suite de transitions correspondant à la séquence et menant
de l’état initial à un état final.
abbbb{s0}
abbbb{s1, s2}
abbbb{s3, s5}
abbbb{s4, s5}
abbbb{s5}
abbbb__{s5}b s4 s0 s2 s3 s1 s5 s3 aa aa aa bb b
11Théorie des langages
Motsrejetéspar un NFA
Exercice
Soit un automate M’ décrit par le diagramme de transitions suivant:AI HEF DC BG 11 111 111 11 00 00 00 00 12Théorie des langages
Vérifier si les mots suivants sont reconnus par l’automate M’ ci dessous: 1) 10000 2) 10011 3) 1101
10000{A}
10000{B, C}
10000{B, D, E}
10000{A, E, G, H}
10000{F, H}
10000_{H}AI HEF DC BG 11 111 111 11 00 00 00 00 13Théorie des langages
2. 10011
10011{A}
10011{B, C}
10011{B, D, E}
10011{A, E, G, H}
10011{B, C, G, I}
10011_{F, G, H}AI HEF DC BG 11 111 111 11 00 00 00 00 14Théorie des langages
3. 11011101{A} 1101{B, C}1101{F} 1101{}1101_{} AIHE FD CB G1 11 111 111 10 00 00 00 0
15Théorie des langages
Théorème
Pour tout automate fini non déterministe, il existe un automate fini déterministe qui accepte exactement le même langage
Preuve : on démontre ce théorème dans la séance des TDs
16Théorie des langagesExemple Construisons un automate fini déterministe qui reconnaît les mêmes séquences que l’automate non déterministe
<Q, , , q0 , F >où Q = {1, 2, 3},
= {a, b},
F = {3}.
17Théorie des langages3 21 ba ab La construction de l’automate fini déterministe se fait à partir
des résultats suivants:
Q’ = (Q) = {,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.
ne change pas.
est la fonction suivante, sachant que (, a) = (, b) =
({1}, a) = ({1}, b) = {2, 3}
({2}, a) = ({2}, b) =
({3}, a) = {1, 2}({3}, b) =
({1, 2}, a) = ({1, 2}, b) = {2, 3}
({1, 3}, a) = {1, 2}({1, 3}, b) = {2, 3}
({2, 3}, a) = {1, 2}({2, 3}, b) =
({1, 2, 3}, a) = {1, 2} ({1, 2, 3}, b) ={2, 3} 18Théorie des langagesq D0
= {q
0 } = {1}
F’ = {{3}, {1, 3}, {2, 3}, {1, 2, 3}} {2,3}{1}{1,2} { }{2}{1,3} {1,2,3}{3} ab aa aa aa bb bb bb ab 19Théorie des langages
Si on enlève les états qui ne peuvent pas être atteints:{2,3} {1}{1,2} { }a aab bb ab On peut voir que le langage que l’automate accepte est{b(ab) n
: nN}.
20Théorie des langages
Transformation d’un NFA en un DFA
Soit AN = <QN , , N , qN0 , FN > un automate non-déterministe (NFA), il existe un automate déterministe (DFA) AD = <QD , , D , qD0 , FD > tel que L(A
N )= L(AD )Q D (QN ) tous les éléments de (QN )seront accessibles depuis l’état initial de QD D (qD QD , a ) = q NQ D N(q N
, a) q
D0 = {qN0 }F D = {q Q
D | (q FN ) }
21Théorie des langages
Remarque (1/2)
Les langages reconnus par les automates finis non déterministes sont les mêmes que les langages reconnus par les automates finis déterministes.
Le nombre d’états augmente exponentiellement lorsqu’on transforme un automate non déterministe en automate déterministe.
22Théorie des langages
Remarque (2/2)
Un programme simulant un automate non déterministe doit
ou bien explorer les chemins possibles un à un en faisant des retours en arrière (peut être long).
ou bien construire l’automate déterministe correspondant (peut prendre beaucoup d’espace).
23Théorie des langages
Exercice
Construire un automate fini déterministe qui accepte les mêmes séquences que l’automate fini non déterministe ci-dessous.
L’alphabet est {a, b}.41 32 aa ab bb ba b
24Théorie des langages