Languages Formels

TP6: Automates à piles

Exercice 1 (Exemples d'automates à pile)

1. Construire un automate à pile reconnaissant le langage L₁ = { aⁱb^jc^k | i + j = k }

2. Construire un automate à pile reconnaissant le langage L₂ = { aⁱb^jc^k | i + k = j }

3. Construire un automate à pile reconnaissant le langage des palindromes { u ∈ { a, b }^* | ũ = u }

Où ũ est l'image mirroir de u.

Exercice 2 (Variantes d'automates à pile)

Un automate à pile à double sens peut, à chaque transition, déplacer sa tête de lecture vers la gauche ou vers la droite ou encore la laisser sur place. De plus, on supposera que la donnée w est encadrée par 2 symboles spéciaux (marqueurs) ⊲ et ⊳. Le mot w est donc accepté par l'automate s'il y a un calcul réussi sur ⊲ w ⊳.

De façon équivalente, un automate à pile à double sens est une machine de Turing qui ne peut pas modifier sa bande d'entrée et qui a une seule bande de travail qui est utilisée comme une pile.

a) Montrer que le langage {aⁿbⁿcⁿ | n ≥ 1} peut être accepté par un automate à pile déterministe à double sens.

b) Montrer que le langage {ww|w ∈ {a,b}^*} peut être accepté par un automate à pile à double sens.

c) Montrer que le langage {vcuvw | u, v, w ∈ {a,b}^* } peut être accepté par un automate à pile à double sens.

Exercice 3 (Déterministes et non ambigus)

1. Montrer que tout langage reconnu par un automate à pile déterministe est non ambigu

2. Montrer que l'inclusion est stricte en considérant le langage L = {aⁿbⁿ |n ≥ 1} ∪ {aⁿb²ⁿ | n ≥ 1}.

Exercice 4

Construire un automate à pile acceptant par état final reconnaissant le langage B = { bin(i)$mir(bin(i+1)) | i ≥ 0 } de {0, 1, $}^*

Où bin(i) ∈ {0,1}^* est la représentation en binaire (sans 0 additionnel à gauche) du nombre i, par exemple bin(11)=1011, et où mir(w) est le mot mirroir de w, par exemple mir(bin(12))= 0011.