Teoria d'autòmats
From Wikipedia, the free encyclopedia
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 capaços de resoldre.[1] Alguns d'aquests models tenen un paper central en diverses aplicacions de les ciències de la computació, incloent processament de text, compilador és, disseny de maquinari i intel·ligència artificial. La teoria d'autòmats està estretament relacionada amb la teoria del llenguatge formal, ja que els autòmats són classificats sovint per la classe de llenguatges formals que són capaços de reconèixer.
Un autòmat és un model matemàtic per a una màquina d'estat finita (FSM 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). En la varietat comuna "Mealy" de FSMs, aquesta funció de transició diu a l'autòmat a quin estat canviar donats uns determinats estat i símbol.
L'entrada és llegida símbol per símbol, fins que és "consumida" completament (pensi en aquesta com una cinta amb una paraula escrita en ella, que és llegida per un cap lectora de l'autòmat; el cap es mou al llarg de la cinta, llegint un símbol alhora) una vegada l'entrada s'ha esgotat, l'autòmat s'atura.
Depenent de l'estat en què l'autòmat finalitza es diu que aquest ha acceptat o rebutjat l'entrada. Si aquest acaba en l'estat "accepta", l'autòmat accepta la paraula. Si ho fa en l'estat "rebutja", l'autòmat va rebutjar la paraula, el conjunt de totes les paraules acceptades per l'autòmat constitueixen el llenguatge acceptat pel mateix.