On considère un automate fini déterministe {(Q,q_{0},F,\delta )} sur un alphabet {\Sigma .}
On peut étendre la fonction de transition {\delta (}définie pour l’instant sur une partie de {Q\times \Sigma )} pour en faire une fonction définie sur une partie de {Q\times \Sigma^{\star}.} Pour cela, on procède par récurrence sur la longueur des mots de {\Sigma :} +
- pour tout état {q,} on pose {\delta (q,\epsilon )=q(}le mot vide ne fait pas changer d’état !)
- soit {q} un état{,a} une lettre et {m} un mot : si {\delta (q,a)=q^{\prime },} on pose {\delta (q,am)=\delta (q^{\prime },m).}
Ainsi {q_{j}=\delta (q_{i},m)} est l’état atteint à partir de {q_{i}} et en suivant les transitions relatives à chaque lettre de {m} On pourra noter {q_{i}-\to^{m}q_{j},} et dire que la transition (étendue) de {q_{i}} à {q_{j}} est étiquetée par le mot {m.}
Si l’une des relatives aux lettres de {m} constitue un blocage, on dira que {\delta (q,m)} constitue un blocage.
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres