Languages Formels : Exercice à rendre

Exercice 4

On considère des systèmes dont le fonctionnement peut être modélisé par une variante d'automate à pile qui n'a pas de canal d'entrée. Un tel système évolue donc seulement en fonction de l'état de contrôle et de la lettre en haut de la pile.

  • - Un système à pile S est un quadruplet S=(Q, Γ, δ , q0) où Q, Γ, δ et q0 sont respectivement l'ensemble des états de contrôle, l'alphabet de pile, la relation de transition δ ⊆(Q×(Γ∪{ε}))×(Q×Γ*) et l'état initial.
  • - Un état de S est un couple (q, α) où q∈Q est un état de contrôle et α ∈ Γ* un mot de pile. L'état initial de S est (q0, ε). Un état (q', α') est directement accessible à partir d'un état (q, α), ce que l'on note (q, α) ⇒ (q', α'), s'il existe β, a et u tels que α=βa, α'=βu et ((q, a),(q', u)) ∈ δ. La clôture réflexive et transitive de ⇒ est notée ⇒*.
  • - On notera une transition ((q, ε),(q', a)) par (q, a+, q'); de même une transition ((q, a),(q', ε)) sera notée (q, a-, q').
  • - Le langage de la pile de S dans l'état q, noté L(S, q), est défini par
  • L(S, q):={α| α ∈ Γ*, (q0, ε) ⇒* (q, α)}
    • Le langage de la pile de S, noté L(S), est la réunion des L(S, q) pour q ∈ Q.

    1. Expliquer comment on peut simuler un système à pile S quelconque par un autre ayant une relation de transition dans ((Q×Γ)×(Q×{ε}))∪((Q×{ε})×(Q×Γ)).

    On considère dans toute la suite de l'exercice que δ satisfait cette contrainte et peut donc être représentée par un ensemble fini de triplets (q, x, q') où chaque x est de la forme a+ ou a-. On associe alors à un système à pile S=(Q, Γ, δ , q0) l'automate fini S'=(Q, Γ, δ', q0, Q), où tout les états sont acceptants et où la relation de transition δ '⊆ Q×(Γ∪{ε})×Q est la plus petite relation satisfaisant les conditions suivantes :

  • - si (q, a+, q') ∈ δ alors (q, a, q') ∈ δ',
  • - si (q, a-, q') ∈ δ et (q'', a, q)∈ δ'+ alors (q'', ε, q') ∈ δ',

    • où δ'+ représente la clôture transitive de δ'.

  • 2. Soit le système à pile S1 =({1, 2, 3},{a, b}, δ1, 1) où δ1 est l'ensemble
    • {(1, a+, 2),(2, b+, 3),(3, b-, 1),(1, b+, 3)}
  • Dessiner S1 et l'automate associé S'1.
  • 3. Montrer que (q, α) est accessible à partir de (q0, ε) dans S si et seulement si q est accessible dans S' par le mot α.
  • 4. Montrer que pour tout q∈Q, le langage L(S, q) est rationnel ; en conclure que le langage de la pile, L(S), est aussi rationnel.
  • 5. Expliquer comment calculer δ' et prouver la terminaison de votre algorithme.