Langages Formels : Exercice à rendre

1. Montrer qu'un langage L est déterministe et préfixe (L∩LΣ⁺=∅) ssi il existe un automate déterministe qui accepte L par pile vide.

2. Montrer que pour les automates à pile déterministes, l'acceptation par pile vide est équivalente à l'acceptation par pile vide ET état final.