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)

  • 1. Montrer que le langage Lcross={ an bm cn dm | n,m ≥ 0 } n'est pas algébrique.
  • 2. Montrer que le langage Lcopy = { ww | w ∈ {a,b}* } n'est pas algébrique.
  • 3. Montrer que le langage {an bn cp dp | n,p ≥ 0} est algébrique mais pas linéaire.
  • 4. Montrer que le langage {an bn cm |n,m ≥ 0} ∪ {an bm cm | n,m ≥ 0} est algébrique et inhéremment ambigu. On pourra appliquer le lemme aux mots aK+K! bKcK puis aK bK cK+K! et exhiber deux arbres de dérivations différents pour le mot aK+K! bK+K! cK+K!.

    Exercice 3

    Donner la forme normale de Chomsky de la grammaire ({S,A,B},{a,b},P,S) définie par les productions :

  • S → bA|aB
  • A → bAA|aS|a
  • B → aBB|bS|b

    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

  • 1. l'inclusion K ⊆ L est indécidable ;
  • 2. l'inclusion L ⊆ K est décidable