TD 9 - Automates et Langages - RICM

Notations:  les majuscules sont utilisées pour les non-terminaux, S est le symbole initial.

Exercice 1. On dérive dans des grammaires

  1. Dériver si possible dans la grammaire (S->Sab, S->e) les mots bbbaabbaaa, abababab. Dessiner les arbres. Quel est le langage engendré?
  2. Dériver si possible dans la grammaire (S->bSa, S->R, R->aRb, R->e) les mots bbbaabbaaa, abababab. Dessiner les arbres. Quel est le langage engendré?

Exercice 2. Forme de Backus-Naur

On a la grammaire suivante

Est-ce qu'elle engendre les polinômes  3*x^2+x*y*z^3+7 et 5*x*y+4

Si oui, dessiner les arbres de dérivation

Exercice 3. On conçoit les grammaires

Construire les grammaires (hors contexte) pour les langages suivants:

  1. Tous les mots sur {a,b} de longueur impaire
  2. Palindromes sur l'alphabet {a,b}
  3. Tous les mots sur {a,b} qui ont autant de a que de b (ce n'est pas facile)
  4. Les expressions régulières sur {a,b}  (!!!)
  5. Les expressions Booléennes de ADA
  6. {am bn cm+n| m,n Î N}

Exercice 4. Automate => Grammaire régulière

Construire les grammaires (hors contexte) pour les langage des automates suivants (déjà vus):

 

 

Exercice 5.  Grammaire régulière => Automate

Construire les automates pour les grammaires suivantes :

  1. S->aB, S->bA, B->bB, A->aA, A->e, B->e
  2. S->abaaA, S->aabb, A->abS, A->aaa

 

Retour