Théorie des Langages Formels Chapitre 1 - UPJVleve/Enseign/LF1718/chapitre1_LF.pdf · L’enseignement Introduction Mots Ensembles Théorie des Langages Formels Chapitre 1 ... Théorie

L’enseignement Introduction Mots Ensembles

Théorie des Langages FormelsChapitre 1

Florence Levé

[email protected]

Année 2017-2018

1/36


Au sujet de l’unité d’enseignementLa théorie des langages formels est une des matières fondamentalesde l’informatique.

Objectifs de l’enseignement :I comprendre les concepts de base de la théorie des langages

formels ;I comprendre son rôle et son intérêt en informatiqueI savoir manipuler et utiliser langages, automates, grammaires.

De nombreuses notions et approches de l’informatique vontêtre évoquées, notamment à travers les exemples :

I algorithmique, complexité, preuve de programme, expressionsrégulières, . . .

Pré-requis : connaissance minimale de la notion d’ensembleModalités de contrôle des connaissances :

I sup(E, (E+P)/2),I pas le droit aux documents.

2/36


Bibliographie

Introduction à la calculabilité, P. Wolper, Dunod 2006 (3èmeédition), chapitres 1 à 4.Théorie des automates (méthodes et exercices corrigés),P. Séébold, Vuibert 1999.Méthodes mathématiques pour l’informatique (4ème édition),J. Vélu, chapitres 21 et 22, Dunod 2005.Théorie des langages et des automates, J.-M. Autebert,Masson 1994 (deuxième partie, p41–67).Éléments de théorie des automates,J. Sakarovitch, Vuibert 2003 (chapitre 1, p55–232).Nombreux sites webs : n’hésitez pas à faire vos propresrecherches.Ce cours est basé sur celui dispensé par Gwénaël Richommejusqu’en 2009.

3/36


Qu’est-ce que les langages formels ?

Un langage formel = un ensemble de mots.

ExemplesI L’ensemble des mots définis dans un dictionnaire.I L’ensemble des phrases que l’on peut écrire en français.

•Remarque : alphabet = lettres, espace et symboles de

ponctuation, . . .

I L’ensemble des programmes en langage JAVA.

4/36


Quelques problématiques

Analyse lexicale : est-ce que mon programme utilise les motsde base du langage ?

I utilisation d’automates dans les compilateurs.

Analyse syntaxique : est-ce que les mots/phrases de monprogramme sont correctement construits ?

I utilisation de grammaires dans les compilateurs.I (problème : reconnaissance des langues naturelles)

Est-ce que le programme fait ce que je veux ?I indécidable.I preuve à la main dans de nombreux cas !

Quels langages peuvent être reconnus par une machine ?

5/36


Quelques originesDes besoins similaires dans 3 thématiques :

Informatique :I Besoin de décrire de manière finie certains langages infinisI Premiers langages de programmation : algol, ...I Claude Shannon 1949 : description de protocoles de

communicationLogique :

I Besoin de définir formellement le discours mathématiqueI Stephen Cole Kleene 1954 : montre qu’un langage est

reconnaissable si et seulement s’il peut être engendré, à partirdes lettres de l’alphabet, à l’aide des trois opérations union,produit et étoile.

LinguistiqueI Besoin de décrire les langues naturellesI Début des années 50 : premières tentatives visant à utiliser

l’ordinateur pour traduire un texteI Noam Chomsky 1956 : hiérarchie des langages.

6/36


La Hiérarchie des langages de Chomsky

Langages récursivement énumérables

Langages contextuels

Langages algébriques

Langages rationnels

7/36






Langages rationnels

{rationnels}I = {reconnaissables}I langages reconnus par un automate et/ou définis par une

expression régulière.7/36






Langages rationnels

⇢ {algébriques}I langages définis par une grammaire ou reconnus par un

automate à pile.

7/36






Langages rationnels

⇢ {contextuels}I langages définis par une grammaire contextuelle.

7/36






Langages rationnels

⇢ {récursivement énumérables}I langages acceptables par une machine de Turing (permet

d’étudier la décidabilité d’un problème).

7/36


Quelques utilisations1. Recherche de motif dans un texte

Texte en entrée :

de t

t o t o

t

lettre différente de t

lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36



Texte en entrée : Une histoire de toto de plus

de t

t o t o

t


lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36




de t

t o t o

t


lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36




de t

t o t o

t


lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36



Texte en entrée : Une_histoire de toto de plus

de t

t o t o

t


lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36




de t

t o t o

t


lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36




de t

t o t o

t


lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36




de t

t o t o

t


lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36




de t

t o t o

t


lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36




de t

t o t o

t


lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36




de t

t o t o

t


lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36




de t

t o t o

t


lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36




de t

t o t o

t


lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36



Texte en entrée : Une histoire_de toto de plus

de t

t o t o

t


lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36




de t

t o t o

t


lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36




de t

t o t o

t


lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36



Texte en entrée : Une histoire de_toto de plus

de t

t o t o

t


lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36




de t

t o t o

t


lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36




de t

t o t o

t


lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36




de t

t o t o

t


lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36




de t

t o t o

t


lettre différente

de o et de t

t

t


lettre différente

de o et de t

lettre

différente

8/36



Applications de la recherche de mots/motifsI Recherche dans un index

•index d’un fichier ;

•index du web.

I Recherche de virus•

fichier : un mot (une suite) de 0 et de 1.

•virus : un mot (ou un ensemble de mots)

•base des signatures : un gros automate (version simplifiée)

9/36


Quelques utilisationsExemple 2. Compilation

Génération de compilateurs (et donc de nouveaux langagesinformatiques)

I Automates : analyse lexicale ;I Grammaires : analyse syntaxique.I Remarque : la science de la compilation fait appel à des

techniques supplémentaires : transformation de code, contrôlede type, ...)

10/36


Quelques utilisations3. REGEXP (REGular EXPressions)

Expressions régulièresUtilisées par les mécanismes de recherche/remplacement

I éditeurs de texte : JEdit, emacsI Recherche dans des dictionnaires en ligne : dictionnaire de

l’académie française (essayer par exemple ˆa[a-z]*iste)I commandes de base unix : ls, grep, sed, . . .I inclus dans des langages de script : perl, javascript, . . .

11/36


Quelques utilisations4. Liens avec d’autres domaines

Les langages formels apparaissent ou sont liés à de nombreuxdomaines, de l’informatique ou non :

réseaux, systèmes d’exploitation, logiciels (compilation,traduction, vérification),modélisation, présentation de protocoles, algorithmescalculabilité, complexité, logique,combinatoire des mots, dynamique symbolique, théorie desnombres,linguistique (traitement de la langue naturelle),électronique,bioinformatique (séquençage du génome),imagerie (analyse d’images),. . .

12/36


Le plan du cours

Un langage est un ensemble de mots. Pour étudier les langages, leplan du cours sera le suivant :

Définitions, mots, langages, langages rationnelsAutomates et langages reconnaissables

I définitions, fonctionnement d’un automateI équivalence avec langages rationnelsI déterminismeI minimalité

Langages non reconnaissableGrammaires

13/36


Lettres et alphabets

Un langage est un ensemble de mots. Un mot est écrit avec deslettres appartenant à un alphabet.

Lettre : symboles.Alphabet : ensemble fini non vide de lettres.

Exemples

1. Alphabet latin, grec, . . .2. Chiffres : {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, }3. Caractères ASCII, UNICODE, . . .4. Parties de ces alphabets : {a, b}, {0, 1}

Attention : les symboles doivent être non ambigüs !

{a, b, ab},{ab, a, ba}

�ne sont pas des alphabets.

14/36


Lettres grecques courantes

lettre minuscule majusculealpha ↵beta �gamma � �delta � �epsilon "phi � �psi rho ⇢mu µnu ⌫

15/36


Mots

Mot : suite de lettres.I Notation : les lettres sont accolées.

I Exemples : bonjour, abaababaab, 0110101, . . .

I Formellement, a1 . . . an est le mot constitué dans l’ordre deslettres a1 puis a2 puis . . . an.

I On ne tient pas compte de la signification éventuelle.

Mot vide : suite vide de lettres : ".

Attention ! Ne pas confondre le mot vide " avec l’ensemble vide ;

16/36


La concaténation

Définition : la concaténation de deux mots u et v est le motobtenu en mettant bout à bout dans l’ordre les lettres de u

puis les lettres de b.

Notation : uv ou u.v

La concaténation est aussi appelée produit de concaténation

Exemple : (aabac).(dab) vaut aabacdab

Formellement, si⇢

n � 0 et p � 0 sont deux entiers,a1, . . . , an, b1, . . . , bp sont des lettres,

alors(a1 . . . an).(b1 . . . bp) = a1 . . . anb1 . . . bp

17/36


La concaténation






Formellement, si⇢



17/36


La concaténation






Formellement, si⇢



17/36


Monoïde

Propriétés de la concaténation :I

u" = u = "uI (uv)w = u(vw)

Propriété : l’ensemble des mots muni de la concaténationforme un monoïde.

Monoïde : ensemble muni d’une opération interne associativepossédant un élément neutre.

Autres exemples de monoïdes : (IN,+), (IN+,⇥)

L’ensemble des mots définis sur un alphabet A se note A

⇤

18/36


Monoïde libre

Propriété fondamentale :Tout mot se décompose de manière unique sur les lettres.

a1 . . . an = b1 . . . bp implique⇢n = p

et ai = bi pour tout 1 i n.

Le monoïde A

⇤ est dit libre (de base A).

19/36


Longueur

Longueur d’un mot : nombre de lettres qui le composent.

Notation : |u| est la longueur de u.

Exemple : |abaab| = 5

Propriétés :I |"| = 0

I |uv | = |u|+ |v |

20/36


Longueur





I |uv | = |u|+ |v |

20/36


Longueur





I |uv | = |u|+ |v |

20/36


Nombre d’occurrences

|u|a : nombre d’occurrences de la lettre a dans un mot u

Exemple : |abaab|a = 3

Propriétés :I |"|a = 0

I |uv |a = |u|a + |v |aI |u| =

X

a2A

|u|a

21/36






I |uv |a = |u|a + |v |aI |u| =

X

a2A

|u|a

21/36






I |uv |a = |u|a + |v |aI |u| =

X

a2A

|u|a

21/36


Un peu de vocabulaire

Facteur : u = pvs

Préfixe (facteur gauche) : dans l’exemple précédent, p, pv ,sont des préfixes de u.

Suffixe (facteur droit) : dans l’exemple précédent, s, vs sontdes suffixes de u.

Exemple : Facteurs, préfixes et suffixes du mot abaab ?

22/36


Ensembles

Un ensemble est caractérisé par la notion d’appartenance

I pour un ensemble E , tout objet x appartient ou non à E .

Ix 2 E : x appartient à E

(on dit aussi que x est dans E ) ;

Ix 62 E : x n’appartient pas à E .

23/36


Définitions d’ensemble

Par extension : en précisant les valeurs de l’ensemble entreaccolades (valeurs séparées par des virgules).

I Exemple : E = {a, c , f }Par compréhension, en précisant la propriété que vérifient lesélements de l’ensemble.

I Ensemble des entiers pairs =

{x 2 IN | x mod 2 = 0}I Ensemble des mots sur A de longueur paire =

{x 2 A

⇤ | |x | mod 2 = 0}

24/36


Égalité

Deux ensembles sont égaux si les éléments de l’unappartiennent à l’autre et réciproquement.En d’autres termes E = F

I si pour tout x dans E , x appartient à F etpour tout x dans F , x appartient à E

I (avec les notations de la logique)(8x 2 E , x 2 F ) et (8x 2 F , x 2 E )

Exemples, avec a, b et c trois lettres différentes :I {ab, ac , a, b} = {a, ab, b, ac}I {a, bc} = {a, a, bc , a, bc , a}

AttentionI {ab, ac , a, b} 6= {ab, ac}I {ab, ac , b} 6= {ab, ac , a}

25/36


Notation de la logique

Très utile pour synthétiser des idées/présentations !Un langage à apprendre !9 il existe8 pour tout) implique : dire qu’une propriété p implique une propriété q

signifie que si la propriété est vérifiée alors la propriété q l’estaussi(p ) q) est aussi une propriété (vraie si p est fausse), est équivalent à : dire qu’une propriété p équivaut à unepropriété q signifie que p et q sont simultanément vraie ousimultanément fausse.

26/36


Inclusion

Un ensemble E est dit inclus dans un ensemble F si toutélément de E appartient à F (8x 2 E , x 2 F ).

I Notation : E ✓ F

Un ensemble E est dit strictement inclus dans un ensemble F

si E ✓ F et E 6= F .I Notation : E ⇢ F

Exemples :I {ab, ac , a, b} ✓ {a, ab, b, ac} (en fait =)I {ab, ac} ⇢ {ab, ac , a, b}I {ab, ac , a, b} 6⇢ {ab, ac}

Propriété importante :X ✓ Y et Y ✓ X , X = Y

27/36


Ensemble vide

L’ensemble constitué d’aucun élément.Notation : ;.Exercice

I " :•

le mot vide

•d’ici à la fin de ce cours, l’expression rationnelle désignant

l’ensemble {"}I ; : l’ensemble videI {"} : l’ensemble ayant comme seul élément le mot vide.I {;} : l’ensemble ayant comme seul élément l’ensemble vide.

28/36


Implémentation d’ensemble

Tableaux pour ensembles finis, voire tableaux triésMais il peut y avoir plus efficace : arbres, . . .Automates. . .

29/36


Opérations ensemblistes

Union. X [ Y = {x | x 2 X ou x 2 Y }.Intersection. X \ Y = {x | x 2 X et x 2 Y }.Complémentation.

X \ Y = {x | x 2 X et x 62 Y } (= X \ (X \ Y )).Diagramme de Venn :

Y

Y\XX\Y

X

Y

X Y

X

30/36


Propriétés (1/4)

X [ ; = X ,X \ ; = ;,X \ ; = X ,; \ X = ;.X [ X = X ,X \ X = X ,X \ X = ;.

31/36


Propriétés (1/4)

X [ ; = X ,X \ ; = ;,X \ ; = X ,; \ X = ;.X [ X = X ,X \ X = X ,X \ X = ;.

31/36


Propriétés (1/4)

X [ ; = X ,X \ ; = ;,X \ ; = X ,; \ X = ;.X [ X = X ,X \ X = X ,X \ X = ;.

31/36


Propriétés (1/4)

X [ ; = X ,X \ ; = ;,X \ ; = X ,; \ X = ;.X [ X = X ,X \ X = X ,X \ X = ;.

31/36


Propriétés (1/4)

X [ ; = X ,X \ ; = ;,X \ ; = X ,; \ X = ;.X [ X = X ,X \ X = X ,X \ X = ;.

31/36


Propriétés (1/4)

X [ ; = X ,X \ ; = ;,X \ ; = X ,; \ X = ;.X [ X = X ,X \ X = X ,X \ X = ;.

31/36


Propriétés (1/4)

X [ ; = X ,X \ ; = ;,X \ ; = X ,; \ X = ;.X [ X = X ,X \ X = X ,X \ X = ;.

31/36


Propriétés (2/4)

(commutativité)⇢

X [ Y = Y [ X ,X \ Y = Y \ X .

Attention !X \ Y n’est pas nécessairement égal à Y \ X

Exemple X = {a}, Y = {b}.I

X \ Y = X = {a},I

Y \ X = Y = {b}.

32/36


Propriétés (3/4)

(associativité)⇢

X [ (Y [ Z ) = (X [ Y ) [ Z ,X \ (Y \ Z ) = (X \ Y ) \ Z .

On peut donc enlever les parenthèses

Attention ! on peut avoir X \ (Y \ Z ) 6= (X \ Y ) \ Z .

Exemple : X = {a, b}, Y = {a}, Z = {a} :I

X \ (Y \ Z ) = X ,I (X \ Y ) \ Z = {b}

33/36


Propriétés (3/4)

(associativité)⇢

X [ (Y [ Z ) = (X [ Y ) [ Z ,X \ (Y \ Z ) = (X \ Y ) \ Z .




X \ (Y \ Z ) = X ,I (X \ Y ) \ Z = {b}

33/36


Propriétés (3/4)

(associativité)⇢

X [ (Y [ Z ) = (X [ Y ) [ Z ,X \ (Y \ Z ) = (X \ Y ) \ Z .




X \ (Y \ Z ) = X ,I (X \ Y ) \ Z = {b}

33/36


Propriétés (4/4)

(distributivité)⇢

X \ (Y [ Z ) = (X \ Y ) [ (X \ Z ),X [ (Y \ Z ) = (X [ Y ) \ (X [ Z ).

Lois de de Morgan :⇢X \ (Y \ Z ) = (X \ Y ) [ (X \ Z ),X \ (Y [ Z ) = (X \ Y ) \ (X \ Z ).

34/36


Propriétés (4/4)

(distributivité)⇢

X \ (Y [ Z ) = (X \ Y ) [ (X \ Z ),X [ (Y \ Z ) = (X [ Y ) \ (X [ Z ).

Lois de de Morgan :⇢X \ (Y \ Z ) = (X \ Y ) [ (X \ Z ),X \ (Y [ Z ) = (X \ Y ) \ (X \ Z ).

34/36


Produit cartésien

Le produit cartésien sera utile pour définir les transitionspossibles d’un automate.

Soient E1, . . . ,En des ensembles, le produit cartésien de cesensembles est égal à l’ensemble des n-uplets (x1, . . . , xn) telsque xi 2 Ei pour chaque i , 1 i n :

E1 ⇥ E2 ⇥ . . .⇥ En = {(x1, . . . , xn) | xi 2 Ei , 1 i n}

Exemple : {a, b}⇥ {ab, ba, c} =

{(a, ab), (a, ba), (a, c), (b, ab), (b, ba), (b, c)}

Exemple : {1, 2}⇥ {a, b}⇥ {2, 3} ={(1, a, 2), (1, a, 3), (1, b, 2), (1, b, 3), (2, a, 2), (2, a, 3), (2, b, 2), (2, b, 3)}

35/36


Produit cartésien



E1 ⇥ E2 ⇥ . . .⇥ En = {(x1, . . . , xn) | xi 2 Ei , 1 i n}




35/36


Produit cartésien



E1 ⇥ E2 ⇥ . . .⇥ En = {(x1, . . . , xn) | xi 2 Ei , 1 i n}




35/36


Cardinal

cardinal d’un ensemble fini = son nombre d’éléments.

Notation : Card(E ) ou #E

Exemple :I

Card({a, b}) = 2

ICard({ab, ba, c}) = 3

ICard({a, b}⇥ {ab, ba, c}) = 6.

ICard({1, 2}⇥ {a, b}⇥ {2, 3}) = 8

Pour E1,E2, . . . ,En (n � 1) des ensembles finis,

Card(E1⇥E2⇥ . . .⇥En) = Card(E1)⇥Card(E2)⇥ . . .⇥Card(En)

36/36


Cardinal



Exemple :I

Card({a, b}) = 2


ICard({a, b}⇥ {ab, ba, c}) = 6.

ICard({1, 2}⇥ {a, b}⇥ {2, 3}) = 8



36/36


Cardinal



Exemple :I

Card({a, b}) = 2


ICard({a, b}⇥ {ab, ba, c}) = 6.

ICard({1, 2}⇥ {a, b}⇥ {2, 3}) = 8



36/36


Cardinal



Exemple :I

Card({a, b}) = 2


ICard({a, b}⇥ {ab, ba, c}) = 6.

ICard({1, 2}⇥ {a, b}⇥ {2, 3}) = 8



36/36


Cardinal



Exemple :I

Card({a, b}) = 2


ICard({a, b}⇥ {ab, ba, c}) = 6.

ICard({1, 2}⇥ {a, b}⇥ {2, 3}) = 8



36/36

Documents

Théorie des Langages Formels Chapitre 1 - UPJVleve/Enseign/LF1718/chapitre1_LF.pdf · L’enseignement Introduction Mots Ensembles Théorie des Langages Formels Chapitre 1 ... Théorie