Calculabilité - Décidabilité (LI347) [0.3cm] Cours no3

Stef Graillat

Informations

• Publié par: Vyom
• Nombre de lectures: 195
• Langue: Catalan

Extrait

Calculabilité - Décidabilité (LI347)
oCours n 3
Stef Graillat
Université Pierre et Marie Curie (Paris 6)
S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 1 / 30
Résumé du cours précédent
ε-transitions : elles permettent d’étendre un AFN en autorisant un
changement d’état en lisant une entrée vide (c’est-à-dire en ne lisant
aucun symbole). Les ε-AFN peuvent être convertis en AFD acceptant
le même langage.
Expression régulière : notation algébrique décrivant exactement les
mêmes langages que les automates finis. Les opérateurs sont l’union,
la concaténation et la fermeture.
Equivalence entre expressions régulières et automates finis : on peut
convertir un AFN en ER. On peut aussi convertir une ER en un ε-AFN.
S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 2 / 30AF et expressions régulières : Des AFD aux expressions
régulières et réciproquement
On a déjà montré les équivalences suivantes :
AFD ⇐⇒ AFN ⇐⇒ ε-AFN
On veut montrer que les langages définis par les ER sont exactement ceux
reconnus par les AFD.
Passage d’un AFD à une ER
Theorem3.4: ForeveryDFAA=(Q,!,!,q,F)Passage d’une ER à un ε-AFN. 0
there is a regex R, s.t. L(R)=L(A).
Proof: Let the states of A be {1,2,...,n},
S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 3 / 30
with 1 being the start state.
Des AFD aux expressions régulières(k)• Let R be a regex describing the set ofij
A = (Q,Σ,δ,q ,F) un AFD avec Q ={1,...,n}, q = 1.0 0labels of all paths in A from state i to state
(k)
R : l’expression régulière reconnaissant les mots w permettant de passerj going through intermediate states {1,...,k}ij
de l’état i à l’état j sans passer par un état intermédiaire de numéro
only.strictement supérieur à k.
i
j
k
S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 4 / 30
586
6
Des AFD aux expressions régulières (suite)
Calcul par induction
Base : k = 0 donc pas d’état intermédiaire.
Cas 1 : i = j
Si a ,...,a sont les symboles permettant de passer de i à j, alors :1 p
(0)
R = a +···+a1 pij
Cas 2 : i = j
Si a ,...,a sont les symboles permettant de passer de i à j, alors :1 p
(0)
R = a +···+a +ε1 pij
Remarque : S’il n’y a pas de symbole permettant de passer de i à j alors
(0)
Cas 1 : si i = j alors R =∅ij
(0)
Cas 2 : si i = j alors R = εij
S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 5 / 30
Des AFD aux expressions régulières (suite)
Induction : on montre que
(k) (k−1) (k−1) (k−1) (k−1)?R = R +R (R ) Rij ij ik kk kj
ji k k k k
(k−1)(k−1) (k−1) dans Rdans R 0 ou plusieurs éléments de R kjik kk
(n)
ER définissant le langage reconnu par A : union des R pour j ∈ F.1j
S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 6 / 30Des AFD aux expressions régulières : un exemple
(0)
0,1 R ε+11 11
(0)
R 012
(0)
R ∅0 211 2 (0)
R (ε+0+1)22
(1) (0) (0) (0) (0)∗R = R +R (R ) R11ij ij i1 1j
par substitution forme simplifiée
(1) ∗ ∗R ε+1+(ε+1)(ε+1) (ε+1) 111
(1) ∗ ∗R 0+(ε+1)(ε+1) 0 1 012
(1) ∗R ∅+∅(ε+1) (ε+1) ∅21
(1) ∗R ε+0+1+∅(ε+1) 0 ε+0+122
On utilise les règles de simplification suivantes :
∗ ∗ ∗ ∗(ε+R) = R , R +RS = RS , ∅R = R∅ =∅, ∅+R = R +∅ = R
S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 7 / 30
Des AFD aux expressions régulières : un exemple
forme simplifiée
(1) ∗R 111
(1) ∗R 1 012
(1)
R ∅21
(1)
R ε+0+122
(2) (1) (1) (1) (1)∗R = R +R (R ) Rij ij i2 22 2j
par substitution forme simplifiée
(2) ∗ ∗ ∗ ∗R 1 +1 0(ε+0+1) ∅ 111
(2) ∗ ∗ ∗ ∗ ∗R 1 0+1 0(ε+0+1) (ε+0+1) 1 0(0+1)12
(2) ∗R ∅+(ε+0+1)(ε+0+1) ∅ ∅21
(2) ∗ ∗R ε+0+1+(ε+0+1)(ε+0+1) (ε+0+1) (0+1)22
S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 8 / 30Des AFD aux expressions régulières : un exemple
0,11
0
1 2
forme simplifiée
(2) ∗R 111
(2) ∗ ∗R 1 0(0+1)12
(2)
R ∅21
(2) ∗R (0+1)22
Le langage reconnu est
(2) ∗ ∗R = 1 0(0+1)12
S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 9 / 30
Élimination d’état
L’algorithme précédent coute cher!
3n ER à construire pour un AFD à n états et la longueur de chaque
ER croit d’un facteur 4 à chaque étape.
ndans le pire cas : 4 symboles!
Éliminer des états en autorisant les ER dans les transitions entre états.
Choisir un état final q ∈ F et éliminer tous les autres états excepté
l’état initial q et q0
Appliquer le procédé de réduction pour tous les états finaux
S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 10 / 30Élimination d’état
Avant
R2
Après
q ∗k R R R +R1 3 42 qq jiR R1 3
R4 qqi j
S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 11 / 30
The state elimination techniqueÉlimination d’état (suite)
Let’s label the edges with regex’s instead of
Now, let’s eliminate state s.
symbols
Élimination de l’état s
R
1m R + Q S* P
11 1 1
q pR 1 111
q p R + Q S* P1 1 1m 1 m
Q
1
S P1
s ⇒
P
m
Q
k
q pk mR R + Q S* Pkm k1 k 1
q p
k m
R + Q S* P
R km k mk1
67
For each accepting state q eliminate from the
S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 12 / 30
original automaton all states exept q and q.0
68Élimination d’état : algorithm
Pour chaque état final q ∈ F, en appliquant la procédure d’élimination, on
va obtenir un automate A de la formeq
UR
S
∗ ∗ ∗correspondant à l’ER E = (R +SU T) SUq
T
ou bien un automate A de la formeq
R
∗correspondant à l’ER E = Rq
L’ER finale est M
Eq
q∈F
S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 13 / 30
Élimination d’état : exemple
Un exemple : A tel que
∗L(A) ={w : w = x1b ou w = x1bc avec x ∈{0,1} ,b,c ∈{0,1}}
0,1
0,1 0,11
A B C D
On étiquette les transitions par des ER :
0+1
0+1 0+11
A B C D
S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 14 / 30Des expressions régulières aux ε-AFN
On élimine l’état B :
0+1
1(0+1) 0+1
A C D
On supprime l’état C On supprime l’état D
0+1 0+1
1(0+1)(0+1) 1(0+1)
A D A C
∗ ∗L’ER est donc (0+1) 1(0+1)+(0+1) 1(0+1)(0+1)
S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 15 / 30
Des expressions régulières aux ε-AFN
Preuve par récurrence structurelle sur R : on suit la définition récursive des
ER.
Base : variables et constantes
Un ε-AFN N tel que L(N) ={ε}
ε
Un ε-AFN N tel que L(N) =∅
Un ε-AFN N tel que L(N) ={a} pour a∈ Σ
a
S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 16 / 30Des expressions régulières aux ε-AFN
Induction :
Étant donné N et N deux ε-AFN, définir un ε-AFN N reconnaissant1 2
L(N )+L(N )1 2
N1
ε ε
ε ε
N2
S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 17 / 30
Des expressions régulières aux ε-AFN
Étant donné N et N deux ε-AFN, définir un ε-AFN N reconnaissant1 2
L(N ).L(N )1 2
ε
N N1 2
?Étant donné M un ε-AFN, définir un ε-AFN N reconnaissant L(M)
ε
ε ε
M
ε
S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 18 / 30!Example: We convert (0+1) 1(0+1)
0! !
!Example: We convert (0+1) 1(0+1)
! !Exemple 1
0! !
(a)
∗Conversion de (0+1) 1(0+1)
!
! !!
0 1Example: We convert (0+1) 1(0+1)∗! !(0+1) 1(0+1)! !(a)
!
0 ! ! 0! ! ! !1
! !
(b) ! !! 1! !
1
! (b)(a) 0! !
Start ! !
! ! !
00 ! !! ! ! !Start ! !!! !1 !
! !! 1
0! ! ! !! 1
1 !
0! !
1 !! !(b) 1
! !
(c) 1
S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 19 / 30(c)!
750! !
75Start ! !
!Applications
! !! 1
0! !ER sous UNIX :
1 !
. pour n’importe quel caractère
[a a ···a ] pour a +a2+···+a1 2 k 1 k! !
1[:digit:] pour les 10 chiffres
[:alpha:] pour les caractères de l’alphabet (aussi [A-Z])(c)
[:alnum:] pour les chiffres et l’alphabet.
| en lieu et place du + 75
R? pour ε+R
?R+ pour RR
R{n} pour une copie de R n fois.
lex, flex
Recherche de motifs.
S. Graillat (Univ. Paris 6) LI347 (cours n˚3) 20 / 30