## Eindige automaten

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.