Languages Formels

TP5: Automates à piles

Exercice 1 (Exemples d'automates à pile)

  • 1. Construire un automate à pile reconnaissant le langage L1 = { uũ | u ∈ Σ*}
  • 2. Construire un automate à pile reconnaissant le langage de Dyck D*n
  • 3. Construire un automate à pile reconnaissant le langage L2 ={w ∈ {a,b}* | |w|a = 2 |w|b}
  • 4. Construire un automate à pile reconnaissant par pile vide le langage L3 = { an bp | 1 ≤ n ≤ p ≤ 2 n }

    • Exercice 2 (Variantes d'automates à pile)

    Soit A = (Q, Σ, Z, T, q0, z0, F) un automate à pile.

  • 1. Montrer que l'on peut construire un automate à pile A' reconnaissant le même langage et tel que T' ⊆ Q' × Z × (Σ ∪ {ε}) × Q' × Z≤ 2.
  • 2. Montrer que l'on peut construire un automate à pile A'' équivalent à A tel que les mouvements de la pile sont uniquement du type push ou pop ou skip.

    • Exercice 3

    On s'intéresse ici à des automates dont l'alphabet de pile Γ est un singleton {z}.

  • a) Montrer que le langage L={anbmc| n≥ m ≥ 1} peut être accepté par pile vide et état final par un automate dont l'alphabet de pile est un singleton.
  • b) Montrer que le langage L={anbmc| n≥ m ≥ 1} ne peut pas être accepté par pile vide par un automate dont l'alphabet de pile est un singleton.

    • Exercice 4

  • 1. Soit A = (Q,Σ,Z,T,q0,z0,F,K) un automate à pile déterministe reconnaissant par sommet de pile et état final (une configuration (q,az) est acceptante si (q,z) ∈ K ⊆ Q × Z). Montrer qu'on peut effectivement construire un automate à pile déterministe équivalent reconnaissant par état final.
  • 2. Soit A un automate à pile déterministe. Montrer qu'on peut effectivement construire un automate à pile qui reconnaît le même langage et dont les ε-transitions sont uniquement effaçantes : (p,x) ε→ (q,ε).

    • Exercice 5 (Autres Exemples)

  • Montrer que le complémentaire du langage L0 où L0 = { uu | y ∈ Σ*} peut être reconnu par un automate à pile.
  • Construire un automate à pile reconnaissant le complémentaire du langage L1 où L1 = { uũ | u ∈ Σ*}