Autòmat finit

De Viquipèdia
Dreceres ràpides: navegació, cerca
Esquema lògic d'un 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ó.

Història[modifica | modifica el codi]

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 formalitzar un procés anomenat cadena de Markov, on la 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ó[modifica | modifica el codi]

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

Acceptadors i reconeixedors[modifica | modifica el codi]

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[modifica | modifica el codi]

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[modifica | modifica el codi]

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

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

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

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

Si la funció de sortida és funció de l'estat i de l'alfabet d'entrada: (\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: (\omega: S \to \Gamma) la definició correspon a una Màquina de Moore

Exemple (acceptador)

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

Formes de representar un autòmat finit[modifica | modifica el codi]

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:

0
1
S1 S2 S1
S2 S1 S2
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[modifica | modifica el codi]

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 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[modifica | modifica el codi]

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.

S1 = 1 S1 + 0 S2 + ε
S2 = 1 S2 + 0 S1

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[modifica | modifica el codi]

Un AFN, AFND o autòmat finit no determinista és aquell que pot tenir més d'una transicions 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)=q1 i δ(q,a)=q2, sent q1q2;
  • 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é[modifica | modifica el codi]


A Wikimedia Commons hi ha contingut multimèdia relatiu a: Autòmat finit Modifica l'enllaç a Wikidata