Perėjimo lentelė iš esmės yra perėjimo funkcijos lentelės vaizdas. Ji turi du argumentus (būseną ir simbolį) ir grąžina būseną ('kitą būseną').
Perėjimo lentelę vaizduoja šie dalykai:
- Stulpeliai atitinka įvesties simbolius.
- Eilutės atitinka būsenas.
- Įrašai atitinka kitą būseną.
- Pradinė būsena pažymėta rodykle be šaltinio.
- Priimta būsena žymima žvaigždute.
1 pavyzdys:
Sprendimas:
Pateiktos DFA perėjimo lentelė yra tokia:
| Dabartinė valstybė | Kita 0 įvesties būsena | Kita 1 įvesties būsena |
|---|---|---|
| →q0 | q1 | 2 k |
| q1 | q0 | 2 k |
| *2 k | 2 k | 2 k |
Paaiškinimas:
- Aukščiau pateiktoje lentelėje pirmame stulpelyje nurodomos visos esamos būsenos. 0 ir 1 stulpeliuose rodomos kitos būsenos.
- Pirmąją perėjimų lentelės eilutę galima nuskaityti taip, kad kai dabartinė būsena yra q0, 0 įėjime kita būsena bus q1, o 1 įėjime kita būsena bus q2.
- Antroje eilutėje, kai dabartinė būsena yra q1, 0 įėjime kita būsena bus q0, o 1 įėjime kita būsena bus q2.
- Trečioje eilutėje, kai dabartinė būsena yra q2 įėjime 0, kita būsena bus q2, o 1 įėjime kita būsena bus q2.
- Rodyklė, pažymėta q0, rodo, kad tai yra pradžios būsena, o apskritimas, pažymėtas q2, rodo, kad tai yra galutinė būsena.
2 pavyzdys:
Sprendimas:
Nurodytos NFA perėjimo lentelė yra tokia:
| Dabartinė valstybė | Kita 0 įvesties būsena | Kita 1 įvesties būsena |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q1, q2 | 2 k |
| 2 k | q1 | 3 k |
| *k3 | 2 k | 2 k |
Paaiškinimas:
- Pirmąją perėjimų lentelės eilutę galima nuskaityti taip, kad kai dabartinė būsena yra q0, 0 įėjime kita būsena bus q0, o 1 įėjime kita būsena bus q1.
- Antroje eilutėje, kai dabartinė būsena yra q1, 0 įėjime kita būsena bus q1 arba q2, o 1 įėjime kita būsena bus q2.
- Trečioje eilutėje, kai dabartinė būsena yra q2 įėjime 0, kita būsena bus q1, o 1 įėjime kita būsena bus q3.
- Ketvirtoje eilutėje, kai dabartinė būsena yra q3 įėjime 0, kita būsena bus q2, o 1 įėjime kita būsena bus q2.