Langages Formels : Exercice à rendre

Exercice 1 : Langages linéaires et automates à un pic

Un automate à un pic est un automate à pile tel que dans tout calcul valide, la taille de la pile n'augmente plus une fois qu'elle a diminué. La taille de la pile peut donc augmenter (au sens large) pendant une première partie du calcul, puis elle ne fait que diminuer (au sens large).

Un langage est à un pic s'il peut être accepté par pile vide par un automate à un pic.

1) Montrer que le langage L={aⁿbⁿ|n ≥ 1} ∪ {aⁿb²ⁿ|n ≥ 1} est un langage linéaire.

2) Montrer que L est un langage à un pic.

3) Montrer que le langage K={ba^i₁ba^i₂b...ba^i_nb | n ≥ 1 et ∃ j,i_j ≠ j} est un langage à un pic.

4) Montrer que tout langage linéaire est un langage à un pic.