Langages Formels : Exercice à rendre

Exercice 1 (Dyck à n paires de parenthèses)

Soit Σ ={a1, . . . , an} ∪ {b1, . . . ,bn} l'alphabet formé de n paires de parenthèses. Un mot w ∈ Σ* est bien parenthésé s'il se réduit au mot vide via les règle ai bi → ε pour 1 ≤ i ≤ n.

Montrer que le langage de Dyck D*n={w ∈ Σ* |w est bien parenthésé} est engendré par la grammaire S → a1 S b1 S + . . . + an S bn S + ε.

Exercice 2 (Langage de Lukasiewicz)

Soit Σ ={a, b}, P={S → aSS+b} soit G=(Σ,{S}, P ). On note L le langage engendré par G. Ce langage est appelé langage de Lukasiewicz.

  • 1. Montrer que tout mot u ∈ L vérifie la propriété (1): |u|b =|u|a + 1.
  • 2. Montrer que tout mot u ∈ L vérifie aussi la propriété (2): ∀ v facteur gauche de u, v ≠ u:|v|a ≥ |v|b.
  • 3. En déduire que L = {u ∈ Σ* | u vérifie (1) et (2)}.
  • 4. On considère le langage de Dyck D*1 à une paire de parenthèses. Montrer que L = D*1b.