Languages Formels

TP7: Automates à piles déterministes

Exercise 1 : Automates à pile avec conditions reconnaissables sur la pile

Un Automate à pile avec conditions reconnaissables sur la pile est un tuple (Q,Σ, Γ, δ, q₀z₀, F) où Q,Σ, Γ, q₀z₀, et F fonctionnent comme dans un Automate à pile, et où l'ensemble des transitions de δ est un sous-ensemble de

Q × Reg(Γ^*) × (Σ ∪ {ε}) × Q × Γ^*

Qui induit une relation sur les configurations de l'automate, où on passe de (q,vg) à (q',vv') en lisant la lettre a si (q, L, a, q', v') est dans δ et vg est dans L. (Sans perte de généralité, on peut oublier les états Q et les voirs comme des lettres de Γ)

Montrer que si un langage est reconnu par un Automate à pile avec conditions reconnaissables sur la pile, il existe un Automate à pile qui le reconnaît, et vice versa.

Exercice 2 : Automate à pile déterministe

Pour chacun de ces langages, dire s'il est reconnaissable par un automate à pile déterministe:

1. L₁ = { uũ | u ∈ Σ^*}

2. L₂ ={w ∈ {a,b}^* | |w|_a = 2 |w|_b}

3. le langage des palindromes { u ∈ {a, b}^* | ũ = u }

4. L₃ = { aⁿ b^p | 1 ≤ n ≤ p ≤ 2 n }

Exercice 3 - Lemme d'itération déterministe

Montrer que pour tout langage déterministe L ⊆ Σ^*, il existe un entier k tel que pour tout w ∈ L avec au moins k lettres marquées, il existe une décomposition w=αuβvγ telle que

1. pour tout n ∈N, αuⁿβvⁿγ ∈ L,

2. soit α,u et β, soit β, v et γ contiennent chacun au moins une lettre marquée ;

3. uβv contient au plus k lettres marquées ;

4. pour tout mot γ' ∈ Σ^*, s'il existe p ∈N tel que αu^pβv^pγ' ∈L alors pour tout p ∈ N on a αu^pβv^pγ' ∈L.

Exercice 4 Automates à compteur

Un automate à compteur est un quintuplet A=(Σ, Q, δ, q₀, F) où Σ est l'alphabet d'entrée, Q est l'ensemble fini des états, q₀ ∈ Q est l'état initial, F ⊆ Q est l'ensemble des états finaux et δ ⊆ Q × {-,0,+} × (Σ ∪ {ε}) × Q × ℤ est la table de transition.

Une configuration est un couple (q, n) ∈ Q × ℤ. La relation d'exécution sur A est engendrée par le passage d'une configuration (q, n) à une configuration (q', n + p) en lisant a, pour a ∈ Σ ∪ {ε} et (q, sign(n), a, q', p) ∈ δ, par clôture réflexive et transitive, avec sign(n) le signe du naturel n. Un mot w est accepté par A s'il existe une exécution de (q₀, 0) à (q, n) en lisant w, avec q ∈ F et n ∈ ℤ quelconque.

1. Montrer que tout langage reconnu par un automate à compteur est algébrique.

2. Donner un automate à compteur pour chacun des langages suivants :

a. L₁:={aⁿb²ⁿ | n ∈ ℕ}

b. L₂:={aⁱb^i+jc^j | i, j ∈ ℕ}

c. L₃:={w|w ∈ {a, b}^*, |w|_b≤|w|_a≤2|w|_b} (utiliser le non-déterminisme)

Exercice 5 : Automate à pile déterministe (encore)

Pour chacun de ces langages, dire s'il est reconnaissable par un automate à pile déterministe:

1. le langage de Dyck D^*_n

2. le langage L₄ = { aⁱb^jc^k | i + j = k }

3. le langage L₅ = { aⁱb^jc^k | i + k = j }