Une machine à états finis dont la fonction transition mappe les symboles des entrées et des États à un ensemble (éventuellement vide) des États suivants. Fonction la transition peut également mapper le symbole null (aucun symbole d'entrée nécessaire) et les États aux États suivants.