Languages Formels

TP2: Grammaires

Exercice 1

Montrer que les langages suivants sont algébriques :

  • 1. {uũ : u ∈ {a,b}∗} où ũ est l'image miroir
  • 2. {an b m : n ≠ m, n,m ∈ N}
  • 3. {an bp cq : n,q≥0, p≥n+q}
  • 4. {anbp : 0 ≤ n, n ≤ p ≤ 2n}

    • Exercice 2

    Soit G= (Σ, V1 ⋃ V2, P1 ⋃ P2) une grammaire vérifiant :

  • V1 ∩ V2= ∅
  • P1 ⊆ V1 × (V1 Σ∗ ⋃ Σ∗)
  • P2 ⊆ V2 × (Σ∗ V2 V1∗ ⋃ Σ∗)

    • Montrer que pour tout x ∈ V1 ⋃ V2, LG(x) est un langage linéaire

    Exercice 3

    Donner une grammaire algébrique qui engendre le langage L3={w∈{a, b}∗ | |w|a= 2|w|b}. Prouver que votre grammaire engendre bien le langage L3.

    Exercice 4

    On considère la grammaire suivante :

  • S → if c then S else S
  • S → if c then S
  • S → a

    • Montrer qu'elle est ambigue mais que le langage engendré ne l'est pas.