La tabella di transizione è fondamentalmente una rappresentazione tabellare della funzione di transizione. Richiede due argomenti (uno stato e un simbolo) e restituisce uno stato (lo 'stato successivo').
Una tabella di transizione è rappresentata dalle seguenti cose:
- Le colonne corrispondono ai simboli di input.
- Le righe corrispondono agli stati.
- Le voci corrispondono allo stato successivo.
- Lo stato iniziale è indicato da una freccia senza sorgente.
- Lo stato di accettazione è indicato da una stella.
Esempio 1:
Soluzione:
La tabella di transizione di un dato DFA è la seguente:
exclp
| Stato attuale | Stato successivo per l'ingresso 0 | Stato successivo dell'ingresso 1 |
|---|---|---|
| →q0 | q1 | q2 |
| q1 | q0 | q2 |
| *q2 | q2 | q2 |
Spiegazione:
- Nella tabella sopra, la prima colonna indica tutti gli stati attuali. Sotto le colonne 0 e 1 vengono visualizzati gli stati successivi.
- La prima riga della tabella di transizione può essere letta come, quando lo stato corrente è q0, sull'ingresso 0 lo stato successivo sarà q1 e sull'ingresso 1 lo stato successivo sarà q2.
- Nella seconda riga, quando lo stato corrente è q1, sull'ingresso 0, lo stato successivo sarà q0, e su 1 ingresso lo stato successivo sarà q2.
- Nella terza riga, quando lo stato corrente è q2 sull'input 0, lo stato successivo sarà q2 e su 1 input lo stato successivo sarà q2.
- La freccia contrassegnata con q0 indica che si tratta di uno stato iniziale e il cerchio contrassegnato con q2 indica che è uno stato finale.
Esempio 2:
Soluzione:
La tabella di transizione di un dato NFA è la seguente:
cos'è l'espressione regolare Java
| Stato attuale | Stato successivo per l'ingresso 0 | Stato successivo dell'ingresso 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q1, q2 | q2 |
| q2 | q1 | q3 |
| *q3 | q2 | q2 |
Spiegazione:
- La prima riga della tabella di transizione può essere letta come, quando lo stato corrente è q0, sull'ingresso 0 lo stato successivo sarà q0 e sull'ingresso 1 lo stato successivo sarà q1.
- Nella seconda riga, quando lo stato corrente è q1, sull'ingresso 0 lo stato successivo sarà q1 o q2 e sull'ingresso 1 lo stato successivo sarà q2.
- Nella terza riga, quando lo stato corrente è q2 sull'ingresso 0, lo stato successivo sarà q1 e sull'ingresso 1 lo stato successivo sarà q3.
- Nella quarta riga, quando lo stato corrente è q3 sull'input 0, lo stato successivo sarà q2 e su 1 input lo stato successivo sarà q2.