La taula de transició és bàsicament una representació tabular de la funció de transició. Pren dos arguments (un estat i un símbol) i retorna un estat (el 'següent estat').
Una taula de transició està representada per les coses següents:
npm esborra la memòria cau
- Les columnes corresponen als símbols d'entrada.
- Les files corresponen als estats.
- Les entrades corresponen al següent estat.
- L'estat inicial es denota amb una fletxa sense font.
- L'estat d'acceptació es denota amb una estrella.
Exemple 1:
Solució:
La taula de transició d'un DFA donat és la següent:
| Estat actual | Següent estat per a l'entrada 0 | Següent estat d'entrada 1 |
|---|---|---|
| →q0 | q1 | q2 |
| q1 | q0 | q2 |
| *q2 | q2 | q2 |
Explicació:
- A la taula anterior, la primera columna indica tots els estats actuals. A les columnes 0 i 1, es mostren els estats següents.
- La primera fila de la taula de transició es pot llegir com, quan l'estat actual és q0, a l'entrada 0 el següent estat serà q1 i a l'entrada 1 el següent estat serà q2.
- A la segona fila, quan l'estat actual és q1, a l'entrada 0, el següent estat serà q0 i a l'entrada 1 el següent estat serà q2.
- A la tercera fila, quan l'estat actual és q2 a l'entrada 0, el següent estat serà q2 i a l'entrada 1 el següent estat serà q2.
- La fletxa marcada amb q0 indica que és un estat inicial i el cercle marcat amb q2 indica que és un estat final.
Exemple 2:
Solució:
La taula de transició d'un NFA donat és la següent:
git pull origin master
| Estat actual | Següent estat per a l'entrada 0 | Següent estat d'entrada 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q1, q2 | q2 |
| q2 | q1 | q3 |
| *q3 | q2 | q2 |
Explicació:
- La primera fila de la taula de transició es pot llegir com, quan l'estat actual és q0, a l'entrada 0 el següent estat serà q0 i a l'entrada 1 el següent estat serà q1.
- A la segona fila, quan l'estat actual és q1, a l'entrada 0 el següent estat serà q1 o q2, i a l'entrada 1 el següent estat serà q2.
- A la tercera fila, quan l'estat actual és q2 a l'entrada 0, el següent estat serà q1 i a l'entrada 1 el següent estat serà q3.
- A la quarta fila, quan l'estat actual és q3 a l'entrada 0, el següent estat serà q2 i a l'entrada 1 el següent estat serà q2.