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.