Cette page propose des exercices corrigés sur : automate à pile.
Exercice 1
La grammaire (linéaire) S → aSb | ε produit le langage {anbn : n ≥ 0}. En vous inspirant de cet exemple, proposer des grammaires pour chacun des langages suivants : {a2n(bc)3n : n ≥ 0}, {a2nb3c20n : n ≥ 0}, {a2nb3nc20 : n ≥ 0}, {ambn : m ≥ n ≥ 0}
1 – S → aaSbcbcbc | ε
2 – S → aaSc20 | bbb
3 – S → Xc20; X → aaXbbb | ε
4 – S → aS | aSb | ε
Exercice 2
Quel langage est généré par la grammaire suivante :
S →aSa | aBa
B →bB | b
Donner l’automate à pile engendré par le langage suivant : L(G) ={anbmcmd2n | n≥0, m > 0}.
Dans la grammaire, la première règle génère récursivement autant de a à chaque extrémité du mot. La deuxième règle génère au moins un b à l’intérieur du mot. Le langage généré est donc L(G) = {anbman | n > 0, m > 0}.
Avant de construire l’automate il faut avant tout comprendre les règles de grammaire. Nous remarquons que les extrémités sont en puissance n tandis que le centre en puissance m. Le langage peut donc être généré par des règles du type A→aAa|B. Nous en déduisons les deux règles générant le langage S →aSdd | A ; A →bAc | bc
Exercice 3
Nous prenons un automate produisant dans palindrome, c’est-à-dire des mots qui se lise de la même façon que ce soit en lecture gauche ou en lecture droite. L’automate est alors :
Donner la table de transition et toutes les dérivations pour les mots ab et abb. Puis montrer par une dérivation réussie que les mots aaaa et baab sont des palindromes.
Dérivation pour le mot ab :
Dérivation pour le mot abb :
Dérivation réussie pour les mots aaaa et baab :
Exercice 4
Soit l’alphabet A = {a, b} et le langage L = {a* b}. Écrire la grammaire de ce langage. Trouver un automate à pile pouvant lire ce langage.
G = { T = {a,b} , N = {S} , S = {S} , P = { S -> b, S -> aS } }
Ici on remarque que la pile n’est pas utile, l’utilisation nulle d’une pile revient à utiliser une lettre vide.
Avec lambda la lettre vide.
Exercice 5
Soit l’alphabet A = {a, b} et le langage L = { an bp / n >= 0 et n <= p <= 2n }. Ecrire la grammaire de ce langage et montrer que c’est un langage algébrique. Trouver un automate à pile pouvant lire ce langage.
G = {T = {a,b}, N = {S} , S = S, P = { S -> ε | aSb | aSbb }}
On peut aussi écrire la grammaire de manière suivante
On remarque que les règles respectent bien le format des grammaires de type 2. Cependant, cette grammaire ne respecte pas le format de type 3.
Z est le symbole que l’on met dans la pile à l’initialisation (symbole de fin de pile).
Exercice 6
Ecrire une grammaire algébrique pouvant écrire n’importe quelle expression régulière avec l’alphabet {0,1}. Pour information la grammaire algébrique contient l’alphabet {0,1,(,), ∪,*, ∅, ε }. Tester sur l’expression régulière (0 ∪ (10)*1)*
Reprenons les règles pour former une expression régulière :
0 ou 1 seul : S→0 | 1
Mot vide ou epsilon : S→∅ | ε
Union de deux sous-mots : S→S ∪ S
Concaténation de deux sous-mots : S→ SS
Etoile d’un sous-mot : S→S*
Parenthésage de priorité : S→(S)
En prenant le mot nous obtenons les dérivations suivantes :
Ce qui donne l’arbre de dérivation suivant :
