Cette page propose des exercices corrigés sur la théorie des langages, plus précisemment sur les automates à 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 :

exercices corrigés sur la théorie des langages les automates à pile

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.

exercices corrigés sur la théorie des langages les automates à pile

Dérivation pour le mot ab :

exercices corrigés sur la théorie des langages les automates à pile

Dérivation pour le mot abb :

exercices corrigés sur la théorie des langages les automates à pile

Dérivation réussie pour les mots aaaa et baab :

exercices corrigés sur la théorie des langages les automates à pile

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.

exercices corrigés sur la théorie des langages les automates à pile

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.

exercices corrigés sur la théorie des langages les automates à pile

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 :

exercices corrigés sur la théorie des langages les automates à pile

Ce qui donne l’arbre de dérivation suivant :

exercices corrigés sur la théorie des langages les automates à pile

Partager
fr_FRFR
%d blogueurs aiment cette page :