Tabela przejść jest w zasadzie tabelaryczną reprezentacją funkcji przejścia. Przyjmuje dwa argumenty (stan i symbol) i zwraca stan („następny stan”).
Tabela przejściowa jest reprezentowana przez następujące elementy:
- Kolumny odpowiadają symbolom wejściowym.
- Wiersze odpowiadają stanom.
- Wpisy odpowiadają kolejnemu stanowi.
- Stan początkowy jest oznaczony strzałką bez źródła.
- Stan akceptacji jest oznaczony gwiazdką.
Przykład 1:
Rozwiązanie:
Tabela przejściowa danego DFA wygląda następująco:
| Stan obecny | Następny stan dla wejścia 0 | Następny stan wejścia 1 |
|---|---|---|
| →q0 | pytanie 1 | q2 |
| pytanie 1 | q0 | q2 |
| *q2 | q2 | q2 |
Wyjaśnienie:
- W powyższej tabeli pierwsza kolumna wskazuje wszystkie aktualne stany. W kolumnach 0 i 1 pokazane są kolejne stany.
- Pierwszy wiersz tabeli przejść można odczytać następująco: gdy bieżący stan wynosi q0, na wejściu 0 następnym stanem będzie q1, a na wejściu 1 następnym stanem będzie q2.
- W drugim wierszu, gdy aktualny stan to q1, na wejściu 0 kolejnym stanem będzie q0, a na 1 wejściu kolejnym stanem będzie q2.
- W trzecim wierszu, gdy na wejściu 0 obecny stan to q2, kolejnym stanem będzie q2, a na 1 wejściu kolejnym stanem będzie q2.
- Strzałka oznaczona przy q0 oznacza, że jest to stan początkowy, a okrąg przy q2 wskazuje, że jest to stan końcowy.
Przykład 2:
Rozwiązanie:
Tabela przejściowa danego NFA wygląda następująco:
| Stan obecny | Następny stan dla wejścia 0 | Następny stan wejścia 1 |
|---|---|---|
| →q0 | q0 | pytanie 1 |
| pytanie 1 | q1, q2 | q2 |
| q2 | pytanie 1 | q3 |
| *q3 | q2 | q2 |
Wyjaśnienie:
- Pierwszy wiersz tabeli przejść można odczytać następująco: gdy bieżący stan wynosi q0, na wejściu 0 następnym stanem będzie q0, a na wejściu 1 następnym stanem będzie q1.
- W drugim wierszu, gdy bieżący stan to q1, na wejściu 0 następnym stanem będzie q1 lub q2, a na 1 wejściu następnym stanem będzie q2.
- W trzecim wierszu, gdy na wejściu 0 obecny stan to q2, kolejnym stanem będzie q1, a na 1 wejściu kolejnym stanem będzie q3.
- W czwartym wierszu, gdy na wejściu 0 obecny stan to q3, kolejnym stanem będzie q2, a na 1 wejściu kolejnym stanem będzie q2.