Ver el código de «Autómata finito»

{{Artículo bueno}}
{{Teoría de autómatas}}
Un '''autómata finito''' ('''AF''') o '''máquina de estado finito''' es un [[modelo computacional]] que realiza [[Proceso (informática)|cómputos]] en forma automática sobre una [[entrada]] para producir una [[salida (informática)|salida]].

Este modelo está conformado por un [[alfabeto]], un conjunto de [[estado (informática)|estados]] finito, una [[Tabla de transición de estados|función de transición]], un estado inicial y un conjunto de estados finales. Su funcionamiento se basa en una función de transición, que recibe a partir de un ''estado inicial'' una [[cadena de caracteres]] pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un ''estado final'' o ''de aceptación'', que representa la salida.

La finalidad de los autómatas finitos es la de reconocer [[lenguaje regular|lenguajes regulares]], que corresponden a los [[lenguaje formal|lenguajes formales]] más simples según la [[Jerarquía de Chomsky]].

== Historia ==

[[Archivo:Mccullochpitts.png|thumb|250px|El [[Neurona de McCulloch-Pitts|modelo neuronal de McCulloch-Pitts]] también utiliza diagramas con estados y transiciones, además de los conceptos de entrada y salida.]]
El origen de los autómatas finitos probablemente se remonta a su uso implícito en [[Servomecanismo|máquinas electromecánicas]], desde principios del {{siglo|XX||s}}.<ref name="wolfram">{{Cita libro |apellido=Wolfram |nombre=Stephen |enlaceautor=Stephen Wolfram |título=A New Kind of Science |url=http://www.wolframscience.com/reference/notes/958a |fechaacceso=31 de marzo de 2010 |idioma=inglés |año=2002 |editorial=Wolfram Media |capítulo=Starting From Randomness |página=958}}</ref> Ya en 1907, el matemático ruso [[Andréi Márkov]] formalizó un proceso llamado [[cadena de Markov]], donde la ocurrencia de cada evento depende con una cierta probabilidad del evento anterior.<ref>{{Cita publicación |apellido=Basharin |nombre=Gely P. | autor2 = Langville, Amy N. | autor3 =  Naumov, Valeriy A.  |título=The Life and Work of A. A. Markov |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.4887 |idioma=inglés |publicación=Linear Algebra and its Applications |fecha=2004 |volumen=386 |páginas=3-26 |fechaacceso=31 de marzo de 2010}}</ref> Esta capacidad de "recordar" es utilizada posteriormente por los autómatas finitos, que poseen una memoria primitiva similar, en que la activación de un estado también depende del estado anterior, así como del símbolo o palabra presente en la función de transición.

Posteriormente, en 1943, surge una primera aproximación formal de los autómatas finitos con el modelo [[Neurona de McCulloch-Pitts|neuronal de McCulloch-Pitts]]. Durante la década de 1950 prolifera su estudio, frecuentemente llamándoseles ''máquinas de secuencia''; se establecen muchas de sus propiedades básicas, incluyendo su interpretación como [[lenguaje regular|lenguajes regulares]] y su equivalencia con las [[expresión regular|expresiones regulares]].<ref name="wolfram" /> Al final de esta década, en 1959, surge el concepto de [[autómata finito no determinista]] en manos de los [[informático teórico|informáticos teóricos]] [[Michael Oser Rabin|Michael O. Rabin]] y [[Dana Scott]].<ref name="AFND" />

En la década de 1960 se establece su conexión con las [[serie de potencias|series de potencias]] y los sistemas de sobreescritura.<ref>{{Cita libro |apellido=Wolfram |nombre=Stephen |enlaceautor=Stephen Wolfram |título=A New Kind of Science |url=http://www.wolframscience.com/reference/notes/958a |fechaacceso=31 de marzo de 2010 |idioma=inglés |año=2002 |editorial=Wolfram Media |página=893}}</ref> Finalmente, con el desarrollo del [[sistema operativo]] [[Unix]] en la década de 1970, los autómatas finitos encuentran su nicho en el uso masivo de expresiones regulares para fines prácticos, específicamente en el diseño de [[analizador léxico|analizadores léxicos]] (comando <code>lex</code>) y la búsqueda y reemplazo de texto (comandos <code>ed</code> y <code>grep</code>).<ref>{{Cita publicación |apellido=Thompson |nombre=Ken |enlaceautor=Ken Thompson |título=Programming Techniques: Regular expression search algorithm |url=http://portal.acm.org/citation.cfm?id=363387&dl=GUIDE, |idioma=inglés |publicación=Communications of the ACM |fecha=1968 |volumen=11 |número=6 |páginas=419-422 |fechaacceso=1 de abril de 2010}}</ref> A partir de ese tiempo, los autómatas finitos también se comienzan a utilizar en [[sistema dinámico|sistemas dinámicos]].<ref name="wolfram" />

== Definición formal ==
Formalmente, un autómata finito es una 5-[[tupla]] (''Q'', Σ, ''q<sub>0</sub>'', δ, ''F'') donde:<ref name="hopcroft">{{Cita publicación |apellido=Chakraborty |nombre=Samarjit |título=Formal Languages and Automata Theory. Regular Expressions and Finite Automata |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.89.9977 |idioma=inglés|publicación=Computer Engineering and Networks Laboratory. Swiss Federal Institute of Technology (ETH) Zürich |fecha=17 de marzo de 2003 |página=17|fechaacceso=30 de marzo de 2010}}</ref>
* <math>Q\,</math> es un conjunto finito de [[estado (informática)|estados]];
* <math>\Sigma\,</math> es un [[alfabeto]] finito;
* <math>q_0\in Q</math> es el estado inicial;
* <math>\delta\colon Q\times\Sigma\to Q</math> es una [[Tabla de transición de estados|función de transición]];
* <math>F \subseteq Q</math> es un conjunto de estados finales o de aceptación.

=== Representación como diagramas de estados ===
[[Archivo:DFAexample.svg|thumb|250px|Este autómata finito está definido sobre el [[alfabeto]] Σ={0,1}, posee dos [[estado (informática)|estados]] ''s''<sub>1</sub> y ''s''<sub>2</sub>, y sus [[Tabla de transición de estados|transiciones]] son δ(''s''<sub>1</sub>,0)=''s''<sub>2</sub>, δ(''s''<sub>1</sub>,1)=''s''<sub>1</sub>, δ(''s''<sub>2</sub>,0)=''s''<sub>1</sub> y δ(''s''<sub>2</sub>,1)=''s''<sub>2</sub>. Su estado inicial es ''s''<sub>1</sub>, que es también su único estado final.]]
Los autómatas finitos se pueden representar mediante [[grafo]]s particulares, también llamados ''diagramas de estados finitos'', de la siguiente manera:

* Los estados ''Q'' se representan como [[vértice (teoría de grafos)|vértices]], etiquetados con su nombre en el interior.
* Una transición ''δ'' desde un estado a otro, dependiente de un símbolo del alfabeto, se representa mediante una [[arista (teoría de grafos)|arista]] [[grafo dirigido|dirigida]] que une a estos vértices, y que está etiquetada con dicho símbolo.
* El estado inicial ''q<sub>0</sub>'' se caracteriza por tener una arista que llega a él, proveniente de ningún otro vértice.
* El o los estados finales ''F'' se representan mediante vértices que están encerrados a su vez por otra circunferencia.

=== Representación como tabla de transiciones ===
{{AP|Tabla de transición de estados}}
Otra manera de describir el funcionamiento de un autómata finito es mediante el uso de '''tablas de transiciones''' o '''matrices de estados'''. Dos posibles tablas para el ejemplo de la imagen anterior podrían ser las siguientes:

{| align="center"
|
{| class="wikitable"
! salida<br />''q'' ∈ Q || símbolo<br />σ ∈ Σ || llegada<br />δ(''q'',σ) ∈ Q
|- align="center"
| ''s''<sub>1</sub> || 0 || ''s''<sub>2</sub>
|- align="center"
| ''s''<sub>1</sub> || 1 || ''s''<sub>1</sub>
|- align="center"
| ''s''<sub>2</sub> || 0 || ''s''<sub>1</sub>
|- align="center"
| ''s''<sub>2</sub> || 1 || ''s''<sub>2</sub>
|}
|
{| class="wikitable"
! || 0 || 1
|- align="right"
| bgcolor=#eee| '''→*''s''<sub>1</sub>''' || ''s''<sub>2</sub> || ''s''<sub>1</sub>
|- align="right"
| bgcolor=#eee| '''''s''<sub>2</sub>''' || ''s''<sub>1</sub> || ''s''<sub>2</sub>
|}<br /><br /><br />
|}
La primera representa explícitamente los parámetros y el valor que toma cada ocurrencia de la función de transición.<ref>{{Cita publicación |apellido=Brena |nombre=Ramón |título=Autómatas y Lenguajes. Un enfoque de diseño |url=http://homepages.mty.itesm.mx/rbrena/AyL.html |publicación=Tecnológico de Monterrey, México |fecha=2003 |página=205 |fechaacceso=31 de marzo de 2010 |fechaarchivo=3 de julio de 2007 |urlarchivo=https://web.archive.org/web/20070703032827/http://homepages.mty.itesm.mx/rbrena/AyL.html |deadurl=yes }}</ref> La segunda es más compacta, y marca con una flecha el estado inicial, y con un asterisco los estados finales.

=== Funcionamiento ===
[[Archivo:Maquina.png|thumb|250px|El esquema general es el de una cinta lectora que avanza sólo hacia delante y de a una celda, según la [[Tabla de transición de estados|función de transición]].]]

En el comienzo del proceso de reconocimiento de una [[cadena de caracteres|cadena]] de [[entrada]], el autómata finito se encuentra en el ''estado inicial'' y a medida que procesa cada símbolo de la cadena va cambiando de estado de acuerdo a lo determinado por la ''función de transición''. Cuando se ha procesado el último de los símbolos de la cadena de entrada, el autómata se detiene en el estado final del proceso. Si el estado final en el que se detuvo es un estado ''de aceptación'', entonces la cadena pertenece al lenguaje reconocido por el autómata; en caso contrario, la cadena no pertenece a dicho lenguaje.

Note que el estado inicial <math>q_0</math> de un autómata finito siempre es único, en tanto que los estados finales pueden ser más de uno, es decir, el conjunto <math>F</math> puede contener más de un elemento. También puede darse el caso de que un estado final corresponda al mismo estado inicial.

=== Generalización de la función de transición ===

Si Σ es un alfabeto, entonces se denota Σ* al conjunto de todas las [[cadena de caracteres|cadenas de caracteres]] o ''palabras'' que se pueden conformar con dicho alfabeto.

Una función de transición δ se puede generalizar a una función δ*, que opera sobre estados y [[cadena de caracteres|secuencias de símbolos]], en lugar de símbolos individuales del alfabeto. Así, esta nueva función de transición se define <math>\delta^*\colon Q\times\Sigma^*\to Q</math>, permitiendo caracterizar los autómatas de manera más abreviada y sin perder expresividad.<ref name="hopcroft" />

La función δ* puede expresarse también de manera [[recursión|recursiva]], definiendo para toda cadena ''x'' ∈ Σ*, todo símbolo ''a'' ∈ Σ, y un estado ''q'' ∈ ''Q'':<ref name="hopcroft" />
* <math>\delta^*(q,\epsilon)=q\,</math>, que es la base inductiva, siendo ε la [[cadena vacía]], y
* <math>\delta^*(q,xa)=\delta(\delta^*(q,x),a)\,</math>, que es la [[inducción matemática|inducción]] propiamente tal.

Se llama '''configuración''' de un autómata finito a un "instante" en el cómputo de la máquina; es decir, al estado actual en que se encuentra dicho cómputo, junto con la palabra que ha sido procesada hasta ese momento. Formalmente, se define como un [[par ordenado]] (''q'', ''x'') ∈ ''Q'' × Σ*. De este modo, se puede definir además la '''configuración inicial''' del autómata, como el par (''q<sub>0</sub>'',''x''), donde ''x'' es la entrada; y la '''configuración final''', como el par (''q'',ε), con ''q'' ∈ ''F''.

De este modo, el [[lenguaje regular]] aceptado por un autómata finito ''A'' puede denotarse como L(''A'') = {w; δ<sup>*</sup>(q<sub>0</sub>,w)∈ F}, es decir, como el conjunto de todas las configuraciones iniciales que conllevan a estados finales.

== Autómata finito determinista ==
[[Archivo:Automata finito.png|thumb|240px|[[Autómata finito determinista|AFD]] que reconoce el [[lenguaje regular]] conformado exclusivamente por las cadenas con un número par de ceros y par de unos.]]
{{AP|Autómata finito determinista}}
Un '''autómata finito determinista''' (abreviado '''AFD''') es un autómata finito que además es un [[sistema determinista]]; es decir, para cada estado ''q'' ∈ ''Q'' en que se encuentre el autómata, y con cualquier símbolo ''a'' ∈ Σ del alfabeto leído, existe siempre a lo más una transición posible δ(''q'',''a'').

En un AFD no pueden darse ninguno de estos dos casos:
* Que existan dos transiciones del tipo δ(''q'',''a'')=''q''<sub>1</sub> y δ(''q'',''a'')=''q''<sub>2</sub>, siendo ''q''<sub>1</sub> ≠ ''q''<sub>2</sub>;
* Que existan transiciones del tipo δ(''q'', [[cadena vacía|ε]]), salvo que ''q'' sea un estado final, sin transiciones hacia otros estados.

Un tipo interesante de autómatas finitos deterministas son los llamados acíclicos y un ejemplo de estos son los [[trie]]s.

== Autómata finito no determinista ==
[[Archivo:Buechie01.PNG|thumb|250px|[[Autómata finito no determinista|AFND]] con transiciones δ(''q''<sub>0</sub>,''b'')=''q''<sub>0</sub> y δ(''q''<sub>0</sub>,''b'')=''q''<sub>1</sub>, que acepta el [[lenguaje regular]] sobre el alfabeto {''a'',''b''} conformado por todas las palabras que terminan en ''b''; es decir, que equivale a la [[expresión regular]] (a<nowiki>|</nowiki>b)*b<sup>+</sup>.]]
[[Archivo:NFA-powerset-construction-example.svg|thumb|180px|[[Autómata finito no determinista|AFND-ε]] a cuyo estado 2 se puede acceder pasando por el estado 3, sin procesar símbolos de entrada.]]
{{AP|Autómata finito no determinista}}
Un '''autómata finito no determinista''' (abreviado '''AFND''') es aquel que, a diferencia de los autómatas finitos deterministas, posee al menos un estado ''q'' ∈ ''Q'', tal que para un símbolo ''a'' ∈ Σ del alfabeto, existe más de una transición δ(''q'',''a'') posible.

Haciendo la analogía con los AFDs, en un AFND puede darse cualquiera de estos dos casos:
* Que existan transiciones del tipo δ(''q'',''a'')=''q''<sub>1</sub> y δ(''q'',''a'')=''q''<sub>2</sub>, siendo ''q''<sub>1</sub> ≠ ''q''<sub>2</sub>;
* Que existan transiciones del tipo δ(''q'', [[cadena vacía|ε]]), siendo ''q'' un estado no-final, o bien un estado final, pero con transiciones hacia otros estados.

Cuando se cumple el segundo caso, se dice que el autómata es un '''autómata finito no determinista con transiciones vacías''' o '''transiciones ε''' (abreviado '''AFND-ε'''). Estas transiciones permiten al autómata cambiar de estado sin procesar ningún símbolo de entrada.

Formalmente, se distingue de la 5-tupla que define a un autómata finito determinista en su [[Tabla de transición de estados|función de transición]]. Mientras en un AFD esta función se define de la siguiente manera:
: <math>\delta:Q\times\Sigma\to Q</math>
en un AFND se define como:
: <math>\delta:Q\times\Sigma\to\mathcal{P}(Q)</math>
Para el caso de los AFND-ε, se suele expresar la función de transición de la forma:
: <math>\delta:Q\times\{\Sigma\cup\epsilon\}\to\mathcal{P}(Q)</math>

donde ''P(Q)'' es el [[conjunto potencia]] de ''Q''.

Esto significa que los autómatas finitos deterministas son un caso particular de los no deterministas, puesto que ''Q'' pertenece al conjunto ''P(Q)''.

La interpretación que se suele hacer en el cómputo de un AFND es que el autómata puede estar en varios estados a la vez, generándose una ramificación de las ''configuraciones'' existentes en un momento dado. Otra interpretación puede ser imaginar que la máquina "adivina" a qué estado debe ir, eligiendo una transición entre varias posibles.

Note finalmente que en un autómata finito no determinista podemos aceptar la existencia de más de un nodo inicial, relajando aún más la definición original.

== Equivalencias entre autómatas finitos ==

Se dice que dos autómatas finitos son '''equivalentes''', si ambos reconocen el mismo [[lenguaje regular]].

Toda [[expresión regular]] (que define a su vez un lenguaje regular) puede ser expresada como un [[autómata finito determinista]],<ref>{{Cita publicación |apellido=Berry |nombre=G. |enlaceautor=Gérard Berry |coautores=[[Ravi Sethi|Sethi, R.]] |título=From regular expressions to deterministic automata |url=http://hal.archives-ouvertes.fr/docs/00/07/59/04/PDF/RR-0649.pdf |idioma=inglés |publicación=TCS: Theoretical Computer Science |fecha=1987 |volumen=48 |páginas=117-126 |fechaacceso=1 de abril de 2010}}</ref> y viceversa.<ref>{{Cita publicación |apellido=Neumann |nombre=Christoph |título=Converting Deterministic Finite Automata to Regular Expressions |url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.2597&rep=rep1&type=pdf |idioma=inglés |fecha=2005 |fechaacceso=1 de abril de 2010}}</ref> Dada una expresión regular, es posible construir un [[autómata finito no determinista|AFND-ε]] que reconozca dicho lenguaje, por ejemplo mediante el [[algoritmo de Thompson]]. Luego, todo AFND-ε puede transformarse en un AFND equivalente, así como todo AFND puede transformarse en un AFD equivalente, mediante el método llamado [[construcción de conjunto potencia]]. Así, por [[transitividad (matemática)|transitividad]], para cualquier autómata finito no determinista siempre existe un autómata finito determinista equivalente, y viceversa.<ref name="AFND">{{Cita publicación |apellido=Rabin |nombre=Michael O. |enlaceautor=Michael Oser Rabin |coautores=[[Dana Scott|Scott, Dana]] |título=Finite automata and their decision problems |url=http://portal.acm.org/citation.cfm?id=1661909 |idioma=inglés |publicación=IBM Journal of Research and Development |editorial=IBM Corp. Riverton, NJ, USA |fecha=1959 |volumen=3 |número=2 |páginas=114-125 |fechaacceso=5 de abril de 2010 |issn=0018-8646}}</ref>

Normalmente en el diseño de autómatas finitos, lo primero que se hace es construir un AFND-ε, que es el más sencillo de construir, por poseer menos restricciones en su función de transiciones. Luego dicho autómata se reduce a un AFND, y finalmente a un AFD, el cual por sus características [[determinismo|deterministas]] ya puede ser [[implementación|implementado]] sin problemas utilizando un [[lenguaje de programación]].

=== Conversión de un AFND-ε a un AFND ===

La conversión de un AFND-ε en un [[Autómata finito no determinista|AFND]] se basa en el concepto de '''clausura-ε''', que corresponde a una [[clausura transitiva]] contextualizada en la [[teoría de autómatas]].

Dado un estado ''q'', se llama '''clausura-ε(''q'')''' al conjunto de todos los estados a los que se puede acceder a partir de ''q'', procesándose a lo más un único símbolo de la entrada. Puede definirse [[recursividad|recursivamente]] de la siguiente manera:<ref>{{Cita publicación |apellido=van Noord |nombre=Gertjan |título=Treatment of epsilon moves in subset construction |url=http://portal.acm.org/citation.cfm?id=971841.971845 |idioma=inglés |publicación=Computational Linguistics |editorial=[[MIT Press]]. Cambridge, MA, USA |fecha=2000 |volumen=26 |número=1 |páginas=61-76 |fechaacceso=5 de abril de 2010 |issn=0891-2017}}</ref>

* ''(Base inductiva)'' Para todo estado ''q'', ''q'' ∈ clausura-ε(''q'').
* ''([[Inducción matemática|Inducción]])'' Dados dos estados ''p'' y ''r'', si ''p'' ∈ clausura-ε(''q'') y ''r'' ∈ δ(''p'',ε), entonces ''r'' ∈ clausura-ε(''q'').

El algoritmo para eliminar las transiciones vacías es el siguiente:
# Se calcula la clausura-ε del estado inicial, formándose un conjunto ''A'' que corresponderá al estado inicial del nuevo autómata.
# Para cada símbolo del alfabeto, se verifican los estados alcanzables a partir de algún estado contenido en ''A'', y se calcula la clausura-ε de dichos estados alcanzables. Si dichas clausuras producen nuevos conjuntos distintos de ''A'', estos serán nuevos estados a los que se accederá a partir de ''A'' y del símbolo correspondiente.
# Se repite lo anterior para cada nuevo conjunto, hasta que no existan transiciones posibles para ningún símbolo del alfabeto.

; Ejemplo
{{Imagen múltiple
 | posición_tabla = right
 | dirección = vertical
 | ancho  = 250
 | título = Eliminación de las transiciones vacías de un [[Autómata finito no determinista|AFND-ε]].| posición_título = left
 | foto1  = Example e-AFND.png
 | texto1 = AFND-ε inicial.| alineación_texto1 = left
 | foto2  = Example AFD.png
 | texto2 = En este caso se obtiene un AFD, que es un caso particular de AFND.| alineación_texto2 = left
}}
En el ejemplo de la figura, se tendrá inicialmente:
:clausura-ε(''1'') = {1,2,3,4,6} = ''A''
:: Para ''A'':
::: Para el símbolo ''a'': 4 va a 5, y clausura-ε(''5'') = {5,7} = ''B''.
::: Para el símbolo ''b'': no existen transiciones posibles.
:: Para ''B'':
::: Para el símbolo ''a'': no existen transiciones posibles.
::: Para el símbolo ''b'': 5 va a 6, y clausura-ε(''6'') = {6} = ''C''.
:: Para ''C'':
::: Para el símbolo ''a'': no existen transiciones posibles.
::: Para el símbolo ''b'': no existen transiciones posibles.
Con esto concluye el algoritmo y se obtiene el autómata de la figura.

En algunos casos puede ocurrir que al quitar las transiciones épsilon obtengamos directamente un [[Autómata finito determinista|AFD]], pues la única razón de no-determinismo era justamente la presencia de dichas transiciones.

=== Conversión de un AFND a un AFD ===
{{AP|Construcción de subconjuntos}}
{{Imagen múltiple
 | posición_tabla = right
 | dirección = vertical
 | ancho  = 250
 | título = Conversión de un [[Autómata finito no determinista|AFND]] a un [[Autómata finito determinista|AFD]].| posición_título = left
 | foto1  = AFND to AFD 1.png
 | texto1 = AFND inicial.| alineación_texto1 = right
 | foto2  = AFND to AFD 2.png
 | texto2 = Proceso de conversión.| alineación_texto2 = right
 | foto3  = AFND to AFD 3.png
 | texto3 = AFD final. | alineación_texto3 = right
}}
Todo [[autómata finito no determinista|AFND]] (''Q''<sub>N</sub>, Σ, ''q<sub>0</sub>'', δ<sub>N</sub>, ''F''<sub>N</sub>) puede convertirse en un [[autómata finito determinista|AFD]] (''Q''<sub>D</sub>, Σ, ''q<sub>0</sub>'', δ<sub>D</sub>, ''F''<sub>D</sub>) equivalente, que mantiene el alfabeto Σ y el estado inicial ''q<sub>0</sub>'' originales. La conversión implica pasar por un AFD intermedio con estados y transiciones redundantes, que al no ser accesibles a partir del estado inicial, son eliminados para obtener el AFD definitivo.

Para definir el AFD intermedio, se deben seguir los siguientes pasos:

# Primero se redefine el conjunto de estados ''Q''<sub>N</sub> = {''q''<sub>0</sub>, ''q''<sub>1</sub>, ..., ''q''<sub>m</sub>} original, como uno conformado por todos los subconjuntos de ''Q''<sub>N</sub>. Los nuevos estados finales serán todos aquellos estados que contengan a alguno de los estados finales originales.
# Posteriormente, se redefine el conjunto de transiciones original, por transiciones del tipo δ<sub>D</sub>(''S'',''a''), donde ''a''∈Σ, y ''S'' es la unión de todos los estados ''q'' de ''Q''<sub>N</sub> para los cuales existía la transición δ<sub>N</sub>(''q'',''a'').
# Por último, se eliminan los '''estados inaccesibles''' o '''inalcanzables''' (junto con sus transiciones de salida), es decir, aquellos a los que no se puede acceder a partir del estado inicial. Luego de esta depuración, se obtiene el AFD final.

; Ejemplo

En las figuras de ejemplo, como el AFND inicial posee tres estados (''q''<sub>0</sub>, ''q''<sub>1</sub>, ''q''<sub>2</sub>), entonces el AFD intermedio poseerá siete ({''q''<sub>0</sub>}, {''q''<sub>1</sub>}, {''q''<sub>2</sub>}, {''q''<sub>0</sub>, ''q''<sub>1</sub>}, {''q''<sub>0</sub>, ''q''<sub>2</sub>}, {''q''<sub>1</sub>, ''q''<sub>2</sub>}, {''q''<sub>0</sub>, ''q''<sub>1</sub>, ''q''<sub>2</sub>}), y como el estado final original era ''q''<sub>2</sub>, entonces los estados finales del AFD intermedio son {''q''<sub>2</sub>}, {''q''<sub>0</sub>, ''q''<sub>2</sub>}, {''q''<sub>1</sub>, ''q''<sub>2</sub>} y {''q''<sub>0</sub>, ''q''<sub>1</sub>, ''q''<sub>2</sub>}. Con respecto a las nuevas transiciones, note por ejemplo que se mantuvo la transición δ<sub>N</sub>(''q''<sub>0</sub>,''1'')=''q''<sub>0</sub>, siendo ahora llamada δ<sub>D</sub>({''q''<sub>0</sub>},''1'')={''q''<sub>0</sub>}; sin embargo, dado que originalmente se daba que δ<sub>N</sub>(''q''<sub>0</sub>,''0'')=''q''<sub>0</sub> y δ<sub>N</sub>(''q''<sub>0</sub>,''0'')=''q''<sub>1</sub>, ahora estas dos transiciones fueron reemplazadas por δ<sub>D</sub>({''q''<sub>0</sub>},''0'')={''q''<sub>0</sub>, ''q''<sub>1</sub>}. Para terminar, note que los estados {''q''<sub>1</sub>}, {''q''<sub>2</sub>} y {''q''<sub>1</sub>, ''q''<sub>2</sub>} no están conectados con el resto del autómata que posee el estado inicial; por tanto, son eliminados. Asimismo es eliminado también {''q''<sub>0</sub>, ''q''<sub>1</sub>, ''q''<sub>2</sub>}, pues a pesar de estar conectado con el resto del autómata, no es accesible a partir de {''q''<sub>0</sub>}. Así finalmente, eliminando estos cuatro estados, así como sus respectivas transiciones, se obtiene el AFD buscado.

=== Minimización de un AFD ===

Dos estados de un autómata finito determinista son '''estados equivalentes''' si al unirse en un solo estado, pueden reconocer el mismo [[lenguaje regular]] que si estuviesen separados. Esta unión de estados implica la unión tanto de sus transiciones de entrada como de salida. Si dos estados no son equivalentes, se dice que son '''estados distinguibles'''. Un estado final con un estado no-final nunca serán equivalentes.

Un AFD está minimizado, si todos sus estados son ''distinguibles'' y ''alcanzables''. Un [[algoritmo]] de minimización de AFD es el siguiente:
# Eliminar los estados inaccesibles del autómata.
# Construir una tabla con todos los pares (''p'', ''q'') de estados restantes.
# Marcar en la tabla aquellas entradas donde un estado es final y el otro es no-final, es decir, aquellos pares de estados que son claramente distinguibles.
# Para cada par (''p'', ''q'') y cada símbolo ''a'' del alfabeto, tal que ''r'' = δ(''p'',''a'') y ''s'' = δ(''q'',''a''):
## Si (''r'', ''s'') ya ha sido marcado, entonces ''p'' y ''q'' también son distinguibles, por lo tanto marcar la entrada (''p'', ''q'').
## De lo contrario, colocar (''p'', ''q'') en una lista asociada a la entrada (''r'', ''s'').
# Agrupar los pares de estados no marcados.

Luego del tercer paso, si la tabla creada queda completamente marcada, entonces el AFD inicial ya era mínimo.

La [[complejidad computacional]] del problema de minimizar un AFD es [[tiempo polinómico|polinomial]]. De hecho, existen algoritmos más eficientes aún que el mostrado en este artículo (aunque menos intuitivos).<ref>{{Cita publicación |apellido=Hopcroft |nombre=John E. |enlaceautor=John Hopcroft |título=An n log n algorithm for minimizing states in a finite automaton |url=http://portal.acm.org/citation.cfm?id=891883 |idioma=inglés |publicación=Theory of Machines and Computations |editorial=Academic Press, Nueva York |fecha=1971 |páginas=189-196 |fechaacceso=9 de abril de 2010}}</ref> Sin embargo, el problema de minimizar un [[autómata finito no determinista]] es [[NP-completo]] y [[PSPACE-completo]].<ref>{{Cita publicación |apellido=Jiang |nombre=Tai |autor2=Ravikumar, B. |título=Minimal NFA problems are hard |url=http://portal.acm.org/citation.cfm?id=165076&dl=GUIDE&coll=GUIDE&CFID=85447364&CFTOKEN=52905360 |idioma=inglés |publicación=SIAM Journal on Computing |editorial=Society for Industrial and Applied Mathematics Philadelphia, PA, Estados Unidos |fecha=1993 |volumen=22 |número=6 |páginas=1117-1141 |fechaacceso=9 de abril de 2010 |issn=0097-5397}}</ref><ref>{{Cita publicación |apellido=Malcher |nombre=Andreas |título=Minimizing finite automata is computationally hard |url=http://www.springerlink.com/content/xj7hde7ewmucw94a/ |idioma=inglés |publicación=Theoretical Computer Science |editorial=Elsevier Science Publishers Ltda. Essex, Reino Unido |fecha=2004 |volumen=327 |número=3 |páginas=375-390 |fechaacceso=5 de abril de 2010 |issn=0304-3975 }}</ref>

; Ejemplo
{{Imagen múltiple
 | posición_tabla = right
 | dirección = vertical
 | ancho  = 250
 | título = Minimización de un [[Autómata finito determinista|AFD]].| posición_título = left
 | foto1  = AFD redundante.png
 | texto1 = AFD con estados redundantes.| alineación_texto1 = left
 | foto2  = AFD minimal.png
 | texto2 = AFD minimizado.| alineación_texto2 = left
}}

En la primera figura del ejemplo, se muestra un autómata con el estado inaccesible ''d'', el cual puede eliminarse inmediatamente. Luego se construye la tabla de pares de estados, y a continuación se marcan, de acuerdo a la tercera línea del algoritmo, las filas y columnas correspondientes a los estados finales ''c'' y ''g'', salvo la celda que representa el par (''c'',''g''), puesto que al ser ambos estados finales, pueden ser estados equivalentes. Posteriormente, se marcan las celdas restantes de acuerdo a la cuarta línea del algoritmo, notando que el par (''b'', ''f'') queda asociado con el par (''c'', ''g''), y así finalmente se obtiene el autómata final, agrupando los estados ''b'' y ''f'', así como ''c'' y ''g'', tal y como se muestra en la segunda figura del ejemplo.

{|
|+ '''Tablas para la búsqueda de estados equivalentes'''
|-
|
{|
| b || style="background:#ddd;"|
|-
| c || style="background:#ddd;"| || style="background:#ddd;"|
|-
| e || style="background:#ddd;"| || style="background:#ddd;"| || style="background:#ddd;"|
|-
| f || style="background:#ddd;"| || style="background:#ddd;"| || style="background:#ddd;"| || style="background:#ddd;"|
|-
| g || style="background:#ddd;"| || style="background:#ddd;"| || style="background:#ddd;"| || style="background:#ddd;"| || style="background:#ddd;"|
|-
|   || a || b || c || e || f
|}
| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
|
{|
| b || style="background:#ddd;"|
|-
| c || style="background:#888;"| || style="background:#888;"|
|-
| e || style="background:#ddd;"| || style="background:#ddd;"| || style="background:#888;"|
|-
| f || style="background:#ddd;"| || style="background:#ddd;"| || style="background:#888;"| || style="background:#ddd;"|
|-
| g || style="background:#888;"| || style="background:#888;"| || style="background:#ddd;"| || style="background:#888;"| || style="background:#888;"|
|-
|   || a || b || c || e || f
|}
| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
|
{|
| b || style="background:#888;"|
|-
| c || style="background:#888;"| || style="background:#888;"|
|-
| e || style="background:#888;"| || style="background:#888;"| || style="background:#888;"|
|-
| f || style="background:#888;"| || style="background:#ddd;"| || style="background:#888;"| || style="background:#888;"|
|-
| g || style="background:#888;"| || style="background:#888;"| || style="background:#ddd;"| || style="background:#888;"| || style="background:#888;"|
|-
|   || a || b || c || e || f
|}
|}

== Generalizaciones de autómatas finitos ==
[[Archivo:Mealymachine jaredwf.png|thumb|200px|Ejemplo de [[Máquina de Mealy]], un tipo de [[transductor de estados finitos]], que generaliza los autómatas finitos.]]
Existen diversas generalizaciones posibles de hacer sobre los autómatas finitos, para aumentar su uso y expresividad. Así, por ejemplo, se definen los [[transductor de estados finitos|transductores de estados finitos]] como autómatas finitos que están dotados además de un [[alfabeto]] de salida, distinto al de entrada, y que pueden poseer más de un estado inicial.<ref>{{Obra citada |título=A general computational model for word-form recognition and production |apellidos=Koskenniemi |nombre=Kimmo |año=1984 |editorial=Association for Computational Linguistics |ubicación=Morristown, NJ, Estados Unidos |páginas=178-181 |url=http://acl.ldc.upenn.edu/P/P84/P84-1038.pdf |fechaacceso=10 de abril de 2010 |urlarchivo=https://web.archive.org/web/20060614094810/http://acl.ldc.upenn.edu/P/P84/P84-1038.pdf |fechaarchivo=14 de junio de 2006 }}</ref> Las [[máquina de Moore|máquinas de Moore]] y [[máquina de Mealy|máquinas de Mealy]] son conocidos ejemplos de transductores, que se utilizan sobre todo para modelar [[sistema secuencial|sistemas secuenciales]].<ref>{{Cita publicación |apellido=Moore |nombre=Edward F. |título=Gedanken-experiments on Sequential Machines |url=http://books.google.cl/books?hl=es&lr=&id=oL57iECEeEwC&oi=fnd&pg=PA129&dq=Gedanken-experiments+on+Sequential+Machines&ots=xtIZlfNSh3&sig=_IZbeMzi9_E7N5vQpocPAfK1KiU#v=onepage&q=Gedanken-experiments%20on%20Sequential%20Machines&f=false |idioma=inglés |publicación=Automata Studies, Annals of Mathematical Studies |editorial=[[Princeton University Press]] |fecha=1956 |ubicación=Princeton, N.J. |número=34 |páginas=129-153 |fechaacceso=10 de abril de 2010}}</ref><ref>{{Cita publicación |apellido=Mealy |nombre=George H. |título=A Method for Synthesizing Sequential Circuits |idioma=inglés |publicación=Bell Systems Technical Journal |fecha=1955 |volumen=34 |páginas=1045-1079 |fechaacceso=10 de abril de 2010}}</ref>

Es incluso posible aumentar el poder de [[computabilidad|cómputo]] de un autómata finito, permitiendo un alfabeto adicional sobre éste, que actúe sobre una memoria de tipo [[Pila (informática)|pila]] para ser considerada en cada transición. Esta es la idea utilizada por los llamados [[autómata con pila|autómatas con pila]], los cuales son capaces de reconocer [[gramática libre de contexto|lenguajes libres de contexto]], que están un nivel por sobre los [[lenguaje regular|lenguajes regulares]] en la [[Jerarquía de Chomsky]].<ref>{{Obra citada |título=Formal languages and their relation to automata |apellidos=Hopcroft |nombre=John E. |enlaceautor=John E. Hopcroft |apellidos2=Ullman |nombre2=Jeffrey D. |enlaceautor2=Jeffrey D. Ullman |año=1969 |editorial=Addison-Wesley Longman Publishing Co., Inc. |ubicación=Boston, MA, Estados Unidos |página=262 |url=http://portal.acm.org/citation.cfm?id=1096945 |fechaacceso=10 de abril de 2010}}</ref>

== Véase también ==
* [[Lenguaje regular]]
* [[Teoría de autómatas]]
* [[Sistema combinacional]]
* [[Autómata con pila]]
* [[Máquina de Turing]]
* [[Máquina abstracta]]

== Referencias ==
{{listaref|2}}

== Bibliografía ==
* {{Cita libro |apellido=Hopcroft |nombre=John |apellido2=Motwani |nombre2=Rajeev |apellido3=Ullman |nombre3=Jeffrey D. |enlaceautor=John Hopcroft |título=Introduction to Automata Theory, Languages, and Computation |url=https://archive.org/details/trent_0116404725818 |fechaacceso=30 de marzo de 2010 |idioma=inglés |año=2001 |editorial=[[Addison-Wesley]] |ubicación=Massachusetts, Estados Unidos}}

{{Control de autoridades}}
[[Categoría:Lenguajes formales]]