Overgangstabellen

Overgangstabellen zijn tabellen die de overgangsfunctie van een eindige automaat weergeven. Voor elke combinatie van de huidige toestand en een invoerteken uit het alfabet bepaalt de tabel wat de volgende toestand is en, in sommige varianten, welk uitvoer of welke actie volgt.

In een deterministische eindige automaat (DFA) wijst elke combinatie van toestand en invoerexact één volgende toestand aan. In een niet-deterministische eindige automaat (NFA) kan een cel meerdere mogelijke volgende toestanden bevatten. Een overgangstabel kan volledig zijn (voor alle combinaties een invoer) of gedeeltelijk (ssen alleen voor bepaalde combinaties gedefinieerd).

Overgangstabellen worden ook gebruikt om uitvoer te modelleren. Bij Mealy-machines hangt de uitvoer af van de overgang (toestand en invoer), terwijl bij Moore-machines de uitvoer aan de toestanden zelf is gekoppeld. Tabellen kunnen zo worden vormgegeven dat ze zowel toestanden, invoeren als eventuele uitvoer of acties bevatten.

Toepassingen van overgangstabellen liggen in de theorie van formele talen, bij de bouw van lexical analyzers en parsers, in protocol- en besturingssystemen, en in hardwareontwerp waar toestandsmachines helpen het gedrag van systemen te beschrijven en te implementeren.

Constructie van een overgangstabel begint met het bepalen van het alfabet, de toestandsverzameling, de starttoestand en de accepttoestanden. Vervolgens worden de regels ingevuld: definieer voor elke toestand en invoer de volgende toestand (en eventuele uitvoer). Vaak wordt een trap- of dode toestand toegevoegd om de tabel volledig te maken.

Voorbeeld: een DFA die strings over {0,1} laat eindigen op 0 heeft twee toestanden: q0 (start) en q1 (eindigt op 0). Overgangen: q0 -0-> q1, q0 -1-> q0; q1 -0-> q1, q1 -1-> q0. Accepttoestand is q1.