Mostra la font per a Autòmat finit

{{Falten referències|data=2022}}
{{Image frame|width=300|content=<imagemap>
File:Automata theory.svg|300px

rect 270 200 680 330 [[Lògica combinacional]]
rect 190 180 710 410 [[Autòmat finit]]
rect 110 160 740 490 [[Autòmat amb pila]]
rect 30 140 770 570 [[Màquina de Turing]]

rect 10 10 790 130 [[Teoria d'autòmats]]

desc top-right
</imagemap>
| caption = Classes d'autòmates {{noprint|{{small|(En fer clic a cada capa, apareix un article sobre aquest tema)}}}}
}}
[[Fitxer:Finite State Machine Logic.svg|miniatura|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 ==
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 [[llenguatge regular|llenguatges regulars]].

=== Transductors ===
Els [[Transductor d'estats finits|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]] <math>(S, \Sigma, T, s, A)</math> on:
* <math>\Sigma</math> és un [[alfabet]] d'entrada (un conjunt finit i no buit de símbols);
* <math>S</math> un conjunt finit i no buit d'estats;
* <math>s \in S</math> és l'estat inicial i element d'<math>S</math>; En un [[Autòmat finit no determinista|Autòmat Finit no Determinsta]], <math>S_0</math> és un conjunt d'estats inicials.
* <math>T</math> és la funció de transició: <math>T: S \times \Sigma \to \mathcal{P}(S)</math>;
* <math>A \subseteq S</math> és un conjunt d'estats d'acceptació o finals, subconjunt d'<math>S</math>.
Formalment, un autòmat finit '''transductor''' pot ser descrit com una 6-[[tupla]] <math>(S, \Sigma, \Gamma, s, \omega)</math> on:
* <math>\Sigma</math> és un [[alfabet]] d'entrada (un conjunt finit no buit de símbols);
* <math>\Gamma</math> és l'alfabet de sortida (un conjunt finit no buit de símbols);
* <math>S</math> un conjunt finit i no buit d'estats;
* <math>s \in S</math> és l'estat inicial i element d'<math>S</math>; En un [[Autòmat finit no determinista|Autòmat Finit no Determinsta]], <math>S_0</math> és un conjunt d'estats inicials.
* <math>T</math> és la funció de transició: <math>T: S \times \Sigma \to \mathcal{P}(S)</math>;
* <math>\omega</math> la funció de sortida.

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

'''Exemple''' (acceptador)

* Σ = {0,1},
* S = {S<sub>1</sub>, S₂},
* T = {(S<sub>1</sub>,0,{S₂});(S<sub>1</sub>,1,{S<sub>1</sub>});(S₂,0,{S<sub>1</sub>});(S₂,1,{S₂})} 
* s = S<sub>1</sub>
* A = {S<sub>1</sub>}.

== 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 ''[[Taula de transició d'estats|Taules de Transicions]]'': la taula de transicions per l'AF de l'exemple és

{| border="0" cellpadding="1" align=center
| || <center>'''0'''</center> || <center>'''1'''</center>
|-
|'''''S''<sub>1</sub>''' || ''S''₂ || ''S''<sub>1</sub>
|-
|'''''S''₂''' || ''S''<sub>1</sub> || ''S''₂
|}

* Els ''[[Diagrama de transicions|Diagrames de transicions]]'': el diagrama de transicions per l'exemple és

[[Fitxer:DFAexample.svg|center|170px|Diagrama de transicions]]

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

<center>
'''<nowiki>Ø υ 1* υ (1* ο 0 ο 1* ο 0)*</nowiki>'''
</center>

== Descripció informal del seu funcionament ==
En el començament del procés de reconeixement d'una cadena d'entrada, l'[[autòmat finit determinista|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'[[autòmat finit determinista|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 <math>q_0</math> 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 [[autòmat finit no determinista|AFND]] amb n ε-moviments on n = nombre d'estats inicials.

== Autòmats finits deterministes ==
Uu '''AFD''' o '''Autòmat Finit [[Sistema determinista|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<sub>1</sub> = 1 S<sub>1</sub> + 0 S₂ + ε
:S₂ = 1 S₂ + 0 S<sub>1</sub>

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 [[trie]]s .

== 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''<sub>1</sub> i δ(''q'',''a'')=''q''₂, sent ''q''<sub>1</sub> ≠ ''q''₂;
* Que existeixin transicions del tipus δ(''q'', [[cadena vacía|ε]]), 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]]

{{Commonscat}}
{{Viccionari-lateral|autòmat finit}}
{{Autoritat}}
{{Llenguatges formals i gramàtiques}}

{{ORDENA:Automat Finit}}
[[Categoria:Computabilitat]]
[[Categoria:Desenvolupament de programari]]
[[Categoria:Lògica]]
[[Categoria:Matemàtica discreta]]
[[Categoria:Llenguatges formals]]