Prijelazna tablica je u osnovi tablični prikaz prijelazne funkcije. Uzima dva argumenta (stanje i simbol) i vraća stanje ('sljedeće stanje').
Prijelaznu tablicu predstavljaju sljedeće stvari:
- Stupci odgovaraju ulaznim simbolima.
- Redovi odgovaraju stanjima.
- Unosi odgovaraju sljedećem stanju.
- Početno stanje označeno je strelicom bez izvora.
- Stanje prihvaćanja označeno je zvjezdicom.
Primjer 1:
Riješenje:
Prijelazna tablica danog DFA je sljedeća:
| Sadašnje stanje | Sljedeće stanje za ulaz 0 | Sljedeće stanje unosa 1 |
|---|---|---|
| →q0 | q1 | q2 |
| q1 | q0 | q2 |
| *q2 | q2 | q2 |
Obrazloženje:
- U gornjoj tablici prvi stupac označava sva trenutna stanja. U stupcima 0 i 1 prikazana su sljedeća stanja.
- Prvi red prijelazne tablice može se čitati kao, kada je trenutno stanje q0, na ulazu 0 sljedeće stanje će biti q1, a na ulazu 1 sljedeće stanje će biti q2.
- U drugom redu, kada je trenutno stanje q1, na ulazu 0 sljedeće stanje bit će q0, a na ulazu 1 sljedeće stanje bit će q2.
- U trećem redu, kada je trenutno stanje q2 na ulazu 0, sljedeće stanje će biti q2, a na ulazu 1 sljedeće stanje će biti q2.
- Strelica označena s q0 označava da je to početno stanje, a krug označen s q2 označava da je to konačno stanje.
Primjer 2:
Riješenje:
Prijelazna tablica datog NFA je sljedeća:
| Sadašnje stanje | Sljedeće stanje za ulaz 0 | Sljedeće stanje unosa 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q1, q2 | q2 |
| q2 | q1 | q3 |
| *q3 | q2 | q2 |
Obrazloženje:
- Prvi red prijelazne tablice može se čitati kao, kada je trenutno stanje q0, na ulazu 0 sljedeće stanje će biti q0, a na ulazu 1 sljedeće stanje će biti q1.
- U drugom redu, kada je trenutno stanje q1, na ulazu 0 sljedeće stanje će biti ili q1 ili q2, a na ulazu 1 sljedeće stanje će biti q2.
- U trećem redu, kada je trenutno stanje q2 na ulazu 0, sljedeće stanje će biti q1, a na ulazu 1 sljedeće stanje će biti q3.
- U četvrtom retku, kada je trenutno stanje q3 na ulazu 0, sljedeće stanje će biti q2, a na ulazu 1 sljedeće stanje će biti q2.