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 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.

Vocabulari

Els conceptes bàsics de símbols , paraules , alfabets i strings són comuns en la majoria de les descripcions dels autòmats. Aquests són:

Símbol: Una dada arbitrària que té algun significat o efecte en la màquina. A aquests símbols també se'ls crida "lletres" o "àtoms".^[2]
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 $\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, al seu torn, ser considerat com el conjunt de totes les possibles concatenacions de cadenes. Formalment, aquest conjunt de totes les cadenes es diu en anglès free monoide. S'indica com $\Sigma ^{*}$ , i el superíndex * es diu l'estrella de Kleene.

Autòmats finits

Formalment, un autòmat finit (AF) pot ser descrit com una 5 - tupla $\langle Q,\Sigma ,\delta ,S_{0},F\rangle$ .

Hi ha tres tipus d'autòmats finits

Autòmat finit determinista (AFE): Cada estat d'un autòmat d'aquest tipus té una transició per cada símbol de l'alfabet.

Autòmat finit no determinista (AFND): Els estats d'un autòmat d'aquest tipus poden, o no, tenir una o més transicions per cada símbol de l'alfabet. L'autòmat accepta una paraula si existeix almenys un camí des de l'estat q ₀ a un estat final F etiquetatge amb la paraula d'entrada. Si una transició no està definida, de manera que l'autòmat no pot saber com continuar llegint l'entrada, la paraula és rebutjada.
Autòmat finit no determinista amb transicions ε (AFND-ε): A més de ser capaç d'assolir més estats llegint un símbol, permet assolir sense llegir cap símbol. Si un estat té transicions etiquetades amb $\epsilon$ , llavors el AFND pot trobar en qualsevol dels estats assolibles per les transicions $\epsilon$ , directament oa través d'altres estats amb transicions $\epsilon$ . El conjunt d'estats que poden assolir mitjançant aquest mètode des d'un estat q, es denomina la clausura $\epsilon$ de q.

No obstant això, es pot observar que tots aquests tipus d'autòmats poden acceptar els mateixos llenguatges . Sempre es pot construir un AFD que accepti el mateix llenguatge que el dau per un AFND.

Extensions als autòmats finits

Els llenguatges acceptats pels autòmats descrits més amunt es denominen llenguatges regulars. Autòmats més potents poden acceptar llenguatges més complexos. Alguns d'aquests autòmats són:

Autòmat amb pila: Són màquines idèntiques als AFD (o AFI), exceptuant el fet que disposen d'una memòria addicional, fent ús d'una pila. La funció de transició $\delta \;$ ara dependrà també dels símbols que es trobin al principi de la pila. Aquesta funció determinarà com canvia la pila en cada transició. Aquest tipus d'autòmats accepten els llenguatges independents del context.
Autòmat linealment acotat: Es tracta d'una màquina de Turing limitada.
Màquina de Turing: Són les màquines computacionals més potents. Posseeixen una memòria infinita en forma de cinta, així com un capçal que pot llegir i canviar aquesta cinta, i moure en qualsevol direcció al llarg de la cinta.

Referències

↑ «Basics of Automata Theory» (en anglès). Stanford Computer Science. [Consulta: 15 octubre 2021].
↑ burch/socs/written/text/v1.pdf page 81 of

Vegeu també

Enllaços externs

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Teoria d'autòmats

[1] «Basics of Automata Theory» (en anglès). Stanford Computer Science. [Consulta: 15 octubre 2021].

[2] urch/socs/written/text/v1.pdf page 81 of

[1]

[2]