Download pdf - Plan Langage(s) · 2018. 6. 26. · Computer Science, Volume B J.M. Autebert, J. Berstel, L. Boasson, Context-free languages and pushdown automata, in Handbook of formal languages,

IntroductionLangages réguliers

Langages hors-contexteAutres classes de langages

Algorithmique du texte

Langage(s)

Philippe ÉZÉQUEL

Université Jean Monnet, Saint-Étienne

Philippe ÉZÉQUEL Langage(s)




Plan

1 Introduction

2 Langages réguliers

3 Langages hors-contexte

4 Autres classes de langages

5 Algorithmique du texte





Bibliographie sommaire

J. Sakarovitch, Éléments de théorie des automates, Vuibert

J.M. Autebert, Langages algébriques, Masson

J.M. Autebert, Calculabilité et décidabilité, Masson

D. Perrin, Finite Automata, in Handbook of TheoreticalComputer Science, Volume B

J.M. Autebert, J. Berstel, L. Boasson, Context-free languagesand pushdown automata, in Handbook of formal languages,volume 1





Mots et langagesHiérarchie de Chomsky

Plan

1 IntroductionMots et langagesHiérarchie de Chomsky










Un peu d’histoire

test de Turing :ELIZASHRDLUJabberwacky

traitement automatique du langage naturel : analyse, synthèse,traduction

langages de programmation, d’interrogation, dedescription,. . . : compilation

grammaires génératives de Chomsky






Mots

on se donne un ensemble fini de lettres (alphabet), A

un mot est une suite finie de lettres : a1a2 · · · an

mot vide : ǫ

ensemble des mots noté A⋆

concaténation : a1 · · · an.b1 · · · bm = a1 · · · anb1 · · · bm

(A⋆, .) monoïde, élément neutre ǫ

facteur, préfixe, suffixe, sous-mot,. . .






Langages

langage : partie de A⋆

opérations booléennes sur les langages : union, intersection,complémentaireopérations spécifiques :

concaténation : L.M = {u.v | u ∈ L, v ∈ M}L0 = {ǫ}, Ln+1 = Ln.L

étoile de Kleene :L⋆ =

⋃

n≥0

Ln

quotient à gauche : u−1L = {v | u.v ∈ L}quotient à droite : Lu−1 = {v | v .u ∈ L}






Grammaires génératives

outil de production de mots d’un langagegrammaire G = (A,V,S ,P) où

A : alphabet terminal

V : alphabet non terminal

A ∩ V = ∅axiome S ∈ VP ensemble de règles : g −→ d avec g , d ∈ (A ∪ V)⋆

relation de réécriture induite : soient u, v ∈ (A ∪ V)⋆

u −→G v ⇐⇒ u = l .g .r , v = l .d .r , g −→ d ∈ P

langage engendré : LG (S) = {m ∈ A⋆ | S −→⋆

Gm}






Hiérarchie de Chomsky

Types de langages

Soit g −→ d ∈ P ;

type 0 : pas de restrictions sur g et d

type 1 : g = uXv , d = uαv , u, v , α ∈ (A ∪ V)⋆, X ∈ V

type 2 : g ∈ V, d ∈ (A ∪ V)⋆

type 3 : g ∈ V, d ∈ AV ∪ A ∪ {ǫ}

type 0 : langages récursivement énumérables

type 1 : langages contextuels

type 2 : langages hors-contexte

type 3 : langages réguliers






Langages réguliers : exemple

Multiples de 3 écrits en base 10 :

S −→ 0 | 1U | 2D | 3Z | 4U | 5D | 6Z | 7U | 8D | 9ZZ −→ 0Z | 1U | 2D | 3Z | 4U | 5D | 6Z | 7U | 8D | 9Z | ǫU −→ 0U | 1D | 2Z | 3U | 4D | 5Z | 6U | 7D | 8Z | 9UD −→ 0D | 1Z | 2U | 3D | 4Z | 5U | 6D | 7Z | 8U | 9D






Langages hors-contexte : exemples

Langage de Dyck

S −→ aSbS | ǫ

Expressions arithmétiques

E −→ T + E | TT −→ F × T | FF −→ x | nombre | (E )






Langages contextuels : exemple

anbncn, n > 0

S −→ aSBC | aBCCB −→ HBHB −→ HCHC −→ BCaB −→ abbB −→ bbbC −→ bccC −→ cc






La hiérachie est stricte

tout langage de type i est aussi de type i − 1 (i ∈ {1, 2, 3})

{anbn, n > 0} hors-contexte, pas régulier

{anbncn, n > 0} contextuel, pas hors-contexte

{(n, n!) | n ∈ N} récursivement énumérable, pas contextuel





Langages reconnaissablesLangages rationnelsPropriétésUtilisations

Plan

1 Introduction

2 Langages réguliersLangages reconnaissablesLangages rationnelsPropriétésUtilisations



5 Algorithmique du textePhilippe ÉZÉQUEL Langage(s)





Automates à états finis

Quintuplet (A,Q, I ,F ,T ) où

A : alphabet terminal

Q : ensemble des états

I ⊆ Q : ensemble des états initiaux

F ⊆ Q : ensemble des états finaux

T : Q×A −→ 2Q transitions de l’AEF






Exemple

0 1

2

3

a, b

a, b

a

aa, b

a a, b

a, b a a, b






Automates et langages

chemin de l’automate : suite de transitions

q0a1−→ q1 · · ·

an−→ qn

étiquette d’un chemin : a1 · · · an

chemin réussi : q0 ∈ I , qn ∈ F

m accepté par l’AEF s’il est l’étiquette d’un chemin réussi

langage reconnu par l’AEF : ensemble des mots acceptés

L reconnaissable s’il est reconnu par un AEF






Variantes d’automates

possibilité d’ǫ-transitions

émondage de l’automate : états accessibles et co-accessibles

si T : Q×A −→ Q et I singleton : automate déterministe

Déterminisation d’AEF

L est reconnaissable si et seulement si L est reconnu par un AEFdéterministe






Expressions rationnelles

Soit A un alphabet. L’ensemble des expressions rationnelles sur Aest défini par

0, ǫ, et, pour a ∈ A, a sont des expressions rationnelles

si E et F sont des expressions rationnelles, E ⋆, E + F , E .Faussi






Langage dénoté par une ER

0, ǫ, et a dénotent ∅, {ǫ}, et {a}si E dénote le langage LE et F le langage LF ,

E ⋆ dénote L⋆

E,

E + F dénote LE ∪ LF ,E .F dénote LE .LF

L est rationnel s’il est dénoté par une expression rationnelle






Exemples

(a + b)⋆a(a + b)(a + b)

(a + ba)⋆(b + ǫ)

a⋆b⋆

b⋆ab⋆ab⋆ab⋆






Grands résultats

Théorème de Kleene

L est régulier ⇐⇒ L est reconnaissable ⇐⇒ L est rationnel

Propriétés de fermeture

La classe des langages réguliers est close pour

les opérations booléennes sur les langages,

l’étoile de Kleene,

les quotients à gauche et à droite,

et bien d’autres opérations. . .






Mais aussi :

l’appartenance d’un mot à un langage régulier est décidable entemps linéaire : parcours de l’AEF déterministe

l’égalité de 2 langages réguliers est décidable : AEF minimaux






À quoi ça sert ?

définition de motifs :recherche de sous-chaînes (cf plus loin)désignation

analyse lexicale en compilation : découpage d’un flot decaractères en unités syntaxiques ((F)LEX)

automates d’états finis : modélisation de processus

et bien sûr en mathématiques. . .





Formes normales de grammairesAutomates à pilePropriétés

Plan

1 Introduction


3 Langages hors-contexteFormes normales de grammairesAutomates à pilePropriétés








Utilisations

langages de programmation : analyse syntaxique

langages naturels : larges fragments des langues humaines






Forme normale de Chomsky

(dite aussi forme quadratique)

Les règles sont de l’une des 2 formesX −→ YZ , avec X ,Y ,Z ∈ VX −→ a, avec X ∈ V et a ∈ A

très pratique pour étudier les propriétés des langageshors-contexte

ǫ pas dans le langage. . .






Forme normale de Greibach

les règles sont de la forme

X −→ au, X ∈ V, a ∈ A, u ∈ V⋆

très pratiques pour utilisation en compilation

ǫ pas dans le langage. . .






Mise sous forme normale

Toute grammaire hors-contexte peut être mise sous forme normalede Chomsky (de Greibach)






Reconnaissance d’un langage hors-contexte

Langages hors-contexte reconnus par les automates à pile (AP) :

pile où l’on peut empiler/dépiler des lettres

ensemble d’états pour l’AP

alphabet de pile et alphabet terminaltransitions : deux sortes

1 dans l’état q, lisant a sur le mot et Z en sommet de pile,passer dans l’état q′, dépiler Z , empiler v et avancer d’unelettre dans le mot (transition (q,Z , a)) : (q,Z )

a−→ (q′, v)

2 dans l’état q, lisant Z en sommet de pile, passer dans l’état q′,dépiler Z et empiler v (ǫ-transition) : (q,Z )

ǫ

−→ (q′, v)

divers modes d’acceptation : pile vide, état final, fond de piletestable,. . . , tous équivalents






Exemple : langage de Dyck

Rappel : mots bien parenthésés.

un seul état,

on empile les ouvrantes,

à la lecture d’un fermante, on dépile une ouvrante (si on peut)

reconnaissance par pile videtransitions :

1 (q, ǫ)a

−→ (q,A)2 (q,A)

a−→ (q,AA)

3 (q,A)b

−→ (q, ǫ)






Langages hors-contexte déterministes

Reconnus par les AP déterministes :

au plus une transition (q,Z , a)

pas de transition (q,Z , a) s’il y a une ǫ-transition (q,Z , ǫ)

Théorème de Sénizergues (prix Gödel 2003)

L’équivalence de langages hors-contexte déterministes est décidable

MAIS

L’équivalence de langages hors-contexte est indécidable






Propriétés positives

la classe des langages hors-contexte est fermée pour l’union etl’étoile de Kleene

la classe des langages hors-contexte est fermée pourl’intersection et le shuffle avec un langage régulier.

la finitude d’un langage hors-contexte est décidable

l’appartenance d’un mot à un langage hors-contexte estdécidable : algorithme CYK en O(n3)

l’appartenance d’un mot à un langage hors-contextedéterministe est décidable en temps linéaire : analyseurs LR(YACC, BISON)






Propriétés négatives

la classe des langages hors-contexte n’est pas fermée pourl’intersection et le complémentaire

pire : la nature de l’intersection ou du complémentaire estindécidable

savoir si une grammaire engendre un langage donné estindécidable

l’ambiguïté d’un langage hors-contexte est indécidable





Machines de TuringLangages contextuels et récursivement énumérables

Plan

1 Introduction



4 Autres classes de langagesMachines de TuringLangages contextuels et récursivement énumérables







Description

un ruban infini, chaque case du ruban contient un symbole

une tête de lecture/écriture qui pointe sur une case du ruban

la tête de lecture/écriture est dans un état parmi une listed’états possibles

métaphore d’un ordinateur. . .

Etat

↓

... 4 y α $ ℵ b a 0 3 _ # ...






Programme d’une machine de Turing

Instruction

si l’état est q1 et le symbole sous la tête est s alors

passer dans l’état q2,

remplacer s par s ′,

déplacer la tête.

Déplacement de la tête sur le ruban : une case à droite (noté⊲) ou une case à gauche (noté ⊳).

Notation d’une instruction (par ex) : (q1, s) =⇒ (q2, s ′,⊲).






Variantes

ruban semi-infini,

plusieurs têtes,

plusieurs rubans,

déterministes,

indéterministes. . .

constructivement équivalentes






MT comme calculateur

une machine de Turing prend en entrée une suite de symboles(sur le ruban)

soit la machine s’arrête, soit elle ne s’arrête pas

si elle s’arrête, le résultat est le contenu final du ruban

exemples :1 Entrée : n en base 102 Sortie : n + 1 en base 10






MT comme accepteur

on distingue des états finaux

une machine de Turing prend en entrée un mot, une lettre parcase

soit la machine s’arrête, soit elle ne s’arrête pas.

si elle s’arrête dans un état final : mot accepté

si elle s’arrête dans un état non final : mot refusé






Langages contextuels

engendrés par des grammaires de type 1 : règles de la forme

uXv −→ uαv

reconnus par des MT linéairement bornées : la MT utiliseun espace au plus égal à celui occupé par le mot d’entrée

appartenance décidable

classe fermée pour le complémentaire, l’union

donc l’intersection






Langages récursivement énumérables

engendrés par des grammaires de type 0 : aucune contraintesur les règles

reconnus par MT quelconques

classe fermée pour l’union, l’intersection, l’étoile de Kleene

pas pour le complémentaire

Théorème de Rice

Soit P une propriété non triviale de langages. Le problème de savoirsi L(M) vérifie P est indécidable





DictionnairesRecherche de motifDistance d’édition

Plan

1 Introduction




5 Algorithmique du texteDictionnairesRecherche de motifDistance d’édition






Trie

idée : factoriser les préfixes des mots du dictionnaire

arbre ordonné, étiquetage des arêtes

sommets internes marqués : correspondent à un mot

toutes les feuilles sont marquées

utilisation : complétion automatique, téléphones portables






Exemple

mr t

a e i o a o

l t g l r s z b t i c i n

e e e o e e t d






Algorithme naïf

Soit à rechercher le motif aab dans la chaîne aaaaaaaab.

a a a a a bX X ×a a b

X X ×a a b

X X ×a a b

X X X

a a b






Complexité de l’algorithme naïf

(presque) chaque lettre de la chaîne est comparée à chaquelettre du motif

si le motif fait m lettres et la chaîne N, mN comparaisons(environ)

valeurs réalistes (bioinformatique) : m = Θ(10),N = Θ(109). . .






Algorithme de Knuth, Morris et Pratt (KMP)

problème de l’algorithme naïf : ne tient pas compte descorrespondances déjà vues

au lieu de reprendre brutalement : savoir quel préfixe maximaldu motif on a lu

construction d’un automate : linéaire en la taille du motif

parsing de la chaîne par l’automate : linéaire en la taille de lachaîne

bien sûr optimal ( ?)






Algorithme KMP : exemple

Avec le motif aab :

ǫǫ a aa aabaaba a

ab

b

b

b a






Définition

opérations d’édition : insertion, suppression, substitution

distance d’édition entre 2 mots u et v : nombre minimal

d’opérations d’édition pour transformer u en v .

dE (abbaba, babba) ≤ 3 :

abbaba −→ babbaba−→ babbab−→ babba






Propriétés

dE (u, ǫ) = |u|

dE (u, u) = 0

dE (u, v) = dE (v , u)

dE (u,w) ≤ dE (u, v) + dE (v ,w)

C’est bien une distance. . .






Algorithme de calcul

dE (u, ǫ) = |u|dE (ǫ, u) = |u|dE (u.a, v .a) = dE (u, v)dE (u.a, v .b) = 1 + min(dE (u.a, v), dE (u, v .b), dE (u, v))






Calcul pratique : mise en place

Soit à calculer dE (bab, abba)

bab

a b b a






Calcul pratique : initialisation

On écrit la distance entre les préfixes et le mot vide :

b 3a 2b 1

0 1 2 3 4a b b a






Calcul pratique : remplissage

On remplit les cases de proche en proche selon les règles suivantes

1 si les lettres indices de la case sont égales, on reporte la valeurde la diagonale :

b 3 44 3

b2 si les lettres indices de la case sont différentes, on reporte la

plus petite des 3 valeurs, plus 1 :

b 3 32 2

a






Calcul pratique : résultat

La distance est le contenu de la case en haut à droite :

b 3a 2b 1

0 1 2 3 4a b b a
