Index - Documentation

AFN

Préambule

AFN = Automate Fini Non déterministe
( NFA = Non Finite Automaton )

peut avoir plusieurs transitions pour un état et un symbole.
peut avoir des transitions ε (transition sans lire de caractère).

Conversion des ER en AFN

Une analyse lexicale et syntaxique est réalisée sur l'ER, puis depuis l'AST obtenu, on utilise l'algorithme de Thompson pour créer notre NFA :

transition ε
transition symbole
Alternative N₁\|N₂
Concatenation N₁N₂
Répétition N₁*
Option N₁?