Autòmat finit

De Viquipèdia

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 composat 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 varis 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ó.

Taula de continguts 1 Classificació 1.1 Acceptadors i reconeixedors 1.2 Transductors 2 Definició formal 3 Formes de representar un autòmat finit 4 Descripció informal del seu funcionament 5 Autòmats finits deterministes 6 Autòmats finits no deterministes 7 Vegeu també

[edita] Classificació

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

[edita] Acceptadors i reconeixedors

Aquest tipus de maquines 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.

[edita] Transductors

Els Transductors generen sortides basats en les entrades i/o els estats usant accions. Són usats per aplicacions de control. 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.

[edita] Definició formal

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

• Σ és un alfabet d'entrada (un conjut finit i no buit de símbols);
• S un conjunt finit i no buit d'estats;
• és l'estat inicial i element d'S; En un Autòmat Finit no Determinsta, S₀ es un conjunt d'estats inicials.
• T és la funció de transició: ;
• é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,Σ,Γ,s,ω) on:

• Σ és un alfabet d'entrada (un conjut finit no buit de símbols);
• Γ és l'alfabet de sortida (un conjunt finit no buit de símbols);
• S un conjunt finit i no buit d'estats;
• és l'estat inicial i element d'S; En un Autòmat Finit no Determinsta, S₀ es un conjunt d'estats inicials.
• T és la funció de transició: ;
• ω la funció de sortida.

Si la funció de sortida és funció de l'estat i de l'alfabet d'entrada: () la definició corresponent a una Màquina de Mealy. Si la funció de sortida depen només de l'estat: () 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₁}.

[edita] 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 mes 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	S2	S1
S2	S1	S2

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

• 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)*

[edita] Descripció informal del seu funcionament

En l'inici del procés de reconeixement d'una cadena d'entrada, l'AF es troba a l' estat inicial i a mida que processa cada símbol de la cadena va canviant l'estat d'acord amb el que hi ha determinat a la funció de transició. Quan s'ha processat l'últim dels símbols de la cadena d'entrada, l'autòmat s'atura. Si l'estat en el que s'atura és un estat d'acceptació o final, llavors la cadena pertany al llenguatge reconegut per l'autòmat; en cas contrari, la cadena no pertany al llenguatge.

[edita] 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 de un estat d'un mateix símbol a varis 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.

[edita] Autòmats finits no deterministes

Un AFN, AFND o autòmat finit no determinista és aquell que presenta zero, una o més transicions per el mateix caràcter de l'alfabat i es classifiquen en: amb transicions Σ i 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 esta analitzant.

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

[edita] Vegeu també

• Sistema determinista
• Teoria de grafs
• Llenguatge regular