Tabelul de tranziție este practic o reprezentare tabelară a funcției de tranziție. Ia două argumente (o stare și un simbol) și returnează o stare („starea următoare”).
Un tabel de tranziție este reprezentat de următoarele lucruri:
- Coloanele corespund simbolurilor de intrare.
- Rândurile corespund stărilor.
- Intrările corespund stării următoare.
- Starea de pornire este indicată de o săgeată fără sursă.
- Starea de acceptare este indicată cu o stea.
Exemplul 1:
Soluţie:
Tabelul de tranziție al DFA dat este următorul:
| Starea actuală | Următoarea stare pentru intrarea 0 | Următoarea stare de intrare 1 |
|---|---|---|
| →q0 | q1 | q2 |
| q1 | q0 | q2 |
| *q2 | q2 | q2 |
Explicaţie:
- În tabelul de mai sus, prima coloană indică toate stările curente. Sub coloana 0 și 1, sunt afișate următoarele stări.
- Primul rând al tabelului de tranziție poate fi citit ca, când starea curentă este q0, pe intrarea 0 următoarea stare va fi q1 și pe intrarea 1 următoarea stare va fi q2.
- În al doilea rând, când starea curentă este q1, la intrarea 0, următoarea stare va fi q0, iar la 1 intrare următoarea stare va fi q2.
- În al treilea rând, când starea curentă este q2 la intrarea 0, următoarea stare va fi q2, iar la 1 intrare următoarea stare va fi q2.
- Săgeata marcată cu q0 indică faptul că este o stare de început, iar cercul marcat cu q2 indică faptul că este o stare finală.
Exemplul 2:
Soluţie:
Tabelul de tranziție al NFA dat este următorul:
codul numărului aleatoriu c
| Starea actuală | Următoarea stare pentru intrarea 0 | Următoarea stare de intrare 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q1, q2 | q2 |
| q2 | q1 | q3 |
| *q3 | q2 | q2 |
Explicaţie:
- Primul rând al tabelului de tranziție poate fi citit ca, atunci când starea curentă este q0, pe intrarea 0 următoarea stare va fi q0 și pe intrarea 1 următoarea stare va fi q1.
- În al doilea rând, când starea curentă este q1, la intrarea 0 următoarea stare va fi fie q1, fie q2, iar la 1 intrare următoarea stare va fi q2.
- În al treilea rând, când starea curentă este q2 la intrarea 0, următoarea stare va fi q1, iar la 1 intrare următoarea stare va fi q3.
- În al patrulea rând, când starea curentă este q3 la intrarea 0, următoarea stare va fi q2, iar la 1 intrare următoarea stare va fi q2.