TechCodeview

Overgangstabellen er i utgangspunktet en tabellrepresentasjon av overgangsfunksjonen. Den tar to argumenter (en tilstand og et symbol) og returnerer en tilstand (den 'neste tilstanden').

En overgangstabell er representert av følgende ting:

java binært tre

• Kolonner tilsvarer inngangssymboler.
• Rader tilsvarer stater.
• Oppføringer tilsvarer neste tilstand.
• Starttilstanden er angitt med en pil uten kilde.
• Aksepttilstanden er merket med en stjerne.

Eksempel 1:

Løsning:

Overgangstabell for gitt DFA er som følger:

Forklaring:

streng i array i c

• I tabellen ovenfor indikerer den første kolonnen alle gjeldende tilstander. Under kolonne 0 og 1 vises de neste tilstandene.
• Den første raden i overgangstabellen kan leses som, når gjeldende tilstand er q0, på inngang 0 vil neste tilstand være q1 og på inngang 1 vil neste tilstand være q2.
• I den andre raden, når gjeldende tilstand er q1, på inngang 0, vil neste tilstand være q0, og på 1 inngang vil neste tilstand være q2.
• I den tredje raden, når gjeldende tilstand er q2 på inngang 0, vil neste tilstand være q2, og på 1 inngang vil neste tilstand være q2.
• Pilen merket til q0 indikerer at det er en starttilstand og sirkel merket til q2 indikerer at det er en slutttilstand.

Eksempel 2:

Løsning:

Overgangstabell for gitt NFA er som følger:

Forklaring:

• Den første raden i overgangstabellen kan leses som når gjeldende tilstand er q0, på inngang 0 vil neste tilstand være q0 og på inngang 1 vil neste tilstand være q1.
• I den andre raden, når gjeldende tilstand er q1, på inngang 0 vil den neste tilstanden være enten q1 eller q2, og på 1 inngang vil den neste tilstanden være q2.
• I den tredje raden, når gjeldende tilstand er q2 på inngang 0, vil neste tilstand være q1, og på 1 inngang vil neste tilstand være q3.
• I den fjerde raden, når gjeldende tilstand er q3 på inngang 0, vil neste tilstand være q2, og på 1 inngang vil neste tilstand være q2.