Exercices 2 (Solutions)

Il existe plusieurs façons de décrire les langages réguliers, y compris les grammaires régulières et les expressions régulières, ainsi que les grammaires non-récursives utilisant des expressions régulières. Toutes ces techniques de description sont équivalentes, de sorte qu'elles produisent exactement les langages réguliers, mais elles ne sont évidemment pas identiques.

Ces méthodes de description sont utiles dans des domaines différents. Les grammaires sont le moyen de description le plus universel (voir la hiérarchie de Chomsky), les expressions régulières sont faciles à lire et à réaliser dans un programme (mais limitées aux langages réguliers), et les automates implémentent directement des machines abstraites pour la reconnaissance des langages (c'est pour ça qu'ils sont utilisés dans des générateurs de compilateurs).

Le but de cette série d'exercices est de se familiariser avec les notions de grammaires régulières, d'expressions régulières et de grammaires utilisant des expressions régulières.

Exercice 5

Comme l'expression régulière nous donne deux options (b { a } b et b), il nous faut (au moins) deux productions partant du symbole de départ S, une qui est à la base des mots bb, bab, baab, etc; et une qui produit b (attention à la différence entre le caractère b et le mot b).

Pour concevoir des règles pour produire bb, bab, baab, ..., on travaille de droite à gauche (alternativement de gauche à droite; quelle est la différence?):

Une seule règle suffit pour produire un b:
      S  -->  b
      

On obtient donc la grammaire suivante:
      G5d->g = ( { S, A }, { a, b }, S, { S  -->  b,
                                          S  -->  A b,
                                          A  -->  A a,
                                          A  -->  b } )
      
Si, alternativement, on avait travaillé de gauche à droite, on aurait obtenu la grammaire suivante:
      G5g->d = ( { S, A }, { a, b }, S, { S  -->  b,
                                          S  -->  b A,
                                          A  -->  a A,
                                          A  -->  b } )
      

Exercice 6

Apparemment les mots du langage commencent par ab et se terminent par a. Entre ces deux sous-mots, on peut avoir le mot vide e, le mot ab, le mot abab, etc. Le langage est désormais
      { aba, ababa, abababa }
      =
      { (ab)n a  |  n = 1, 2, 3, ... }
      =
      { w  |  w est une suite alternante de a's et de b's
                commençant et finissant par a et
                contenant au moins un b (deux a's). }
      =
      ...
      
Pour concevoir la grammaire, on travaille de nouveau de droite à gauche: Remarque 1: Que se passerait-il si on n'utilisait pas le symbole non-terminal auxiliaire A, mais si à sa place on mettait S dans toutes les productions?

Remarque 2: L'expression régulière { a } { b } décrit le langage
      { an bp  |  n, p = 0, 1, 2, ... }
      
Ce langage peut être produit par une grammaire avec les productions suivantes (dérivation comme en haut):
      S  -->  S b
      S  -->  A
      A  -->  A a
      A  -->  e        (le mot vide)
      
Attention: Cette grammaire n'est pas régulière, car A peut produire le mot vide e. Il faut remonter cette production:
      S  -->  S b
      S  -->  A
      S  -->  e        (pas de a)
      A  -->  A a
      A  -->  a        (A produit toujours au moins un a)
      

Exercice 7

Tous les mots commencent par a. Après on a un enchaînement de b's et de c's:
      { aw  |  w dans { b, c }* }
      =
      { a,
        ab, ac,
        abb, abc, acb, acc,
        ... }
      =
      ...
      
La grammaire donnée n'est pas régulière, mais on peut la transformer dans une grammaire qui satisfait les contraintes spécifiées:


Christine Röckl
Last modified: Mon Apr 15 14:03:14 DST 2002