Languages Formels
TP4: Grammaires
Exercice 1
Le langage Lprime= { ap | p est premier} peut-il être engendré par une grammaire contextuelle ?
Exercice 2 (Applications du lemme d'Ogden)
Exercice 3
Donner la forme normale de Chomsky de la grammaire ({S,A,B},{a,b},P,S) définie par les productions :
Montrer que si un mot u est engendré par un non-terminal A, alors il existe des mots u1 et u2 respectivement engendrés par B et C tels que A → BC ∈ P.
En déduire un algorithme en O(n3) capable de tester si un mot u, où |u|=n, est engendré par G.
Exercice 4
On considère le langage L=LG(S) où la grammaire G est définie par S → aSSb+c. Montrer que tout langage rationnel inclus dans L est fini.
Exercice 5.
Soit K un langage rationnel et L un langage algébrique. Montrer que