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.

Par définition, un langage est dit régulier, s'il existe une grammaire régulière qui le produit.
Pour chaque langage régulier il existe une (voire plusieurs) expression régulière qui le décrit. Un langage décrit par une expression régulière est régulier.
Pour chaque langage régulier il existe une (voire plusieurs) grammaire utilisant des expressions régulières de manière non-récursive qui le décrit. Un langage décrit par une grammaire utilisant des expressions régulières de manière non-récursive est régulier.

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

On pose un b et on continue à gauche:
```
      S  -->  A b
      
```
Le fait de continuer autrement à gauche est exprimé par l'utilisation d'un nouveau symbole non-terminal.
Ensuite on réalise un enchaînement de a's:
```
      A  -->  A a
      
```
Le fait que le nombre de a's est à priori illimité est exprimé par l'apparition de A et à gauche et à droite de la production.
Pour terminer, le non-terminal A produit le b à gauche des mots:
```
      A  -->  b
      
```

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

On pose un a et on continue à gauche:
```
      S  -->  A a
      
```
Voir aussi exercice 5.
Ensuite on réalise un enchaînement de ab's:
```
      A  -->  A ab
      
```
Voir aussi exercice 5.
Pour terminer, le non-terminal A produit ab à gauche des mots:
```
      A  -->  ab
      
```

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

      { aⁿ b^p  |  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:

D'abord on transforme la répétition à droite en une production récursive:
```
          S  -->  S b
          S  -->  S c
          
```
Le choix entre B et C est simultanément remplacé par les terminaux à droite des règles correspondantes.
Pour terminer, il faut exécuter la production de A dans la grammaire originale:
```
          S  --> a
          
```

Christine Röckl

Last modified: Mon Apr 15 14:03:14 DST 2002