Beschouw de volgende automaat:
Deze automaat heeft als invoeralfabet 4 symbolen, die we aangeven als 00, 01, 10, en 11.
Het uitvoeralfabet bestaat uit twee symbolen: 0 en 1. Als we de invoer opvatten als twee binaire getallen (“van rechts naar links”), waarvan de bits steeds één invoersymbool vormen, dan kunnen we de uitvoer zien als de som van deze twee getallen.
De toestand houdt steeds bij wat we moeten “onthouden” voor de volgende optelling.
We kunnen de overgangen van deze automaat ook beschrijven in de vorm van een tabel; toestand’ is hierin de volgende toestand.
Input | Toestand | Toestand' | Output |
---|---|---|---|
00 | 0 | 0 | 0 |
01 | 0 | 0 | 1 |
10 | 0 | 0 | 1 |
11 | 0 | 1 | 0 |
00 | 1 | 0 | 1 |
01 | 1 | 1 | 0 |
10 | 1 | 1 | 0 |
11 | 1 | 1 | 1 |
Een voorbeeld van invoer- en uitvoerreeksen geven we hieronder.
01010 - inputreeks A (v.r.n.l.)
00111 - inputreeks B
11100 - toestandenreeks
10001 - outputreeks
Deze reeksen zijn hier van rechts naar links weergegeven. Op die manier zie je sneller welke getallen dit voorstellen: A (v.l.n.r. 01010, decimaal 10) en B (11100, decimaal 7) geeft als output: 10001 (decimaal 17).
Links en Verdieping
Eindige automaten (finite state machines) worden op veel plaatsen in de informatica en ICT gebruikt, van het laagste hardware-niveau tot abstracte Turingmachines.
Zo zou je met behulp van een geheugen (ROM) en een register een eindige automaat in hardware kunnen maken.
Er is een directe relatie tussen eindige automaten en reguliere expressies.
Bij het verwerken van invoer in een programma komen deze vaak van pas.
Ook voor het programmeren van een Arduino vormen eindige automaten een handig programmeerhulpmiddel.