Support de Cours Théorie des Langages et des Automates

Préparé par Moez Hammami

Chapitre I Alphabet et langages .............................................................................................. 3

I.1 Définition: Alphabet ......................................................................................................... 3

I.2 Définition: Mot ................................................................................................................. 3

I.3 Opérations sur les mots ..................................................................................................... 3

I.4 Définition: Langage. ......................................................................................................... 4

Chapitre II Représentation finie des langages......................................................................... 6

II.1 Définition: Langages formels ........................................................................................ 6

II.2 Expressions régulières .................................................................................................... 6

II.2.1 Exemples Introductifs.............................................................................................. 6

II.2.2 Définition d'une expression régulière ...................................................................... 7

II.3 Langages réguliers ........................................................................................................... 8

II.3.1 Théorème (Langages réguliers) ............................................................................. 8

II.3.2 Propriétés des langages réguliers........................................................................... 8

II.4 Exercices.......................................................................................................................... 9

Chapitre III Automates à états finis...................................................................................... 10

III.1 Introduction ................................................................................................................. 10

III.2 Définition d'un automate à l'état fini déterministe ...................................................... 10

III.3 Fonctionnement d'un automate à état fini .................................................................... 12

III.3.1 Définition d'une configuration .............................................................................. 12

III.3.2 Définition d'un langage connu par un automate.................................................... 13

III.4 Représentation graphique d'un automate à états fini.................................................... 14

III.5 Exemples de DFA ........................................................................................................ 14

III.6 Automate à état fini complet ....................................................................................... 16

III.7 Automates finis non déterministes (NFA) ................................................................... 17

III.8 Algorithmes de conversion........................................................................................... 18

III.8.1 Algorithme de déterminisation ou transformation NFA(cid:1)DFA ........................... 18

III.8.2 Algorithme de transformation d'une expression régulière en un NFA.................. 20

III.8.3 Automate déterministe minimal ............................................................................ 23

III.9 Simulation d'un Automate à états finis non déterministe............................................. 27

III.10 Lemme de pompage ................................................................................................... 28

Chapitre IV Les langages à contexte libre (Context Free Languages).................................. 30

IV.1 Introduction par un exemple ........................................................................................ 30

IV.2 Définition d'une Grammaire hors contexte .................................................................. 31

IV.3 Définition d'une Dérivation.......................................................................................... 31

IV.3.1 Dérivation gauche ................................................................................................. 31

IV.3.2 Dérivation droite ................................................................................................... 32

IV.4 Arbre syntaxique (Parse Tree) ..................................................................................... 33

IV.5 Grammaires ambiguës.................................................................................................. 34

IV.6 Exemples de grammaires ............................................................................................. 35

IV.7 Classification de chomsky ........................................................................................... 37

IV.7.1 Grammaires contextuelles « context-sensitive » ou de type 1(CG)...................... 37

IV. 7.2 Grammaires non contextuelles « context-free » ou de type 2 (CFG) ................. 38

IV. 7.3 Grammaires Régulières ou de type3 :RG ........................................................... 38

IV.8 Classification des langages formels ............................................................................. 39

IV.9 Transformation d'une grammaire régulière à droites en NFA .................................... 39

IV.10 Transformation d'un DFA en grammaire régulière.................................................... 40

Chapitre V Automates à pile (Push Down Automaton, PDA)................................................. 42

V.1 Introduction ................................................................................................................... 42

V.2 Définition d'un automate à pile ..................................................................................... 43

V.3 Définition d'une transition ............................................................................................. 44

V.4 Langages reconnus par un PDA .................................................................................... 44

V.5 Définition: langage reconnu par un automate à pile vide.............................................. 45

V.6 Déterminisme ............................................................................................................... 47

V.7 Transformation d'une grammaire hors contexte en PDA .............................................. 49

V.8 Propriétés de clôture ...................................................................................................... 50

V.11 Clôture des langages hors contexte (intersection et complémentation) ...................... 52

Bibliographie............................................................................................................................ 52

Chapitre I Alphabet et langages

I.1 Définition: Alphabet

L'alphabet est un ensemble fini de symboles, noté en général par ∑

Exemple 1: l'alphabet latin ∑={a,b,c………,z}

Exemple 2: l'alphabet binaire ∑={0,1}

Exemple 3: ∑={rouge, noir, 0,1,A}

I.2 Définition: Mot

Un mot ou une chaîne est une séquence de symboles pris de l'alphabet.

Exemple 1: ω1= voiture, ω2= voyage sont deux mots définis sur {a,b,c………,z}

Exemple 2: ω1=00101 ,ω2=101101 sont deux mots définis sur {0,1}

Exemple 3: ω1=rouge0noir ,ω2=10Arouge sont deux mots définis sur {rouge ,noir, 0,1,A}

La taille d'un mot notée |ω| est le nombre de symboles constituant le mot

Exemple 1: |voiture|=7 en considérant l'alphabet {a,b,c………,z}

Exemple 2: |00101|=5 en considérant l'alphabet {0,1}

Exemple 3: |rouge0noir|=3 en considérant l'alphabet {rouge ,noir, 0,1,A}

la chaîne vide notée ε est une chaîne de taille nulle : | ε | = 0.

Sous chaîne: x est une sous chaîne de ω ssi $

Préfixe: x est un préfixe de ω ssi $

Suffixe: x est un suffixe de ω ssi $

y tq ω=yx

Exemple x=voi est un préfixe de voiture car $

x=ture est un suffixe de voiture car $

y tq ω=xy

y= ture tq ω=voiture

y=voi tq ω=voiture

y, z (chaînes sur l'alphabet) tq ω = yxz.

Facteur: soient u, v, ω, t des mots définis sur Σ tq ω=uvt

si u=ε alors v est dit facteur gauche de ω (ou préfixe)

si t=ε alors v est dit facteur droit (ou suffixe)

si u=t=ε alors ω=εvε ω est donc un facteur de lui même

I.3 Opérations sur les mots

Concaténation: soient u, v deux mots définis sur Σ, tq u=xx2..xn , v= yy2..yn.

la chaîne ω concaténation de u et v notée ω=u.v = uv = xx2..xnyy2..yn.

Remarque: la concaténation est non commutative

Propriétés: |ω|=|uv|=|u|+|v|

la concaténation est associative :xyz=(xy)z=x(yz).

e est l'élément neutre pour la concaténation.

Occurrence d'un symbole dans un mot: c'est le nombre d'apparition du symbole dans le

mot.

Exemple:

|abbba|b=3

|abbab|b=3

Image (reverse): ω=aabab ωR=babaa

Exercice

Montrer par récurrence que (ωu)R=uR.ωR " k tq |u|=k

Preuve

Base: k=0, (ωx)R=(ωe )R=ωR= e ωR= xR.ωR

Hypothèse: on suppose que (ωx)R=xR.ωR "

Récurrence: on veut démontrer que (ωx)R=xR.ωR avec |x|=n+1

|x|=n+1 ⇒ x=u.a avec |u|=n et a ˛

(ωx)R=(ωua)R=a.(ωu)R=a.uR.ωR=(ua)R.ωR=xR.ωR

0<=k<=n , avec|x|=k

Donc l'hypothèse est vraie, c'est ce qu'il faut démontrer.

I.4 Définition: Langage.

Un langage est un ensemble de mots

Σ*={séquence de taille finie définie sur Σ}= fermeture de l'alphabet

C'est l'ensemble de toutes les séquences de tailles finies définies sur Σ

Exemple: Σ={a,b} => Σ*={ε, a, b, ab, ba, aa, bb, aaa, bbb, abb, ...}

Définition: un langage est un ensemble de mots appartenant à Σ* et qui vérifient une

propriété donnée => L={ω ˛

Σ*;ω a la propriété P}

Exemple: Σ={a,b}

L={ω ˛

Σ*, |ω|a=|ω|b}

L={ ε, ab, ba, aabb, baba, ………..}

l'ensemble des palindromes est défini par

L2={ ω ˛

L2={ε, aba , bab, a,b,……………………}

Σ* , ω=ωR }

Propriétés:

Σ* tq ω ˛

∑* est infinie est dénombrable

L1 ou ω ˛ L2}

L2={ω ˛

L=L1 ¨

L=L1 ∩ L2={ω ˛

L1 et ω ˛

Concaténation: L=L1·(cid:8)L2=L1L2={ω ˛

Fermeture de Kleene :

L*={ω ˛

L2 }

Σ* tq $

x, y tq ω = xy avec x ˛

L1 et y ˛

L2}

Σ* :ω=ω1ω2……………..ωк pour k≥0 et ω1,ω2,…………,ωк ˛

C'est à dire que si L est un langage (ensemble de mots) alors L* désigne l'ensemble de toutes

les chaînes de longueur finies formées par concaténation de mots de L, où chaque mot peut

être utilisé de 0 à n fois, et où la chaîne vide est aussi incluse.

Exemple

L={aa,b}

L*={ε, b, aa,bb,aab,baa,bbb,aaaa,aabb,baab,bbaa,bbbb,aaaab,aabaa,aabbb,baaaa,bbaab,bbbaa,

bbbbb,...}

Remarque:

˘ *= {e } „

˘ * est la répétition de 0 ou plusieurs fois de ˘

Exercice:

soit Σ = {0,1}

L = { ω ˛

Σ *: ω contient #0 „

#1 }

Montrez que L = Σ

L* ˝

Σ * par définition

L ⇒ Σ* ˝

on a Σ ˝

1 et 2 ⇒ L = Σ

Chapitre II Représentation finie des langages

II.1 Définition: Langages formels

C'est tout sous ensemble de ∑* dont les mots peuvent être définis de deux façons

conformément à:

Définition par propriété: il s'agit d'une modélisation formelle d'une description naturelle

d'un langage.

Exemple L1 = {ensemble des mots définis sur {a,b} de longueur paire}

L1 = {w

{a,b}* / |w

| = 2n avec n ‡

Définition récursive : Définition dans laquelle, un langage est défini sur lui même.

Exemple:

L2 = {w

L3= {w

L3 ”

˛ ∑* / w

= a ou w

=e ou w

= aw 1 ; w 1˛ L2} = {a,aa,..,aaaa,...}

= w 1w 2 avec |w 1|= 2 et w

L3}

II.2 Expressions régulières

II.2.1 Exemples Introductifs

Considérons le langage suivant:

L4 = { e , x, xx, xxx, xxxx,...}

Jusque là, on présente cet ensemble comme étant la fermeture d'un autre ensemble plus petit,

soit S = {x}

alors L4 = S*

On aurait pu écrire d'une façon plus courte

L4 = {x}*

On représente maintenant l'étoile de fermeture de Kleene appliquée non pas à l'ensemble mais

directement à la lettre x.

La simple expression x* va être utilisée pour indiquer une séquence quelconque qui peut être

vide de x. x* = e ou x ou xx ou xxx...

Donc on peut dire que L4 = langage (x) puisque x est n'importe quelle chaîne de x alors L4

est l'ensemble de toutes les chaînes possibles de x (incluant e )

Soit maintenant le langage L = { a, ab, abb, abbb, abbbb...}, on peut résumer ce langage en

français par " tous les mots de la forme : un a suivi par un nombre quelconque de b".

On peut noter L = langage (ab*). La signification est claire: c'est un langage dans lequel les

mots sont la concaténation d'un a initial avec un nombre quelconque de b (b*). On peut

appliquer l'étoile de Kleene à toute la chaîne ab si on veut, comme suit :

(ab)* = e ou ab ou abab ou ababab...

Remarque: Les parenthèses ne sont pas des lettres de l'alphabet de ce langage, alors elles

peuvent être utilisées pour indiquer la factorisation sans accidentellement changer les mots.

Le langage défini par l'expression ab*a est l'ensemble de toutes les chaînes de a et de b qui

ont au moins 2 lettres, qui commencent et finissent par a et qui n'ont que des b ou rien à

l'intérieur.

Langage (ab*a) = {aa, aba, abba, abbba, abbbba,...}

Remarque: il serait faux de dire que notre langage est l'ensemble de tous les mots qui

commencent et qui finissent par a et qui n'ont que des b (ou rien) entre eux, car cette

description peut être aussi appliquée au mot a. Notre symbolisme élimine cette ambiguïté.

Exemple: Le langage de l'expression ab contient toutes les chaînes de a et de b dans

lesquelles tous les a's viennent avant tous les b's.

Language (ab) = {e , a, b, aa, ab, bb, aaa, aab, abb, bbb,...}

Remarque: Il est à noter que ba et aba n'appartiennent pas à ce langage et on n'a pas besoin

du même nombre de a et de b. On observe aussi que ab „

(ab)*

Puisque le langage à droite contient abab tandisque celui à gauche ne le contient pas.

Exemple: soit le langage T défini sur l'alphabet ∑ = {a,b,c}

T = {a, c, ab, cb, abb, cbb, abbb, cbbb, abbbb, cbbbb...}

tous les mots de T commencent avec un a ou un c ensuite, ils sont suivis par un nombre

quelconque eventuellement nulle de b. symboliquement on peut écrire :

T = langage ((a¨ c) b*)

= langage (soit a ou c ensuite quelque b)

Exemple: soit L l'ensemble qui contient touts les chaînes de a et de b de longueur 3

exactement.

L = {aaa, aab, aba, abb, baa, bab, bba, bbb}

b) (a ¨

L = langage ((a ¨

toutes les chaînes de a et de b de n'importe quel longueur L = (a ¨

b) (a ¨

b)*

b)) alors si on veut représenter L', le langage qui contient

II.2.2 Définition d'une expression régulière

Une expression régulière sur un alphabet ∑ est une chaîne de caractères sur l'alphabet ∑

¨ {(,),¨

,*, ˘

toute lettre de ∑ ¨ {˘

, e } est une expression régulière

, e } tel que:

si r1 et r2 sont deux expressions régulières alors

(r1) est une expression régulière

r1r2 est une expression régulière

r1¨

r1* est une expression régulière

r2 est une expression régulière

rien d'autre n'est expression régulière

Exemple: soit ∑={a,b}

L = {w

˛ ∑*, w

contient la sous chaîne aa}

= aa

aaa

...........................................aa......................................

n'importe quelle chaîne de

a et de b

n'importe quelle chaîne de

a et de b

R = (a ¨

b)* aa (a ¨

b)*

Exemple: soit ∑={a,b}

˛ ∑*, w

L = {w

ne contient pas 3b consécutifs}

b ¨

bba)* (e ¨

bb)

ba ¨

R = (a ¨

II.3 Langages réguliers

II.3.1 Théorème (Langages réguliers)

Un langage L est dit régulier si et seulement s'il existe une expression régulière qui le génère.

II.3.2 Propriétés des langages réguliers

Etant donné deux langages réguliers L1 et L2

P1) L1 ¨

L2: définit un langage régulier

P2) L1.L2 est un langage régulier

P3) L1* est un langage régulier

P4)

1L est un langage régulier

est un langage régulier

_____

1 LL

L2 =

P5) L1 ˙

Définition Deux expressions régulières a

Exemple: a ¨

a.˘

= ˘

˘ * = {e }

= a

et b

sont dites équivalentes ssi L(a ) = L(b )

Exemple: Le langage de tous les mots qui ont au moins 2 a's peut être décrit par l'expression

(a¨ b)a(a¨ b)a(a¨ b)*

(quelque a et b au début) (le premier a) (quelque a et b au milieu) (le deuxième a ) (quelque a et b à la fin)

une autre expression peut dénoter le même langage

baba(a ¨

b)*

On passe par un nombre arbitraire (éventuellement nulle de b) jusqu'à ce qu'on trouve le

premier a, ensuite encore des b's, ensuite le deuxième a, ensuite on termine par une suite

quelconque de a et b.

On peut noter: (a¨ b)a(a¨ b)a(a¨ b) = bab*a(a ¨

b)*

II.4 Exercices

contient exactement bbb}

contient la sous chaîne bbb}

contient seulement 3b, le reste c'est des a's}

Exercice 1: Donner les expressions régulières qui génèrent les langages suivants:

L1 = {w

L2 = {w

L3 = {w

L4 = {w

L5 = {w

L6= {{w

L6 = {w

L7 = {w

deux en même temps}

˛ {a,b}*, tel que w

{a,b}*, tel que w

contient un nombre de a divisible par 3}

ne contient pas 3b Consécultifs}

contient un nombre impaire de b}

contient un nombre paire de a}

contient la sous chaîne aaa ou la sous chaîne bbb mais pas les

avec:

Chapitre III Automates à états finis

III.1 Introduction

Un reconnaisseur pour un programme est un programme qui prend en entrée une chaîne x et

répond OUI si x est une chaîne du programme et NON dans le cas contraire.On compile une

expression régulière en un reconnaisseur en construisant un diagramme de transitions

généralisé appelé automate fini. Un automate fini peut être déterministe ou non-déterministe

(c.à.d. qu'on peut trouver plus d'une transition sortant d'un état sur le même symbole d'entrée).

III.2 Définition d'un automate à l'état fini déterministe

Un automate à état fini déterministe (DFA) est un modèle mathématique M(k,Σ,δ,s,F):

tel que:

k: l'ensemble des états de l'automate

Σ: l'alphabet des symboles d'entrée

δ: une fonction de transition qui fait correspondre à des couples état-symbole des états.

s: est un état qui est distingué comme un état de départ ou état initial.

F: un ensemble d'états distingués comme états d'acceptation, ou états finaux.

Remarque:

δ: fonction : K x Σ ﬁ

Exemple 1:

K ; (q,a) =p: Transition de q à p en lisant (reconnaissant ) le symbole a.

δ : (b) (θ)

soient Σ={b, θ}

q 1 q2 q4

K={q1, q2, q3, q4}

q 2 q3 q2

q 3 q4 q4

F={q3}

S={q1}

q 4 q4 q4

Cet automate peut être représenté comme suit:

b,q

Remarque:

Un automate à états fini peut être considéré comme un mécanisme de calcul sans mémoire.

Mot connu par un automate:

Formellement, on définit la fonction δ*(e, u) qui nous dit dans quel état on arrive en partant

de l'état e et on analysant la chaîne u.

-si u est la chaîne vide δ*(e, ε)=e

-si u commence par le symbole t suivi de la sous-chaîne ω:

δ=(e, tω)=δ(δ(e,t),ω)

une chaîne u est acceptée par l'automate M dont l'état initial est q0 si δ*(q0, u) appartient aux

état finaux de M.

Exemple 2:

Soit l'automate M de l'exemple 1

Est ce que ε est reconnu par l'automate?

δ*(q1, ε)=q1 ˇ

F donc ε n'est pas reconnu par M

état initial

Est ce que ω1 =bθθb est reconnue par l'automate ?

δ=(q1,b θ θ b)=δ(δ(q1, b),θθb)

= δ*( q2,θθb)

= δ*(δ(q2,θ),θb)

= δ*(q2,θb)

= δ*(δ(q2,θ), b)

= δ*(q2, b)

= δ*(δ(q2,b), e )

= δ*(q3,e )

=q3 ˛

F donc ωı= bθθb est reconnu par M.

Est ce que ω2= θbθb est reconnu par l'automate?

δ(q1, θbθb)=δ(δ(q1, θ), bθb)

= δ*( q4, bθb)

= δ*(δ(q4,b),θb)

= δ*(q4,θb)

= δ*(δ(q4,θ), b)

= δ*(q4, b)

=δ* (δ(q4,b),ε)

=δ*(q4,ε)=q4 ˇ

F donc ω2=θbθb n'est pas reconnu par M

III.3 Fonctionnement d'un automate à état fini

III.3.1 Définition d'une configuration

Une configuration est un triplet(x,q,v) avec x, v ˛

Σ* et q ˛

K où:

x: désigne la sous-chaîne du mot déjà traitée

q: est l'état courant

v: désigne la sous chaîne du mot restante à traiter

Remarque: le mot est xv

Exemple:

δ=(q1,bθb)=δ(q2,θb) car δ(q1,b)=q2

La configuration

(b, q2, θ b )

déjà lu

état courant restant à lire

Remarque: généralement on travaille avec seulement l'état courant, et le restant à lire:

γі=(q, v)

état courant

restant à lire

Configuration successeur:

Soit γі(x, qі, v)

γј(x', qј , v') est une configuration successeur de γi

ssi

pour v=ε , γj=γi on dit que γi n'a pas de configuration successeur

-pour v=av"

x'=xa

qj=δ(qi,a)

v'=v"

configuration initiale:

notée γ0=(ε, q0,ω) avec q0: état initial;

ω: le mot à reconnaître

Configuration initiale d'acceptation:

γf=(ω, qF, ε) avec qF ˛

F; ω est le mot à reconnaître .

Configuration finale de non acceptation: γf = (ω,qF,ε) avec qF ˇ

Configuration successeur après n transitions

Notation:

γ ⊢

γ'

γ' est la configuration successeur de γ après n étapes de transition

ssi

Notation:

-γ'=γ pour n=0

γ" / γ ⊢ γ" et γ'' ⊢n-1 γ' pour n„ 0

configuration successive d'un nombre

quelconque d'états de transition

γ ⊢

γ' ssi $

k tq γ ⊢

γ'

III.3.2 Définition d'un langage connu par un automate

Notation L(M)

Soit M: Automate a état fini { Σ, K, q0, δ, F}

Le langage connu(accepté) par M est noté L(M) est l'ensemble

L(A)={ω ˛

Σ*/(ε, q0, ω) ⊢

(ω, qF, ε ) avec qF ˛

Exemple:

M=( K, Σ, δ, s, F) avec Σ={a, b}

K={q0, q1}

s=q0;F={q0}

δ a b

q0 q0 q1

q1 q1 q0

(q0,ababa) ⊢ (q0,baba)

⊢ (q1,aba)

⊢ (q1,ba)

⊢ (q0,a)

⊢ (q0,e )

q0 est un état d'acceptation ⇒ ω = ababa est accepté par M.

(q0, aba) ⊢ (q0,ba) ⊢ (q1, a) ⊢ (q1, e )

q1 ˇ

F ⇒ ω1 = aba n'est pas accepté.

III.4 Représentation graphique d'un automate à états fini

état

Remarque

transition sur le symbole a

état initial

état final ou d'acceptation

un automate à états fini déterministe (DFA) est un cas particulier d'automate à états fini dans

lequel:

Aucun état n'a de ε-transition, c'est à dire de transition sur l'entrée ε et

Pour chaque état q et chaque symbole d'entrée a, il y'a au plus un arc étiqueté a qui quitte q

III.5 Exemples de DFA

L(M) = { ω ˛

{a,b}: ω contient un nombre pair de b} (ababa)*

L = Σ = (a¨ b) = (a¨ b)*

remarque: q0 est à la fois état initial et

état final

{a,b}* / w

L = { w

R = (a¨ ba¨ bba)* (e

b¨ bb)

ne contient pas la sous chaîne bbb}

a,b

état mort

L = {w

{a,b}*, w

= bbb} = {bbb}

a a

a,b

L= {w

{a,b}*, w

contient un nombre pair de a et un nombre paire de b}

a paire,

b paire

a impaire,

b paire

a paire,

b impaire

a impaire,

b impaire

remarque: Il suffit de changer la place de

l'état d'acceptation pour obtenir:

a impaire, b paire: q1

a impaire, b impaire: q2

a paire, b impaire: q3

Σ={0,1,2,3,4,5,6,7,8,9}

L = {w

Σ*: w

divisible par 3} : la somme des chiffres est divisible par 3

Remarque: On part de l'idée

chiffre mod 3 = 0 :{0,3,6,8}

chiffre mod 3 = 1 :{1,4,7}

chiffre mod 3 = 2 :{2,5,8}

0,3,6,9

2,5,8

1,4,7

2,5,8

0,3,6,9

L= {w

{a,b}*, w

contient (3k+1)b; k‡

III.6 Automate à état fini complet

Un automate à états fini déterministe est complet si et seulement si d est une fonction totale

sur Q x Σ.

C'est à dire de chaque état, il part exactement une flèche étiquetée par chacune des lettres de

l'alphabet Σ.

Exemple:

C = (Σ,Q, d , q0,F)

Σ = {0,1}

Q = {q0,q1,q2}

d = {(q0,0,q1), (q0,1,q0), (q1,0,q2), (q1,1,q2), (q2,0,q2), (q2,1,q2)}

q0 est l'état initial

F = {q1}

0,1

C accepte les mots du langage L(C) décrit par: 1*0

III.7 Automates finis non déterministes (NFA)

Un automate fini non déterministe est un modèle Mathématique qui consiste en (K, Σ, δ, S, F)

K : ensemble des états

Σ : Alphabet

δ: relation de transition

S : état initial

F : ensemble des états finaux

Le même caractère peut étiqueter deux transitions ou plus en sortie d’un même état et les arcs

peuvent- être étiquetés par e .

Exemple : la figure suivante représente le graphe de transition pour un NFA qui reconnaît le

langage (a¨ b)* abb

On voit bien qu'en sortie de l’état 0, on a deux arcs étiquetés a.

Remarque 1 : Dans un automate fini non déterministe (NFA) il peut y avoir le choix entre

plusieurs chemins lors de la lecture d’un mot.

Pour qu’un mot soit accepté, il suffit que ses lettres étiquettent un chemin d’un état initial à un

état final (même s’il y’en a d’autres ne menant pas à un état final, ou bien s’arrêtant en cours

de route)

Remarque 2 : un DFA est un NFA particulier

NFA DFA

III.8 Algorithmes de conversion

III.8.1 Algorithme de déterminisation ou transformation NFA(cid:1)(cid:1)(cid:1)(cid:1)DFA

Théorème : Pour chaque automate fini non déterministe correspond un automate fini

déterministe qui lui est équivalent.

Si un langage est reconnu par un automate, alors il est également reconnu par un automate

fini déterministe.

Algorithme NFA(cid:1)(cid:1)(cid:1)(cid:1)DFA

Soit A= (K, Σ, δ, q0, F,) un NFA, on construit l’automate B= (K’, Σ, δ’, q’0, F’), K’sera alors

un sous ensemble de P(K) l’ensemble des parties de K.

δ’ø

q’0 {q0} ¨

K’K’¨

q’0

pour tout q’ ˛

{q˛

K tel que (q0,e ,q) ˛

d } (e -fermeture(q0))

K’ non encore considéré faire

Pour tout a ˛

Σ faire

q " {y˛

K tel que $

x ˛ q' tq (x,e ,y) ˛

d } (Transiter(q',a))

Si q "≠ Ø alors

{z˛

q " {q"} ¨

δ’δ’¨

K’K’¨

{q"}

{(q’, a, q")}

K tel que $

y ˛ q" tq (y,e ,z) ˛

d } (e -fermeture(q"))

F’ {q’ tel que q’∩F≠Ø}

Exercice : Construire le DFA pour le NFA suivant.

Dans l’algorithme de détermination

e -fermeture (q) : Ensemble des états de l’NFA accessibles depuis un état q de l’NFA par des

e -Transitions uniquement (sous lecture).

e - fermeture (T) : Ensemble des états de l’NFA accessibles depuis un état q˛ T

Transiter(T,a): Ensemble des états de l'NFA vers lequel il existe une transition sur le symbole

a à partir d'un état q ˛

Dans l’exemple:

e - fermeture (0) = {0, 1, 2, 4,7}

Transiter({0,1,2,4,7},a} = {3,8}

e - fermeture ({3,8})= {1, 2, 3, 4, 6, 7,8}

Avant de voir le premier symbole d’entrée, N peut appartenir à n’importe lesquels des états de

l’ensemble e -fermeture(0) ou 0 est l’état de départ de N donc il peut-être dans T={0,1,2,4,7}

c’est l’état de départ du DFA.

Supposons que a est le prochain symbole d’entrée. Quand il voit a, N peut passer dans l’un

des états de l’ensemble Transiter (T, a)=Transiter ({0, 1, 2, 4,7}, a)= {3,8}

Quand on

l’un des

fermeture(Transiter(T,a)), après avoir lu le a, e -fermeture({3,8})={1,2,3,4,6,7,8}

e -transitions, N peut-être dans

autorise des

états

e -

Appliquons l’algorithme sur notre exemple

Etat de départ= e - fermeture (0)=A= {0, 1, 2, 4,7}

L’alphabet des symboles d’entrée est ici {a, b}. Donc on marque A comme considéré et on

calcule e -fermeture (Transiter(A,a))= e -fermeture({3,8})={1,2,3,4,6,7,8}=B

⇒ Dtran[A,a]=B.

On fait la même chose avec b, e -fermeture (Transiter(A,b))=e -fermeture ({5})={1,2,4,5,6,7}

⇒Dtran (A,b)=C={1 ,2 ,4 ,5 ,6 ,7}.

Nous continuons ce processus avec les ensembles actuellement non marqués B et C on atteint

finalement le point ou tous les ensembles qui sont des états du DFA sont marqués.

Les cinq différents ensembles que nous construisons réellement sont :

A= {0, 1, 2, 4,7}

B= {1, 2, 3, 4, 6, 7,8}

C= {1, 2, 4, 5,6 ,7}

D= {1, 2, 4, 5, 6, 7,9}

E= {1, 2, 4, 5, 6, 7,10}

L’état A est l’état de départ et l’état E est l’unique état d’acceptation car il contient un état

d’acceptation du NFA (10)

Voici la table de transition :

Etat Symbole d’entrée

III.8.2 Algorithme de transformation d'une expression régulière en un NFA

L’algorithme est dirigé par la syntaxe, car il utilise l’arbre syntaxique décrivant l’expression

régulière pour guider le processus de construction.

Algorithme

Construction d’un NFA à partir d’une expression régulière, ou construction de Thompson

Donnée : une expression régulière sur un alphabet ∑

Résultat: un NFA de N qui reconnaît L(r)

Méthode : on décompose d’abord r en ses sous expressions, puis, en utilisant les règles (1) et

(2) ci-dessous, on construit des NFA pour chacun des symboles de base de r, c’est-à-dire soit

ε soit les symboles de l’alphabet.

Remarque : si un symbole a apparaît plusieurs fois dans r, un NFA séparé est construit pour

chaque occurrence.

Ensuite en se guidant par l’arbre syntaxique dans un parcours en profondeur, on combine

régulièrement ces NFA en utilisant la règle (3) ci-dessous, jusqu’à obtenir le NFA pour

l’expression régulière complète.

Règles de construction

1) Pour ε, construire le NFA

Ici i est un nouvel état de départ et f un nouvel état d’acceptation.

2) Pour a ˛

∑ construire le NFA

Ici encore, i est un nouvel état de départ et f un nouvel état d’acceptation.

3) Supposons que N(s) et N (t) soient les NFA pour les expressions régulières s et t.

a) pour l’expression régulière S ¨

T, construire le NFA composé suivant : N (s¨

N(S)

N(t)

Remarque : Les états de départ et d’acceptation de N(s) et N(t) ne sont pas les états de départ

et d’acceptation de N(s¨

t).

Remarque : tout chemin depuis i vers f doit traverser soit N(s), soit N(t) exclusivement, on

voit donc que l’automate composé reconnaît L(s) ¨

L(t)

b) pour l’expression st , construire l’NFA composé N(st) :

N(S)

N(t)

L’état de départ de N(s) devient l’état de départ du NFA composé et l’état d’acceptation de

N(s) est fusionné avec l’état de départ de N (t).

Toutes les transitions depuis l’état de départ de N (t) deviennent des transitions depuis l’état

d’acceptation de N(s). Le nouvel état fusionné perd son statut d’état de départ ou

d’acceptation dans le NFA composé.

c) pour l’expression régulière S, construire le NFA composé N(S) .

Ici i est un nouvel état de départ et f un nouvel état d’acceptation. Dans le NFA composé, on

peut aller de i à f directement en suivant un arc étiqueté ε qui représente que ε appartient à

(L(s))*, ou bien on peut aller de i à f en traversant N(s) une ou plusieurs fois.

d) Pour l’expression régulière (s), utiliser N(s) lui-même comme NFA.

Remarque Chaque fois qu’on construit un nouvel état, on lui donne un nom distinct. Ainsi il

ne peut y avoir deux états dans deux sous automates qui ai...