Autòmat finit

Un autòmat finit (AF) o màquina d'estats finits (FSM de l'anglès Finite State Machine) és un model matemàtic d'un sistema compost per estats, transicions i accions. Un estat emmagatzema informació del passat. Una transició indica un canvi d'estat i es descriu per la condició que és necessària acomplir per activar la transició. Una acció és una descripció d'una activitat que es realitza en un moment donat. D'accions n'hi ha de diversos tipus:

Acció d'entrada

executa l'acció quan s'entra a l'estat.

Acció de sortida

executa l'acció quan s'abandona l'estat.

Acció d'Input

executa l'acció depenent de l'estat actual i les condicions d'entrada.

Acció de Transició

executa l'acció quan succeeix una certa transició.

Aquest article o secció no cita les fonts o necessita més referències per a la seva verificabilitat.

Classes d'autòmates

(En fer clic a cada capa, apareix un article sobre aquest tema)

Esquema lògic d'un autòmat finit

Història

L'origen dels autòmats finits probablement es remunta al seu ús implícit en màquines electromecàniques, des de principis del segle xx. Ja el 1907, el matemàtic rus Andrei Markov va formalitzar un procés anomenat cadena de Markov, on l'ocurrència de cada esdeveniment depèn amb una certa probabilitat de l'esdeveniment anterior. Aquesta capacitat de "recordar" és utilitzada posteriorment pels autòmats finits.

Posteriorment, el 1943, sorgeix una primera aproximació formal dels autòmats finits amb el model neuronal de McCulloch-Pitts. Durant la dècada dels 50 prolifera seu estudi, sovint anomenat màquines de seqüència, on s'estableixen moltes de les seves propietats bàsiques. Al final d'aquesta dècada, el 1959, sorgeix el concepte d'autòmat finit no determinista en mans dels informàtics teòrics Michael O. Rabin i Dana Scott.

En la dècada dels 60 s'estableix la seva connexió amb les sèries de potències i els sistemes de sobreescriptura. Finalment, amb el desenvolupament del sistema operatiu Unix en la dècada dels 70, els autòmats finits troben el seu nínxol en l'ús massiu d'expressions regulars per a fins pràctics.

Classificació

Hi ha dos grups diferenciats: Acceptadors/Reconeixedors i Transductors.

Acceptadors i reconeixedors

Aquest tipus de màquines donen una sortida binaria, responent si o no si l'entrada s'accepta o no. Alguns dels estats de l'AF es defineixen com finals. Quan tota l'entrada s'ha processat, si l'estat on es troba l'AF és un estat final, l'entrada s'accepta; si no, l'entrada es rebutja. L'entrada d'aquests AF és una cadena constituïda per símbols d'un alfabet i de fet es determina si aquesta cadena pertany al llenguatge que l'autòmat reconeix. Per definició, els llenguatges que poden acceptar els AF són els llenguatges regulars.

Transductors

Els transductors generen sortides basats en les entrades i/o els estats usant accions. Són usats per aplicacions de control. N'hi ha dos tipus:

Màquina de Moore

Aquests AF només usen accions d'entrada, les sortides només depenen de l'estat actual.

Màquina de Mealy

Aquests AF usen accions d'entrada, per tant les sortides depenen de les entrades i de l'estat actual.

Definició formal

Formalment, un autòmat finit acceptador pot ser descrit com una 5-tupla ${\displaystyle (S,\Sigma ,T,s,A)}$ on:

• ${\displaystyle \Sigma }$ és un alfabet d'entrada (un conjunt finit i no buit de símbols);
• ${\displaystyle S}$ un conjunt finit i no buit d'estats;
• ${\displaystyle s\in S}$ és l'estat inicial i element d'${\displaystyle S}$; En un Autòmat Finit no Determinsta, ${\displaystyle S_{0}}$ és un conjunt d'estats inicials.
• ${\displaystyle T}$ és la funció de transició: ${\displaystyle T:S\times \Sigma \to {\mathcal {P}}(S)}$;
• ${\displaystyle A\subseteq S}$ és un conjunt d'estats d'acceptació o finals, subconjunt d'${\displaystyle S}$.

Formalment, un autòmat finit transductor pot ser descrit com una 6-tupla ${\displaystyle (S,\Sigma ,\Gamma ,s,\omega )}$ on:

• ${\displaystyle \Sigma }$ és un alfabet d'entrada (un conjunt finit no buit de símbols);
• ${\displaystyle \Gamma }$ és l'alfabet de sortida (un conjunt finit no buit de símbols);
• ${\displaystyle S}$ un conjunt finit i no buit d'estats;
• ${\displaystyle s\in S}$ és l'estat inicial i element d'${\displaystyle S}$; En un Autòmat Finit no Determinsta, ${\displaystyle S_{0}}$ és un conjunt d'estats inicials.
• ${\displaystyle T}$ és la funció de transició: ${\displaystyle T:S\times \Sigma \to {\mathcal {P}}(S)}$;
• ${\displaystyle \omega }$ la funció de sortida.

Si la funció de sortida és funció de l'estat i de l'alfabet d'entrada: (${\displaystyle \omega :S\times \Sigma \to \Gamma }$) la definició corresponent a una Màquina de Mealy. Si la funció de sortida depèn només de l'estat: (${\displaystyle \omega :S\to \Gamma }$) la definició correspon a una Màquina de Moore

Exemple (acceptador)

• Σ = {0,1},
• S = {S₁, S₂},
• T = {(S₁,0,{S₂});(S₁,1,{S₁});(S₂,0,{S₁});(S₂,1,{S₂})}
• s = S₁
• A = {S₁}.

Formes de representar un autòmat finit

A més d'anotar un AF fent servir la seva descripció formal, és possible representar-lo mitjançant altres anotacions que resulten més còmodes. Les més usuals són:

• Les Taules de Transicions: la taula de transicions per l'AF de l'exemple és

	0	1
S1	S₂	S1
S₂	S1	S₂

• Els Diagrames de transicions: el diagrama de transicions per l'exemple és

Diagrama de transicions

• Les Expressions regulars. Es demostra que donat un autòmat d'estats finits, existeix una expressió regular que el representa.

Ø υ 1* υ (1* ο 0 ο 1* ο 0)*

Descripció informal del seu funcionament

En el començament del procés de reconeixement d'una cadena d'entrada, l'AFD es troba en l'estat inicial. A mesura que processa cada símbol de la cadena va canviant d'estat d'acord amb el que ve determinat per la funció de transició. Quan s'ha processat l'últim dels símbols de la cadena d'entrada, l'AFD s'atura en l'estat final del procés. Si l'estat final en el que s'ha aturat és un estat d'acceptació, llavors la cadena pertany al llenguatge reconegut per l'autòmat, en cas contrari, la cadena no pertany a aquest llenguatge. Recordeu que l'estat inicial ${\displaystyle q_{0}}$ d'un autòmat finit sempre és únic, mentre que els estats finals poden ser més d'un, és a dir, el conjunt F pot contenir més d'un element. També es pot donar el cas que un estat final correspongui al mateix estat inicial. En cas que, per alguna operació sobre l'autòmat, es donés el cas que hi ha més d'un estat inicial, es transformaria en un AFND amb n ε-moviments on n = nombre d'estats inicials.

Autòmats finits deterministes

Uu AFD o Autòmat Finit Determinista és tot autòmat finit on els seus estats d'arribada està unívocament determinat per l'estat inicial i el caràcter llegit per l'autòmat.

És clar que, al contrari de la definició d'Autòmat finit, aquest és un cas particular on no es permeten transicions lamda (buides), el domini de la funció T és S (amb el qual no es permeten transicions des d'un estat d'un mateix símbol a diversos estats).

A partir d'aquest autòmat finit és possible trobar l'expressió regular resolent un sistema d'equacions.

S₁ = 1 S₁ + 0 S₂ + ε

S₂ = 1 S₂ + 0 S₁

Sent ε la paraula nul·la. Resolent el sistema i fent ús de les reduccions apropiades s'obtenen la següent expressió regular: 1*(01*01*)* .

Inversament, donada una expressió regular és possible generar un autòmat que reconegui el llenguatge en qüestió utilitzant l'agorisme de Thompson, desenvolupat per Ken Thompson, un dels principals creadors d'UNIX, juntament amb Dennis Ritchie.

Un tipus interessant d'autòmats finits deterministes són els tries .

Autòmats finits no deterministes

Article principal: Autòmat Finit no Determinista

Un AFN, AFND o autòmat finit no determinista és aquell que pot tenir més d'una transició per una parella de caràcter d'entrada i estat. Es classifiquen en autòmats que tenen transicions Σ i autòmats sense transicions Σ depenent de l'existència o no d'una o més transicions sense que l'autòmat llegeixi el proper caràcter de la cadena que està analitzant.

Tot i que un AFD i un AFND tenen definicions diferents, teòricament es pot mostrar com aquests són equivalents i que, donat un AFND, es pot construir un AFD equivalent i viceversa.

Fent l'analogia amb els AFD, en un AFND pot donar-se qualsevol d'aquests dos casos:

• Que existeixin transicions del tipus (q,a)=q₁ i δ(q,a)=q₂, sent q₁ ≠ q₂;
• Que existeixin transicions del tipus δ(q, ε), sent q un estat no-final, o bé un estat final però amb transicions cap a altres estats.

Quan es compleix el segon cas, es diu que l'autòmat és un autòmat finit no determinista amb transicions buides o transicions ε (abreviat AFND-ε). Aquestes transicions permeten a l'autòmat canviar d'estat sense processar cap símbol d'entrada.

Un autòmat finit no determinista també pot o no tenir més d'un node inicial.

Vegeu també

• Teoria de grafs
• Transductor d'estats finits
• Xarxes de Petri

Viccionari