Övergångstabellen är i grunden en tabellform av övergångsfunktionen. Det tar två argument (ett tillstånd och en symbol) och returnerar ett tillstånd ('nästa tillstånd').
En övergångstabell representeras av följande saker:
- Kolumner motsvarar inmatningssymboler.
- Rader motsvarar tillstånd.
- Poster motsvarar nästa tillstånd.
- Starttillståndet betecknas med en pil utan källa.
- Acceptansläget betecknas med en stjärna.
Exempel 1:
Lösning:
Övergångstabell för given DFA är följande:
| Nuvarande tillstånd | Nästa tillstånd för ingång 0 | Nästa tillstånd för inmatning 1 |
|---|---|---|
| →q0 | q1 | q2 |
| q1 | q0 | q2 |
| *q2 | q2 | q2 |
Förklaring:
- I tabellen ovan anger den första kolumnen alla aktuella tillstånd. Under kolumn 0 och 1 visas nästa tillstånd.
- Den första raden i övergångstabellen kan läsas som, när det aktuella tillståndet är q0, på ingång 0 kommer nästa tillstånd att vara q1 och på ingång 1 kommer nästa tillstånd att vara q2.
- I den andra raden, när det aktuella tillståndet är q1, på ingång 0, kommer nästa tillstånd att vara q0, och på 1 ingång kommer nästa tillstånd att vara q2.
- I den tredje raden, när det aktuella tillståndet är q2 på ingång 0, kommer nästa tillstånd att vara q2, och på 1 ingång kommer nästa tillstånd att vara q2.
- Pilen markerad med q0 indikerar att det är ett starttillstånd och cirkel markerad med q2 indikerar att det är ett sluttillstånd.
Exempel 2:
Lösning:
Övergångstabell för given NFA är följande:
| Nuvarande tillstånd | Nästa tillstånd för ingång 0 | Nästa tillstånd för inmatning 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q1, q2 | q2 |
| q2 | q1 | q3 |
| *q3 | q2 | q2 |
Förklaring:
- Den första raden i övergångstabellen kan läsas som, när det aktuella tillståndet är q0, på ingång 0 kommer nästa tillstånd att vara q0 och på ingång 1 kommer nästa tillstånd att vara q1.
- I den andra raden, när det aktuella tillståndet är q1, kommer nästa tillstånd på ingång 0 att vara antingen q1 eller q2, och på 1 ingång kommer nästa tillstånd att vara q2.
- I den tredje raden, när det aktuella tillståndet är q2 på ingång 0, kommer nästa tillstånd att vara q1, och på 1 ingång kommer nästa tillstånd att vara q3.
- I den fjärde raden, när det aktuella tillståndet är q3 på ingång 0, kommer nästa tillstånd att vara q2, och på 1 ingång kommer nästa tillstånd att vara q2.