Languages Formels

TP3: Grammaires, Formes normales et décidabilité

Exercice 1 (Indécidabilité)

Montrer que pour deux langages algébriques L et L', les problèmes suivants sont indécidables :

  • L est-il rationnel ?
  • L ∩ L' est-il aglébrique ?
  • &Lmacr; est-il algébrique ?

    • Exercice 2 (Propriét\és de fermeture)

    Montrer que la famille des langages algébriques est fermée par :

  • 1. concaténation et itération ;
  • 2. substitution algébrique (Une substitution σ : Σ → 2Σ'* telle que pour tout a ∈ Σ , σ(a) est algébrique).

    • Montrer que les familles des langages algébriques et des langages linéaires sont fermées par :

  • 3. union et image miroir ;
  • 4. intersection avec un langage rationnel ;
  • 5. morphisme ;
  • 6. projection inverse (Une projection est un morphisme p: Σ* → Δ * tel que pour tout a ∈ Σ,|p(a)| ≤ 1);
  • 7. morphisme inverse.

    • Exercice 3

    Soit G= (Σ,V,P,S) une grammaire algébrique. Une variable x ∈ V est strictement récursive (SR) s'il existe une dérivation x →* uxv dans G avec u,v ∈ Σ +. L'objectif est de montrer qu'une grammaire algébrique sans variable SR engendre un langage rationnel.
  • 1. Étant données une grammaire algébrique G= (Σ,V,P,S) et une variable x ∈ V, montrer que l'on peut effectivement calculer l'ensemble
    • Z= { y ∈ V | ∃ x →* uyv avec u,v ∈ Σ+ }.
  • 2. Montrer que l'on peut décider si une grammaire algébrique contient des variables SR.
  • 3. Soit G= (Σ,V,P,S) une grammaire algébrique sans variable SR. Montrer que l'on peut effectivement construire une grammaire algébrique G'= (Σ,V',P',S') réduite, propre, sans variable SR et telle que LG'(S') = LG(S) ∖ { ε }.
  • 4. Soit G= (Σ,V,P,S) une grammaire algébrique réduite, en forme normale de Greibach et sans variable SR. Montrer qu'il existe une constante K ∈ &nat; telle que pour toute dérivation gauche x →* uα avec u ∈ Σ* et α ∈ V* on a |α| ≤ K .
  • 5. Soit G= (Σ,V,P,S) une grammaire algébrique réduite, en forme normale de Greibach et sans variable SR. Montrer que le langage engendré LG(S) est rationnel.

    • Soit G= (Σ,V,P,S) une grammaire algébrique propre. Soit x ∈ V et soient

  • A= {α ∈ (Σ ∪ V)* | x → xα ∈ P }
  • B= {β ∈ (Σ ∪ V ∖ {x} )(\Sigma ∪ V)* | x → β ∈ P }
    • On définit la grammaire G'= (Σ,V',P',S) en ajoutant une variable x' (V' = V ⊎ {x'}) et en remplaçant les règles de G issues de x par les règles x → β + β x' pour β ∈ B et x' → α + α x' pour α ∈ A.
  • 6. Montrer que si y →* uzv dans G' avec y,z ∈ V et u,v ∈ Σ *, alors y →* uzv dans G.
  • 7. Montrer que si G n'a pas de variable SR alors il en est de même pour G'.
  • 8. Soit G= (Σ,V,P,S) une grammaire algébrique sans variable SR. Montrer que l'on peut effectivement construire une grammaire algébrique G'= (Σ,V',P',S) r\'eduite, en forme normale de Greibach, sans variable SR et telle que LG'(S') = LG(S) ∖ { ε }.
  • 9. En déduire qu'un langage est rationnel si et seulement si il peut être engendré par une grammaire algébrique sans variable SR.