Cours n° 18, 15 mars 2012

Jean-François Perrot

Les grammaires "Context-Free" et la hiérarchie de Chomsky

  1. Règles sans contexte
    1. Définition
    2. Exemples
    3. Non-exemples
      1. Lemme de la double étoile (en anglais pumping lemma)
      2. Exemples
    4. Propriétés de fermeture de la classe des langages CF
      1. Union
      2. Produit
      3. Étoile
      4. Intersection avec un langage régulier

  2. Automates à pile
    1. Idée générale
    2. Les deux modèles pour l'acceptation
    3. La question du déterminisme

  3. Hiérarchie de Chomsky
    1. Grammaires linéaires
    2. Grammaires linéaires unilatères et langages réguliers

  1. Règles sans contexte

    1. Définition

      Une grammaire context-free est une grammaire dont toutes les règles sont de la forme
      A -> w
      où A est un symbole non-terminal et w un mot quelconque.

      On note deux différences par rapport aux grammaires context-sensitive :

      • l'absence de contexte dans le membre gauche :
        Dans le modèle context-sensitive, on interprète une règle du genre uAv -> uwv
        comme "le non-terminal A se réécrit en w dans le contexte (u, v)".
        Dans le modèle context-free, on dira que
        "le non-terminal A se réécrit en w indépendamment du contexte où il apparaît".
        On voit donc que l'adjectif anglais free doit être traduit en français non point par libre,
        mais par affranchi, libéré, ou même franc au sens que ce mot avait chez Ronsard :
        Franc des liens du corps pour n'estre qu'un esprit.

      • l'absence de contrainte sur le membre droit :
        Le modèle context-sensitive exige que w soit non-vide, pour assurer le caractère "non-contractant"
        de ses règles.
        Le modèle context-free n'a que faire de cette précaution !
        Il s'ensuit que stricto sensu la classe des langages CF n'est pas incluse dans celle des langages CS,
        alors que le modèle CF est de toute évidence une particularisation de CS où tous les contextes sont vides.
        Pour éviter cette absurdité, les définitions officielles de CS (Wikipedia...) ajoutent des règles spéciales S -> ε.
        Nous négligeons ces détails de présentation.

    2. Exemples

      1. Les langage des systèmes bien parenthésés est engendré par la grammaire

        1. S -> SS
        2. S -> ε
        3. S -> (S)
        4. S -> [S]
        5. S -> {S}
        6. S -> <S>

        On peut voir les dérivations de cette grammaire comme les inverses des chaînes de réécritures-réductions
        vues au cours n° 17 : pour notre exemple favori le mot "([]{<<>>}([(){<>}]))", en dérivant "à gauche"

        S -3> (S) -1> (SS) -4> ([S]S) -2> ([]S)-1> ([]SS)-5> ([]{S}S)-6> ([]{<S>}S)-6> ([]{<<S>>}S)-2>([]{<<>>}S)
        -3> ([]{<<>>}(S)) -4> ([]{<<>>}([S])) -1> ([]{<<>>}([SS])) -3> ([]{<<>>}([(S)S]))-2> ([]{<<>>}([()S]))
        -5> ([]{<<>>}([(){S}]))-6> ([]{<<>>}([(){<S>}]))-2> ([]{<<>>}([(){<>}]))

        On aurait pu aussi bien dériver "à droite" : S -3> (S) -1> (SS) -3> (S(S)) -4> (S([S])) -1> (S([SS]))-5> (S([S{S}]))...
      2. Le langage  {anbn | n >0} est engendré par

        1. S -> aSb
        2. S -> ab

      3. Le langage des palindromes {ww~| w∈X*}

        1. S -> ε
        2. S -> aSa
        3. S -> bSb

      4. Le langage des mots contenant autant de a que de b :

        1. S -> SS
        2. S -> aSb
        3. S -> bSa
        4. S -> ε

        Si la validité des grammaires des trois exemples précédents est assez évidente, pour ce dernier il faut faire un petit effort !
        On observe que tout mot w contenant autant de a que de b se décompose (d'une manière unique) en facteurs de la forme
        aub ou bva, où u et v contiennent autant de a que de b : ces facteurs correspondent aux passages par 0 de la fonction
        (nombre de a - nombre de b). Exemple : pour le mot aabaababbbbbbaabaaba
            aabaababbb b b b a a b aa ba -> a abaababb b / b bbaaba a / ba
            1212323210-1-2-3-2-1-2-10-10
        Les facteurs en question sont engendrés par les règles 2, 3, 4. La règle 1 se charge de les concaténer.

        Par exemple, le mot en question sera engendré par  (en dérivant à gauche):
        S  -1>  SS -1>  SSS  -2> aSbSS  -2> aaSbbSS  -1> aaSSbbSS  -1> aaSSSbbSS  -3> aabSaSSbbSS -4> aabaSSbbSS
        -2> aabaaSbSbbSS -4> aabaabSbbSS -2> aabaabaSbbbSS -4> aabaababbbSS -3> aabaababbbbSaS -3> aabaababbbbbSaaS
        -1> aabaababbbbbSSaaS -3> aabaababbbbbbSaSaaS -4> aabaababbbbbbaSaaS -2> aabaababbbbbbaaSbaaS
        -4> aabaababbbbbbaabaaS -3> aabaababbbbbbaabaabSa -4> aabaababbbbbbaabaaba

    3. Non-exemples

      • Lemme de la double étoile (en anglais pumping lemma)
        Soit L un langage CF infini.
        Dans tout mot w de L suffisamment long on peut trouver deux facteurs u et v dont l'un au moins n'est pas vide,
        w = fugvh ∈ L
        tels que, pour tout entier n, on ait fungvnh ∈ L.

        Idée de la preuve :
        le mot w ∈ L étant arbitrairement long, la chaîne de réécritures qui l'engendre est aussi arbitrairement longue ;
        [plus précisément, il existe une branche de l'arbre de dérivation - cf. cours 16 - qui est arbitrairement longue]
        par conséquent il y a au moins un symbole non-terminal T
        • qui apparaît deux fois dans cette chaîne [branche],
        • et qui entre ces deux apparitions apporte une contribution non nulle au mot terminal 
        c'est-à-dire que la suite de réécritures a nécessairement la forme
        S  ->*  fTh  ->*  fuTvh  ->*  fugvh  = w∈ L, avec la contribution uv non vide.
        D'où il suit que T ->* uTv et que T -> g, donc T ->* ungvn pour tout entier n,
        et puisque S  ->*  fTh, S  ->*  fungvnh, c'est-à-dire que fungvnh∈ L pour tout entier n.
        Quod erat demonstrandum.

      • Exemples
        Aucun des exemples de langages CS que nous avons vus au cours 17 n'est CF.

        1. {anbncn | n >0} parce que l'itération simultanée ne concerne que deux facteurs, pas trois !
          on ne pourra donc pas maintenir l'égalité sur les trois a, b et c simultanément.
          De même pour {aibjck | 1≤ i ≤ j ≤ k}, et a fortiori, pour {anbncndn |  n>0} !

        2. Le langage des carrés {ww | w ∈ {a, b}*} demande un peu plus d'attention. Appelons-le L.
          En particulier, il faut un argument qui ne s'applique pas aux palindromes !
          On examine les mots de L qui sont de la forme apbqarbs avec p, q, r, s positifs.
          (en d'autres termes, on prend l'intersection de L avec le langage régulier a+b+a+b+, voir ci-après).
          Les mots en question sont de la forme anbmanbm avec m et n positifs.
          L'idée est que la mécanique CF est incapable de maintenir l'égalité à la fois sur les a et sur les b.
          Pour le montrer on a besoin d'une forme plus forte du lemme précédent, qui précise que le "facteur itérant"
          ugv a une longueur bornée. Soit p la borne en question : choisissons m et n > p.
          Alors le facteur itérant doit être logé
          • soit dans les a du début, ce qui ruine l'équilibre avec les a de la deuxième moitié 
          • soit à cheval sur les a et les b, ce qui détruit la structure de "carré" ww
          • soit dans les b de la première moitié, ce qui ruine l'équilibre avec les b de la deuxième moitié 
          • etc.

    4. Propriétés de fermeture de la classe des langages CF

      • Union
        Soient G1 et G2 deux grammaires CF engendrant deux langages L1 et L2, sur le même alphabet terminal.
        Les deux ensembles de symboles non-terminaux peuvent sans inconvénient être supposés disjoints.
        Il suffit pour engendrer l'union L1∪L2 de prendre la grammaire G ainsi construite :
        • ses symboles non-terminaux sont ceux de G1, ceux de G2 et un nouvel axiome S
        • ses règles sont celles de G1, celles de G2 et deux nouvelles règles : S->S1, S->S2
          où S1 et S2 sont les axiomes de G1 et de G2 .
      • Produit
        Même raisonnement en remplaçant  L1∪L2 par L1L2, et les "deux nouvelles règles : S->S1, S->S2"
        par "une nouvelle règle : S->S1S2".
      • Étoile
        Même raisonnement avec une seule grammaire G1, en remplaçant  L1L2 par L1*,
        et "une nouvelle règle : S->S1S2" par "deux nouvelles règles : S->S1S, S->ε".
      • Intersection avec un langage régulier
        L'intersection de deux langages CF n'est pas CF en général !
        Contre-exemple : 
        • L1 = {anbncp | n >0, p>0} est CF (produit de {anbn | n >0} par c+)
        • L2 = {apbncn | n >0, p>0} est CF (produit de  a+ par {bncn | n >0} )
        • L1∩L2 = {anbncn | n >0} qui n'est pas CF.

        Toutefois, l'intersection d'un langage CF avec un langage régulier est CF.
        Il n'est pas très facile de le démontrer au moyen d'une grammaire.
        En revanche, le résultat sera évident quand nous mettrons en marche les automates à pile,
        qui sont les correspondants des grammaires CF du côté des automates.

        Munis de ce résultat, nous pouvons revisiter la preuve que le langage des carrés n'est pas CF
        comme suit : considérons l'intersection {ww | w ∈ {a, b}*}∩a+b+a+b+ : si le premier langage est CF,
        l'intersection l'est aussi. Or cette intersection est exactement {anbmanbm | m >0, n>0}.
        Il ne reste plus qu'à démontrer que ce dernier langage n'est pas CF, ce qui se fait par le même argument
        que ci-dessus, un tantinet simplifié.


  2. Automates à pile

  3. Hiérarchie de Chomsky

    Chomsky, Noam (1956). "Three models for the description of language". IRE Transactions on Information Theory (2): 113–124.
    L'article original est accessible en pdf sur Wikipedia.
    1. "Type 0" (grammaires générales - machines de Turing),
    2. "Type I" (grammaires CS - automates linéairement bornés), 
    3. "Type II" (grammaires CF - automates à pile),
    4. "Type III" (grammaires linéaires unilatères - automates finis)