Automate fini non déterministe généralisé

Un automate fini non déterministe généralisé, en abrégé AFNG, est un automate non déterministe dont les transitions ne portent pas seulement des lettres de l’alphabet, mais peuvent porter une expression régulière.

Définition

Nous aurons besoin d’un AFNG dans l’algorithme de conversion d’un automate fini en expression régulière. Un AFNG est donc un AFN dont les transitions sont définies par des expressions régulières. Voici un exemple d’un tel AFNG :

On voit par exemple que, de l’état q₂, une transition mène à l’état q_f, étiquetée par l’expression régulière a^∗ b. Voici les autres exigences sur un AFNG :

• L’état initial q₀ doit avoir une transition vers tous les autres états. Sur la figure, on voit que de l’état q₀ partent des transitions vers tous les autres états.
• Dans un AFNG, il n’y a qu’un seul état final, et tous les autres états ont une transition vers cet état. Comme on le voit sur la figure, tous les états ont une flèche qui pointe vers q_f.
• L’état initial ne doit pas être le même que l’état final. Un AFNG a donc au moins deux états.
• Tous les autres états, sauf l’état initial et l’état final, doivent avoir des transitions vers tous les autres états, sauf l’état initial et l’état final. Y compris des boucles (transition de l’état q_i vers l’état q_i).

Conversion d’un AFN ordinaire en AFNG

Si nous avons un AFN, la conversion en AFNG est simple.

1. Nous créons un nouvel état initial q_s et une ε-transition vers l’ancien état initial.
2. Nous créons un nouvel état final q_f et, de tous les anciens états finals, nous menons des ε-transitions vers l’état q_f. Les anciens états finals deviennent des états ordinaires.
3. Si quelque part il existe une transition multiple (c’est-à-dire si l’on peut aller de l’état q₁ à l’état q₂ aussi bien par la lettre 0 que par la lettre 1), nous fusionnons ces règles en une seule expression régulière et nous relions toutes les lettres d’origine par l’opérateur de réunion (c’est-à-dire que nous étiquetons la flèche par l’expression régulière 0|1).
4. S’il manque dans l’automate une transition qui devrait s’y trouver d’après la définition, nous la créons et nous l’étiquetons par l’expression régulière ∅. Cela ne change pas le langage que l’automate accepte, car une telle transition n’est jamais empruntée.

Nous pouvons utiliser cet automate pour la conversion d’un automate en expression régulière.