Prechodová tabuľka je v podstate tabuľková reprezentácia prechodovej funkcie. Vyžaduje dva argumenty (stav a symbol) a vráti stav („ďalší stav“).
Tabuľka prechodu je reprezentovaná nasledujúcimi vecami:
- Stĺpce zodpovedajú vstupným symbolom.
- Riadky zodpovedajú stavom.
- Záznamy zodpovedajú ďalšiemu stavu.
- Počiatočný stav je označený šípkou bez zdroja.
- Akceptovaný stav je označený hviezdičkou.
Príklad 1:
Riešenie:
Prechodová tabuľka danej DFA je nasledovná:
| Súčasný štát | Ďalší stav pre vstup 0 | Ďalší stav vstupu 1 |
|---|---|---|
| →q0 | q1 | q2 |
| q1 | q0 | q2 |
| *q2 | q2 | q2 |
Vysvetlenie:
- Vo vyššie uvedenej tabuľke sú v prvom stĺpci uvedené všetky aktuálne stavy. V stĺpcoch 0 a 1 sú zobrazené ďalšie stavy.
- Prvý riadok tabuľky prechodov možno čítať tak, že keď je aktuálny stav q0, na vstupe 0 bude nasledujúci stav q1 a na vstupe 1 bude nasledujúci stav q2.
- V druhom riadku, keď je aktuálny stav q1, na vstupe 0 bude nasledujúci stav q0 a na 1 vstupe bude nasledujúci stav q2.
- V treťom riadku, keď je aktuálny stav q2 na vstupe 0, nasledujúci stav bude q2 a na 1 vstupe bude nasledujúci stav q2.
- Šípka označená ako q0 označuje, že ide o počiatočný stav a kruh označený ako q2 označuje, že ide o konečný stav.
Príklad 2:
Riešenie:
spať pre javascript
Prechodová tabuľka daného NFA je nasledovná:
| Súčasný štát | Ďalší stav pre vstup 0 | Ďalší stav vstupu 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q1, q2 | q2 |
| q2 | q1 | q3 |
| *q3 | q2 | q2 |
Vysvetlenie:
- Prvý riadok tabuľky prechodov možno čítať tak, že keď je aktuálny stav q0, na vstupe 0 bude nasledujúci stav q0 a na vstupe 1 bude nasledujúci stav q1.
- V druhom riadku, keď je aktuálny stav q1, na vstupe 0 bude nasledujúci stav buď q1 alebo q2 a na 1 vstupe bude nasledujúci stav q2.
- V treťom riadku, keď je aktuálny stav q2 na vstupe 0, nasledujúci stav bude q1 a na 1 vstupe bude nasledujúci stav q3.
- Vo štvrtom riadku, keď je aktuálny stav q3 na vstupe 0, nasledujúci stav bude q2 a na 1 vstupe bude nasledujúci stav q2.