Autómates Limités

Un automate limité déterministe, ALD est un modèle mathématique qui réalise des calculs (il exécute une séquence d’instructions, c’est-à-dire, un programme) de manière automatique sur une entrée pour permettre une sortie.
Ce modèle est défini par un alphabet ∑, un ensemble d’états limités, Q= {q0, q1, q2,…}, une fonction de transition, δ, un état initial, q0, et un ensemble d’états finaux, F.
Son fonctionnement se base sur une fonction de transition qui reçoit à partir de l’état initial, une chaine de caractères appartenant à l’alphabet, et qu’elle va lire. A mesure qu’elle lit cette chaine, l’automate se déplace d’un état à un autre, pour finalement s’arrêter à un état final ou d’acceptation, qui représente la sortie.
Le but des automates limités est de reconnaitre des langages simples. Si le mot que j’introduis s’arrête à l’état d’acceptation, celui-ci appartient à ce langage et par conséquent, sera accepté. Dans le cas contraire, il n’appartient pas au langage et n’est donc pas accepté.

Exemple:

Q = ⎨1,2,3⎬

1 est l’état initial

F= {2, 3} sont des états finaux

∑ = ⎨a,b,c⎬ est l’alphabet

Transiciones
δ(1,a) = 3;
δ(1,c) = 2; état d’acceptation
δ(3,a) = 3;
δ(3,b) = 3;
δ(3,c) = 2; état d’acceptation

Cet automate peut être défini par une quintuple, tel que:

A= (Q, ∑, δ, 1, F)

On dit que l´automate est déterministe car pour n´importe quelle valeur d´entrée il existe un seul état auquel l´automate peut se déplacer. Chaque transition en entraine un seul état et avec une même transition on ne peut pas se déplacer à des états différents.