La table de transition est essentiellement une représentation tabulaire de la fonction de transition. Il prend deux arguments (un état et un symbole) et renvoie un état (l'« état suivant »).
Une table de transition est représentée par les éléments suivants :
- Les colonnes correspondent aux symboles d'entrée.
- Les lignes correspondent aux états.
- Les entrées correspondent à l'état suivant.
- L'état de départ est indiqué par une flèche sans source.
- L'état d'acceptation est indiqué par une étoile.
Exemple 1:
Solution:
Le tableau de transition d'un DFA donné est le suivant :
| État actuel | État suivant pour l'entrée 0 | État suivant de l'entrée 1 |
|---|---|---|
| →q0 | q1 | q2 |
| q1 | q0 | q2 |
| *q2 | q2 | q2 |
Explication:
- Dans le tableau ci-dessus, la première colonne indique tous les états actuels. Sous les colonnes 0 et 1, les états suivants sont affichés.
- La première ligne de la table de transition peut être lue comme, lorsque l'état actuel est q0, à l'entrée 0, l'état suivant sera q1 et à l'entrée 1, l'état suivant sera q2.
- Dans la deuxième ligne, lorsque l'état actuel est q1, sur l'entrée 0, l'état suivant sera q0, et sur 1 entrée, l'état suivant sera q2.
- Dans la troisième ligne, lorsque l'état actuel est q2 sur l'entrée 0, l'état suivant sera q2, et sur 1 entrée, l'état suivant sera q2.
- La flèche marquée en q0 indique qu'il s'agit d'un état de départ et le cercle marqué en q2 indique qu'il s'agit d'un état final.
Exemple 2 :
Solution:
La table de transition d'un NFA donné est la suivante :
| État actuel | État suivant pour l'entrée 0 | État suivant de l'entrée 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q1, q2 | q2 |
| q2 | q1 | q3 |
| *q3 | q2 | q2 |
Explication:
- La première ligne de la table de transition peut être lue comme, lorsque l'état actuel est q0, à l'entrée 0, l'état suivant sera q0 et à l'entrée 1, l'état suivant sera q1.
- Dans la deuxième ligne, lorsque l'état actuel est q1, sur l'entrée 0, l'état suivant sera soit q1 ou q2, et sur 1 entrée, l'état suivant sera q2.
- Dans la troisième ligne, lorsque l'état actuel est q2 sur l'entrée 0, l'état suivant sera q1, et sur 1 entrée, l'état suivant sera q3.
- Dans la quatrième ligne, lorsque l'état actuel est q3 sur l'entrée 0, l'état suivant sera q2, et sur 1 entrée, l'état suivant sera q2.