Overgangstabellen er dybest set en tabelformet repræsentation af overgangsfunktionen. Det tager to argumenter (en tilstand og et symbol) og returnerer en tilstand (den 'næste tilstand').

En overgangstabel er repræsenteret af følgende ting:

boble sortering i java

• Kolonner svarer til inputsymboler.
• Rækker svarer til stater.
• Indtastninger svarer til den næste tilstand.
• Starttilstanden er angivet med en pil uden kilde.
• Accepttilstanden er angivet med en stjerne.

Eksempel 1:

Løsning:

Overgangstabel for givet DFA er som følger:

Forklaring:

nbsp

• I ovenstående tabel angiver den første kolonne alle de aktuelle tilstande. Under kolonne 0 og 1 vises de næste tilstande.
• Den første række i overgangstabellen kan læses som, når den aktuelle tilstand er q0, på input 0 vil den næste tilstand være q1 og på input 1 vil den næste tilstand være q2.
• I den anden række, når den aktuelle tilstand er q1, på input 0, vil den næste tilstand være q0, og på 1 input vil den næste tilstand være q2.
• I den tredje række, når den aktuelle tilstand er q2 på input 0, vil den næste tilstand være q2, og på 1 input vil den næste tilstand være q2.
• Pilen markeret med q0 angiver, at det er en starttilstand, og cirkel markeret med q2 angiver, at det er en sluttilstand.

Eksempel 2:

Løsning:

Overgangstabel for givet NFA er som følger:

Forklaring:

• Den første række i overgangstabellen kan læses som, når den aktuelle tilstand er q0, på input 0 vil den næste tilstand være q0 og på input 1 vil den næste tilstand være q1.
• I den anden række, når den aktuelle tilstand er q1, vil den næste tilstand på input 0 være enten q1 eller q2, og på 1 input vil den næste tilstand være q2.
• I den tredje række, når den aktuelle tilstand er q2 på input 0, vil den næste tilstand være q1, og på 1 input vil den næste tilstand være q3.
• I den fjerde række, når den aktuelle tilstand er q3 på input 0, vil den næste tilstand være q2, og på 1 input vil den næste tilstand være q2.