of 14/14
Introduction Langages réguliers Langages hors-contexte Autres classes de langages Algorithmique du texte Langage(s) Philippe ÉZÉQUEL Université Jean Monnet, Saint-Étienne Philippe ÉZÉQUEL Langage(s) Introduction Langages réguliers Langages hors-contexte Autres classes de langages Algorithmique du texte Plan 1 Introduction 2 Langages réguliers 3 Langages hors-contexte 4 Autres classes de langages 5 Algorithmique du texte Philippe ÉZÉQUEL Langage(s) Introduction Langages réguliers Langages hors-contexte Autres classes de langages 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 Theoretical Computer Science, Volume B J.M. Autebert, J. Berstel, L. Boasson, Context-free languages and pushdown automata, in Handbook of formal languages, volume 1 Philippe ÉZÉQUEL Langage(s) Introduction Langages réguliers Langages hors-contexte Autres classes de langages Algorithmique du texte Mots et langages Hiérarchie de Chomsky Plan 1 Introduction Mots et langages Hiérarchie de Chomsky 2 Langages réguliers 3 Langages hors-contexte 4 Autres classes de langages 5 Algorithmique du texte Philippe ÉZÉQUEL Langage(s)

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,

  • View
    1

  • Download
    0

Embed Size (px)

Text of Plan Langage(s) · 2018. 6. 26. · Computer Science, Volume B J.M. Autebert, J. Berstel, L....

  • 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)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Plan

    1 Introduction

    2 Langages réguliers

    3 Langages hors-contexte

    4 Autres classes de langages

    5 Algorithmique du texte

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Mots et langagesHiérarchie de Chomsky

    Plan

    1 IntroductionMots et langagesHiérarchie de Chomsky

    2 Langages réguliers

    3 Langages hors-contexte

    4 Autres classes de langages

    5 Algorithmique du texte

    Philippe ÉZÉQUEL Langage(s)

  • IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Mots 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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Mots et langagesHiérarchie de Chomsky

    Mots

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

    un mot est une suite finie de lettres : a1a2 · · · anmot 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,. . .

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Mots et langagesHiérarchie de Chomsky

    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}

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Mots et langagesHiérarchie de Chomsky

    Grammaires génératives

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

    A : alphabet terminalV : alphabet non terminalA ∩ 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 −→⋆G m}

    Philippe ÉZÉQUEL Langage(s)

  • IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Mots et langagesHiérarchie de Chomsky

    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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Mots et langagesHiérarchie de Chomsky

    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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Mots et langagesHiérarchie de Chomsky

    Langages hors-contexte : exemples

    Langage de Dyck

    S −→ aSbS | ǫ

    Expressions arithmétiques

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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Mots et langagesHiérarchie de Chomsky

    Langages contextuels : exemple

    anbncn, n > 0

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

    Philippe ÉZÉQUEL Langage(s)

  • IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Mots et langagesHiérarchie de Chomsky

    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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Langages reconnaissablesLangages rationnelsPropriétésUtilisations

    Plan

    1 Introduction

    2 Langages réguliersLangages reconnaissablesLangages rationnelsPropriétésUtilisations

    3 Langages hors-contexte

    4 Autres classes de langages

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

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Langages reconnaissablesLangages rationnelsPropriétésUtilisations

    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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Langages reconnaissablesLangages rationnelsPropriétésUtilisations

    Exemple

    0 1

    2

    3

    a, b

    a, b

    a

    aa, b

    a a, b

    a, b a a, b

    Philippe ÉZÉQUEL Langage(s)

  • IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Langages reconnaissablesLangages rationnelsPropriétésUtilisations

    Automates et langages

    chemin de l’automate : suite de transitions

    q0a1−→ q1 · · ·

    an−→ qn

    étiquette d’un chemin : a1 · · · anchemin 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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Langages reconnaissablesLangages rationnelsPropriétésUtilisations

    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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Langages reconnaissablesLangages rationnelsPropriétésUtilisations

    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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Langages reconnaissablesLangages rationnelsPropriétésUtilisations

    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

    Philippe ÉZÉQUEL Langage(s)

  • IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Langages reconnaissablesLangages rationnelsPropriétésUtilisations

    Exemples

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

    (a + ba)⋆(b + ǫ)

    a⋆b⋆

    b⋆ab⋆ab⋆ab⋆

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Langages reconnaissablesLangages rationnelsPropriétésUtilisations

    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. . .

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Langages reconnaissablesLangages rationnelsPropriétésUtilisations

    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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Langages reconnaissablesLangages rationnelsPropriétésUtilisations

    À 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. . .

    Philippe ÉZÉQUEL Langage(s)

  • IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Formes normales de grammairesAutomates à pilePropriétés

    Plan

    1 Introduction

    2 Langages réguliers

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

    4 Autres classes de langages

    5 Algorithmique du texte

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Formes normales de grammairesAutomates à pilePropriétés

    Utilisations

    langages de programmation : analyse syntaxique

    langages naturels : larges fragments des langues humaines

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Formes normales de grammairesAutomates à pilePropriétés

    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. . .

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Formes normales de grammairesAutomates à pilePropriétés

    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. . .

    Philippe ÉZÉQUEL Langage(s)

  • IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Formes normales de grammairesAutomates à pilePropriétés

    Mise sous forme normale

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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Formes normales de grammairesAutomates à pilePropriétés

    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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Formes normales de grammairesAutomates à pilePropriétés

    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, ǫ)

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Formes normales de grammairesAutomates à pilePropriétés

    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

    Philippe ÉZÉQUEL Langage(s)

  • IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Formes normales de grammairesAutomates à pilePropriétés

    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)

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Formes normales de grammairesAutomates à pilePropriétés

    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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

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

    Plan

    1 Introduction

    2 Langages réguliers

    3 Langages hors-contexte

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

    5 Algorithmique du texte

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    Machines 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 _ # ...

    Philippe ÉZÉQUEL Langage(s)

  • IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

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

    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 ′,⊲).

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

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

    Variantes

    ruban semi-infini,

    plusieurs têtes,

    plusieurs rubans,

    déterministes,

    indéterministes. . .

    constructivement équivalentes

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

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

    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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

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

    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é

    Philippe ÉZÉQUEL Langage(s)

  • IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

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

    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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

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

    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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    DictionnairesRecherche de motifDistance d’édition

    Plan

    1 Introduction

    2 Langages réguliers

    3 Langages hors-contexte

    4 Autres classes de langages

    5 Algorithmique du texteDictionnairesRecherche de motifDistance d’édition

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    DictionnairesRecherche 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

    Philippe ÉZÉQUEL Langage(s)

  • IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    DictionnairesRecherche de motifDistance d’édition

    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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    DictionnairesRecherche de motifDistance d’édition

    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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    DictionnairesRecherche de motifDistance d’édition

    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). . .

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    DictionnairesRecherche de motifDistance d’édition

    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 ( ?)

    Philippe ÉZÉQUEL Langage(s)

  • IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    DictionnairesRecherche de motifDistance d’édition

    Algorithme KMP : exemple

    Avec le motif aab :

    ǫǫ a aa aabaaba a

    ab

    b

    b

    b a

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    DictionnairesRecherche de motifDistance d’édition

    Définition

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

    distance d’édition entre 2 mots u et v : nombre minimald’opérations d’édition pour transformer u en v .

    dE (abbaba, babba) ≤ 3 :

    abbaba −→ babbaba−→ babbab−→ babba

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    DictionnairesRecherche de motifDistance d’édition

    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. . .

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    DictionnairesRecherche de motifDistance d’édition

    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))

    Philippe ÉZÉQUEL Langage(s)

  • IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    DictionnairesRecherche de motifDistance d’édition

    Calcul pratique : mise en place

    Soit à calculer dE (bab, abba)

    bab

    a b b a

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    DictionnairesRecherche de motifDistance d’édition

    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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    DictionnairesRecherche de motifDistance d’édition

    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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionLangages réguliers

    Langages hors-contexteAutres classes de langages

    Algorithmique du texte

    DictionnairesRecherche de motifDistance d’édition

    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

    Philippe ÉZÉQUEL Langage(s)

    IntroductionMots et langagesHiérarchie de Chomsky

    Langages réguliersLangages reconnaissablesLangages rationnelsPropriétésUtilisations

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

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

    Algorithmique du texteDictionnairesRecherche de motifDistance d'édition