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
- Dériver si possible dans la grammaire (S->Sab, S->e) les mots bbbaabbaaa, abababab.
Quel est le langage engendré par cette grammaire? Dessiner
les arbres de dérivation (pas encore vus en cours).
- 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 (en forme de Backus-Naur (BNF)
souvent utilisée pour définir la syntaxe des langages de
programmation)
- <polynome>::= <monome> | <polynome> +
<monome>
- <monome>:: = <atome> | <monome> *
<atome>
- <atome> ::= <variable> | <nombre> |
<variable> ^ <nombre>
- <nombre>::= 2 | 3 | 4 | 7
- <variable>::=x | y | z
Représenter cette grammaire comme (G,S,S,P)
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:
- Tous les mots sur {a,b} de longueur impaire
- Palindromes sur l'alphabet {a,b}
- Tous les mots sur {a,b} qui ont autant de a que de b (ce
n'est pas facile)
- Les expressions régulières sur {a,b} (écrire
cette gramaire en BNF également)
- Les expressions Booléennes de ADA
- {am bn cm+n| m,n Î N}
Exercice 4. Automate => Grammaire régulière
Construire les grammaires (régulières) pour les langages
acceptés par les automates suivants (déjà vus):
Exercice 5. Grammaire régulière => Automate
Construire les automates pour les grammaires suivantes :
- S->aB, S->bA, B->bB, A->aA, A->e, B->e
- S->abaaA, S->aabb, A->abS, A->aaa
Retour