- Des automates finis sont utilisés pour reconnaître des modèles.
- Il prend la chaîne de symboles en entrée et change son état en conséquence. Lorsque le symbole souhaité est trouvé, la transition se produit.
- Au moment de la transition, les automates peuvent soit passer à l’état suivant, soit rester dans le même état.
- Les automates finis ont deux états, Accepter l'état ou État de rejet . Lorsque la chaîne d’entrée est traitée avec succès et que l’automate atteint son état final, il l’acceptera.
Définition formelle de FA
Un automate fini est une collection de 5-tuples (Q, ∑, δ, q0, F), où :
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Modèle d'automates finis :
Les automates finis peuvent être représentés par une bande d'entrée et un contrôle fini.
Bande d'entrée : C'est une bande linéaire comportant un certain nombre de cellules. Chaque symbole d'entrée est placé dans chaque cellule.
Contrôle fini : Le contrôle fini décide de l'état suivant lors de la réception d'une entrée particulière de la bande d'entrée. Le lecteur de bande lit les cellules une par une de gauche à droite et un seul symbole d'entrée est lu à la fois.
Types d'automates :
Il existe deux types d'automates finis :
- DFA (automates finis déterministes)
- NFA (automates finis non déterministes)
1. DFAE
DFA fait référence à des automates finis déterministes. Déterministe fait référence au caractère unique du calcul. Dans DFA, la machine passe à un état uniquement pour un caractère d'entrée particulier. DFA n'accepte pas le déplacement nul.
2. NFA
NFA signifie automates finis non déterministes. Il est utilisé pour transmettre n'importe quel nombre d'états pour une entrée particulière. Il peut accepter le mouvement nul.
Quelques points importants concernant DFA et NFA :
- Chaque DFA est NFA, mais NFA n'est pas DFA.
- Il peut y avoir plusieurs états finaux dans NFA et DFA.
- DFA est utilisé dans l'analyse lexicale du compilateur.
- La NFA est davantage un concept théorique.