Langages acceptés,

langages décidés et automates

La notion de langage décidé n’est valable que pour des automates déterministes.

– Automate fini déterministe :

langage accepté ≡ langage décidé.

– Th.: Étant donné une grammaire hors-contexte G (et donc un automate à pile par le théorème d’équivalence), il existe un algorithme pour déterminer si un mot donné appartient à L(G).

– Automate à pile déterministe:

langage accepté ≡ langage décidé, si il n’y a pas de transition sur ε.