Mots reconnus par un AFD

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.

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :