Automates - Damien Nouvel · 2020. 10. 14. · Damien Nouvel Automates 13 / 22 Théorie des langages Alphabets et langages Quelques exemples (suite) : – ∑ = { a, b, c }, L 1 =

Automates

Théorie des langages

Damien Nouvel

Licence Informatique –L1Damien Nouvel

Automates2 / 22

Théorie des langagesPlan

● Alphabets et langages● Expressions régulières formelles


Automates3 / 22




Automates4 / 22

Théorie des langagesAlphabets et langages

● Structure du langage :● Algèbre, ensemble muni d'opérations (anneau)● « Briques de base » : alphabet● Propriétés formelles particulières du langage

● Diférents manières de défnir un langage :● Intentionnelle : « tous les mots qui... »● Extensionnelle : {mot, autremot, a, b, 3, 42 }● Défnitoire : {xyz | x = yz }● Opération sur d'autres langages (union, concaténation,

intersection, complémentaire ...)


Automates5 / 22


● Alphabet, un ensemble « hors-langage » :● Ensemble ∑ des symboles utilisés par un langage

– ∑ = {a, b, c, d … z} ( = [a-z] )– ∑ = {0, 1, 2... 9} ( = [0-9] )– ∑ = {a, f, d, x}– ∑ = {b, c, 0, $, μ, z}– ∑ = {ab, de, xyz}– ∑ = {abc, a, tuv, vu}

● On considère les éléments comme atomiques : « abc » peut-être un symbole unique pour un langage

● Pas de répétitions au sein d'un alphabet (ensemble)


Automates6 / 22


● Mot (ou chaîne) :● Un élément de l'alphabet est un mot● Concaténation « . » de symboles issus d'un alphabet :

– ∑ = {0, 1} : α1 = 0.0.1.0, α2 = 1.0.0.0.1.0 ...

– Associative : (a.b).c = a.(b.c)– Non commutative : 0.1 ≠ 1.0

● Quelque soit l'alphabet, il est possible de former le mot (ou chaîne) vide, noté « ε » (diférent de ∅)

● Taille du mot : | x |, nombre de symboles :– | 0.1.0.0 | = 4 (∑ = {0, 1})– | d.d.ab.ab.d | = 5 (∑ = {ab, d})– | ε | = 0 (∀ ∑)


Automates7 / 22


● Un langage est un ensemble de mots● Défnition de langages à partir d'alphabets :

● Langage généré par un alphabet (récursive) :– Tout mot de l'alphabet appartient au langage– Toute concaténation de mots du langage appartient au langage– Le mot vide ε appartient au langage

● Puissance « ∑i » d'un alphabet :– Tous les mots formés par concaténation de i éléments de ∑– Quelque soit l'alphabet, ∑0 = { ε }– Par ex., si ∑ = {0, 1} alors :

● ∑1 = {0, 1}● ∑2 = {00, 01, 10, 11}● ∑3 = {000, 001, 010, 011, 100, 101, 110, 111}


Automates8 / 22


● Fermeture / étoile de Kleene « * » :● Kleene : mathématicien américain● Fermeture (étoile, itéré) (informellement) : tout ce qu'il est

possible de construire à partir d'un alphabet / langage● Union de toutes les puissances d'un alphabet :

– ∑* = ∑0 ∪ ∑1 ∪ ∑2 ∪ ∑3 ∪ ∑4 …● Ou « langage de ∑ », « langage généré par ∑ »● Quelque soit ∑ : ε ∈ ∑*

● Attention à la distinction symboles / mots :● Si ∑ = {0, 11} alors 1.0.1 n'appartient pas à ∑*

● Si ∑ = {a, ab} alors a.ab.b.ab. n'appartient pas à ∑*


Automates9 / 22


● Langage sur un alphabet :● Un langage L sur un alphabet ∑ est un sous-ensemble de ∑*

● Opérations sur les langages (étant donné ∑) :● Concaténation : « L.M » (ou « LM ») : mot formés par

concaténation d'éléments de L et de M (dans l'ordre)– Associative, non commutative, élément neutre ε, élément

absorbant ø● Puissance : « Li » = { α ∈ L* t. q. |α| = i } (idem alphabet)

– Remarque : L0 = ε et Li = Li-1.L● Fermeture (étoile, itéré) : « L* » = ∪i≥0 L

i (idem alphabet)

– Idempotente : (L*)* = L*

– Quelque soient L et ∑ : ε ∈ L* (idem alphabet)


Automates10 / 22


● Union : « L ∪ M » (ou L + M) mots issus soit de L soit de M– Associative, commutative, élément neutre ø– La concaténation est distributive par rapport à l'union

● Intersection : « L ∩ M » : mots qui existent dans L et dans M– Associative, commutative, élément neutre ∑*, élément absorbant ø

● Complémentaire : « L » : mots de ∑* qui ne sont pas dans L● Fermeture (étoile, itéré) stricte : : « L+ » = ∪i≥1 L

i

– Remarques : idempotente, L+ = L.L* et L* = L+ ∪ {ε}● Quotient droit : « L.M-1 » = {α ∈ ∑*, ∃β ∈ M, α.β ∈ L }● Quotient gauche : « L-1.M » = {α ∈ ∑*, ∃β ∈ L, β.α ∈ M }● Miroir : L (tilde au dessus), langage ou tous les mots sont

« renversés » : l'ordre des symboles est inversé


Automates11 / 22


● Quelques exemples :– Alphabet ∑ = { a, b, c }

– Langages L1 = { a, b }, L2 = { a, c }

Éléments dulangage

Éléments del'alphabet

L1

ab

L2

ac

∑

ab

c


Automates12 / 22


● Quelques exemples (suite) :– ∑ = { a, b, c }, L1 = { a, b }, L2 = { a, c }

– Union : L3 = L1 ∪ L2

– Concaténation : L4 = L1 . L2



∑a b

L1

a b

L2

a c

c

L3

ab

c

L4a a a c

b a b c


Automates13 / 22



– Union et concaténation : L5 = L1 ∪ ( L1 . L2 )

– Intersection : L6 = L1 ∩ L2



∑a b

L1

a b

L2

a c

c

L5

a a a c

b a b c

a

bL

1 . L

2

L6

L1

L1

L6

L1

L2

ab c


Automates14 / 22



– Puissance : L7 = L10, L

8 = L

11, L

9 = L

12, L

10 = L

13



∑a b

L1

a b

L2

a c

c

L7ε

L8a b

L9

a a a b

b a b b

L10a a a a a b

b a a b a b

a b a a b b

b b a b b b


Automates15 / 22



– Fermeture : L11 = ∑* (= ∑0 ∪ ∑1 ∪ ∑2 ...), L

12 = L

1*



∑a b

L1

a b

L2

a c

c

L11

ε

a

b

c

a a

a b

a c

c a

...

a a a

a a b

a a c

c a a

...

...

L12

ε

a

b

a a

a b

b a

b b

...

a a a

a a b

a b a

b a a

...

b a b

...

...

......


Automates16 / 22



– Complémentaire : L13 = L1 (≈ « ∑* - L

1 »)



∑a b

L1

a b

L2

a c

c

L13

εa

b

c

a a

a b

a c

c a

...

a a a

a a b

a a c

c a a

...

...

......∑*


Automates17 / 22



– Intersection et complémentaire : L14 = ( L2 . L1 ) ∩ L22



∑a b

L1

a b

L2

a c

c

L2 . L

1

a a a b

c a c b

a c

c c

L22 L

14

L2

2


Automates18 / 22




Automates19 / 22

Théorie des langagesExpressions régulières formelles

● Expressions régulières :● ≃ expressions rationnelles (langage régulier ≃ rationnel)● Formalisées mathématiquement en 1959 (Rabin & Scott)● Utilisées en programmation (regexp) : grep, awk, Perl, Python

● Un « langage pour défnir un langage »● Symboles (par priorité) : { (, ), *, +, +}● Une expression régulière « génère », « accepte »,

« reconnaît » un langage (dit régulier)● Langage des expression régulières sur ∑ : Reg(∑)

● Reg(∑) ⊂ (∑ ∪ { +, *, +, (, ) } )*

● Programmation : le + deviendra | (éviter la confusion)


Automates20 / 22


● Défnition récursive (étant donné ∑) :● Tout élément de ∑ est une expression régulière● Si r est une expression régulière, alors (r), r+, r* aussi● Si r1 et r2 sont des exp. régulières, alors r1 r2 et r1 + r2 aussi

● Soit l'application L qui associe à une expression régulière un langage, défnie de la manière suivante :

● L : Reg(∑) → ∑*

● L( a ) = { a } ∀ a ∈ ∑ , L( ε ) = { ε } et L( ∅ ) = ∅● L( r1 + r2 ) = L(r1) ∪ L(r2)

● L( r1 r2 ) = L(r1) . L(r2)● L( r* ) = L(r)* et L( r+ ) = L(r)+


Automates21 / 22


● Par ex., soit ∑ = { a, b, c } :● L(b) = b● L(a+c) = L(a) ∪ L(c) = {a, c}● L(ac) = L(a) . L(c) = {a.c}● L(c*) = L(c)* = {c}* = {ε, c, cc, ccc, cccc...}● L(a+c*) = L(a) ∪ L(c*) = {a} ∪ {c}* = {ε, a, c, cc, ccc, cccc...}● L((a+b)*) = (L(a) ∪ L(b))* = {a, b}*

= {ε, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab …}● L((ac)++b) = (L(a) . L(c))+ ∪ L(b) = {ac}+ ∪ {b}

= {b, ac, acac, acacac …}● L(a++(abc)*+((b+a)c)+) = L(a)+ ∪ L(abc))* ∪ L({b, a}.c)+

= {a, aa, aaa ... ε, abc, abcabc ... bc, ac, bcbc, acac...}


Automates22 / 22


● Quelques cas d'applications classiques :● Trouver des fchiers dans un dossier :

– Tous les fchiers d'extension « .jpg » : *.jpg● Chercher toutes les fonctions « get... » dans un programme :

– Expression régulière : function get[a-Z]*(● Extraire toutes les phrases d'un texte :

– Expression régulière : (.+?+!)*(.+?+!)*

● Vérifer si une entrée de programme est bien un entier :– Expression régulière : (-+ε){0...9)*

● Chercher les mots au pluriel dans un texte :– Expression régulière : [a-z]*((e+a)ux+s)

Diapo 1Diapo 2Diapo 3Diapo 4Diapo 5Diapo 6Diapo 7Diapo 8Diapo 9Diapo 10Diapo 11Diapo 12Diapo 13Diapo 14Diapo 15Diapo 16Diapo 17Diapo 18Diapo 19Diapo 20Diapo 21Diapo 22

Documents

Automates - Damien Nouvel · 2020. 10. 14. · Damien Nouvel Automates 13 / 22 Théorie des langages Alphabets et langages Quelques exemples (suite) : – ∑ = { a, b, c }, L 1 =