Teoria d'Autòmats

La teoria d'autòmats és una branca de les ciències de la computació que estudia les màquines abstractes i els problemes que aquestes són capaces de resoldre. La teoria d'autòmats està íntimament relacionada amb la teoria del llenguatge formal, ja que els autòmats es classifiquen sovint per les classes de llenguatges formals que són capaces de reconèixer.

Un autòmat és un model matemàtic per una màquina d'estats finits (FSM en les seves sigles en anglès). Una FSM és una màquina que, donada una entrada de símbols, "salta" a través d'una sèrie d'estats d'acord amb una funció de transició (que pot ser expressada com una taula). Si la màquina d'estats és del tipus anomenat "Mealy", aquesta funció de transició depèn de l'estat en què es troba la màquina i dels símbols d'entrada.

L'entrada és llegida símbol a símbol, fins que és "consumida" completament (es pot pensar com una cinta amb una sèrie de símbols escrits, que es va llegint per un capçal lector; el capçal es mou al llarg de la cita, llegint un símbol a cada pas) un cop la cinta s'esgota, l'autòmat es deté.

Depenent de l'estat en el que l'autòmat finalitza es diu que aquest ha acceptat o rebutjat l'entrada. Si la FSM acaba en un estat "acceptar", l'autòmat ha acceptat la paraula; i ho fa en un estat "rebutjar", l'autòmat ha rebutjat l'entrada. El conjunt de totes les paraules acceptades per l'autòmat formen el llenguatge acceptat per l'autòmat.

Els conceptes bàsics de símbol, paraula, alfabet i string són comuns a la majoria de les descripcions dels autòmats, i són:

Símbol

Una data arbitrària que té algun significat per a la màquina. A aquests símbols també se'ls anomena "lletres" o "àtoms".^[1]

Paraula

Una cadena finita formada per la concatenació d'un nombre de símbols.

Alfabet

Conjunt finit de símbols. Un alfabet s'indica normalment amb ${\displaystyle \Sigma }$, que és el conjunt de lletres en un alfabet.

llenguatge

Un conjunt de paraules, format per símbols en un alfabet donat. Pot ser infinit.

Clausura de Kleene

Un llenguatge es pot considerar com un subconjunt de totes les possibles paraules. El conjunt de totes les paraules pot, alhora, ser considerat com el conjunt de totes les possibles concatenacions de cadenes. Formalment, aquest conjunt de totes les cadenes s'anomena en angles free monoid.

S'indica como ${\displaystyle \Sigma ^{*}}$, i el superíndex * s'anomena l'estrella de Kleene.