We behandelen hier een ander soort automaten: eindige automaten.
Ook hier weer gaat het om het werken met vormen: een eindige automaat verwerkt een reeks invoersymbolen tot een reeks uitvoersymbolen.
De uitvoersymbolen kunnen verschillen van de invoersymbolen.
Een eindige automaat bestaat uit de volgende onderdelen:
een verzameling toestanden; meestal geven we een toestand een naam of een nummer;
één van deze toestanden geven we aan als de begintoestand;
een verzameling invoersymbolen (het invoeralfabet);
een verzameling uitvoersymbolen (het uitvoeralfabet);
een verzameling toestandsovergangen; bij een overgang hoort (gewoonlijk) een invoersymbool en (gewoonlijk) een uitvoersymbool.
Voorbeeld van een automaat. A, B, en C zijn de toestanden.
A is de begintoestand. Het invoeralfabet is {M, T}.
Het uitvoeralfabet is {M+, H+}. Bij sommige overgangen verandert
de toestand niet.
We tekenen een automaat op de volgende manier:
een toestand geven we aan met een cirkel (“bolletje”);
een toestandsovergang geven we aan met pijl van de ene naar de andere toestand; bij deze pijl schrijven we het bijbehorende invoer- en uitvoersymbool.
de begintoestand geven we aan met een dubbele inkomende pijl.