GRAMATICAS Y AUTOMATAS FINITOS

II GRAMATICAS...
2.1 INTRODUCCIÓN A LAS GRAMÁTICA
2.2 ESTRUCTURAS DE LAS GRAMÁTICAS

III AUTOMATAS FINITOS...
2.3 CLASIFICACION DE LAS GRAMATICAS
3.2 AUTOMATAS FINITOS NO DETERMINADOS
3.3 EQUIVALENCIAS ENTRE AUTOMATAS FINITOS
3.4 GENERALIZACIONES DE AUTÓMATAS FINITOS



Videos relacionados...


Descargar archivo en WORD

II GRAMATICAS
2.4 INTRODUCCIÓN A LAS GRAMÁTICA.
Chomsky la define como: " Descripción formalizada de las oraciones de un lenguaje. Una gramática genera o describe un lenguaje."
DEFINICIÓN FORMAL DE GRAMÁTICA
Una gramática es una cuádrupla:
G = (VT, VN, S, P)
donde:
VT= {conjunto finito de símbolos terminales}
VN={conjunto finito de símbolos no terminales}
S es el símbolo inicial y pertenece a VN
P= {conjunto de producciones o de reglas de derivación}
Todas las cadenas del lenguaje definidas por la gramática están formadas con símbolos del vocabulario terminal VT. El vocabulario terminal se define por enumeración de los símbolos terminales.
El vocabulario no terminal VN es el conjunto de símbolos introducidos como elementos auxiliares para la definición de la gramática, y que no figuran en las sentencias del lenguaje.
La intersección entre el vocabulario terminal y no terminal es el conjunto vacío:
{VN} Ç {VT} = {Ø}
La unión entre el vocabulario terminal y no terminal es el vocabulario.
{VN} È {VT} = {V}
En ocasiones es importante distinguir si un determinado vocabulario incluye o no la cadena vacía, indicándose respectivamente con superíndice + o superíndice *, tal como se muestra a continuación:
V+ = V - {l}
V* = V + {l}
El símbolo inicial S es un símbolo no terminal a partir del cual se aplican las reglas de la gramática para obtener las distintas cadenas del lenguaje.
Las producciones P son las reglas que se aplican desde el símbolo inicial para obtener las cadenas del lenguaje. El conjunto de producciones P se define por medio de la enumeración de las distintas producciones, en forma de reglas o por medio de un metalenguaje.
Ej 1: Sea la gramática: G=(VT,VN,S,P) donde VT={a,b}, VN={S} y el conjunto de producciones es:
S ® ab
S ® aSb
Las cadenas de esta gramática están dadas por: ab, aabb, aaabbb, aa…anbb….bn
Ej 2. Sea la gramática: G=({a,b,c,d}, {S,A,B},S,P) donde P son las producciones:
S ® ASB
A ® b
aaA ® aaBB
S ® d
A ® aA
B ® dcd
Las cadenas de esta gramática son: bddcd, abddcd, aabddcd, bbaddcddcddcd……
Ej 3: Sea la gramática: G=(VN, VT,S,P) donde:
VN={, }
VT={0,1,2,3,4,5,6,7,8,9}
S=

Las reglas de producción P son:
::=
::=
::=0| 1| 2| 3| 4| 5| 6| 7| 8| 9

2.5 ESTRUCTURAS DE LAS GRAMÁTICAS.
ESTRUCTURA PROFUNDA Y ESTRUCTURA SUPERFICIAL
ESTRUCTURA PROFUNDA EN LA TEORÍA ESTÁNDAR
En la teoría estándar, la estructura profunda se deriva de las reglas presentes en el subcomponente base del componente sintáctico. Se entiende en este modelo que la estructura profunda es una oración activa, declarativa, positiva y canónica a partir de la cual se realiza la interpretación semántica.
La estructura profunda se relaciona con la Estructura superficial a través del llamado subcomponente transformacional del componente sintáctico. Es el tipo de relación que, por ejemplo, debe esperarse entre una oración activa y su forma pasiva.
Estructura profunda en rección y ligamiento
En Rección y ligamiento, la estructura profunda es rebautizada como Estructura-P, dado que el término “profunda” acarreaba matices ajenos a las ideas de la teoría.
La estructura-P no se deriva de un conjunto de reglas, sino que es resultado de la proyección de determinadas unidades léxicas en el componente computacional. Esta proyección se da a través de la Teoría de la X’ y de la Teoría-θ (o teoría temática).
A diferencia del modelo estándar, rección y ligamiento asigna interpretación semántica sobre la estructura-S (la estructura superficial renombrada), dejando como única función para la Estructura-P el ser la representación sobre la que se realizan los desplazamientos de constituyentes.
________________________________________
GRAMÁTICA FORMAL ESTRUCTURA DE LAS GRAMÁTICAS
REPRESENTACIÓN DE GRAMÁTICAS
Una gramática formal es un objeto o modelo matemático que permite especificar un lenguaje o lengua, es decir, es el conjunto de reglas capaces de generar todas las posibilidades combinatorias de ese lenguaje, ya sea éste un lenguaje formal o un lenguaje natural. Introducción
La expresión «gramática formal» tiene dos sentidos:
*gramática de un lenguaje formal.
*descripción formal de parte de la gramática de un lenguaje natural.
Cuando nos referimos a lenguaje natural estas reglas combinatorias reciben el nombre de sintaxis, y son inconscientes.
Hay distintos tipos de gramáticas formales que generan lenguajes formales (véase la Jerarquía de Chomsky).

Imaginemos una gramática con estas dos reglas:
1. A → bAc 2. A → de
La idea es sustituir el símbolo inicial de la izquierda por otros símbolos aplicando las reglas. El lenguaje al cual representa esta gramática es el conjunto de cadenas de símbolos que pueden ser generados de esta manera: en este caso, por ejemplo:
A → bAc → bbAcc → bbbAccc → bbbdeccc.
El elemento en mayúsculas es el símbolo inicial. Los elementos en minúsculas son símbolos terminales. Las cadenas de la lengua son aquellas que solo contienen elementos terminales, como por ejemplo:
bbbdeccc, de, bdec, … Estas serían tres posibles realizaciones del lenguaje cuya gramática hemos definido con dos reglas.
Para comprender mejor el concepto pondremos algunas reglas de la gramática castellana:
* Una FRASE se puede componer de SUJETO + PREDICADO
O = SN + SV
* Un SUJETO se puede componer de un ARTÍCULO + NOMBRE o SUSTANTIVO (núcleo) + Complementos
SN = Det + N + C
* Un PREDICADO se puede componer de un VERBO conjugado
SV = Aux + GV
* Un ARTICULO puede ser la palabra “el”
*Un NOMBRE o SUBSTANTIVO puede ser “niño”
* etc. [Véase Reglas de rescritura]
Vemos que existen unas definiciones especiales como FRASE, SUJETO, etc. que no aparecen en la frase final formada. Son unas entidades abstractas denominadas Categorías Sintácticas que no son utilizables en una frase.
Las categorías sintácticas definen la estructura del lenguaje representando porciones más o menos grandes de las frases. Existe una jerarquía interna entre las categorías sintácticas.
La categoría superior sería la FRASE que representa una oración válida en lengua castellana.
Por debajo de ella se encuentran sus componentes. Ninguna de estas categorías dan lugar a frases válidas solo la categoría superior.
Al finalizar toda la jerarquía llegamos a las palabras que son las unidades mínimas con significado que puede adoptar una frase.
Aplicando las jerarquías y sustituyendo elementos, llegamos al punto en donde todas las categorías sintácticas se han convertido en palabras, obteniendo por tanto una oración VÁLIDA. (Como por ejemplo: El niño corre). Este proceso se llama producción o generación.
En resumen: Elementos constituyentes
*Una gramática formal es un modelo matemático compuesto por una serie de categorías sintácticas que se combinan entre sí por medio de unas reglas sintácticas que definen cómo se crea una categoría sintáctica por medio de otras o símbolos de la gramática.
*Existe una única categoría superior que denota cadenas completas y válidas.
Mecanismos de especificación
*Por medio de estos elementos constituyentes se define un mecanismo de especificación consistente en repetir el mecanismo de sustitución de una categoría por sus constituyentes en función de las reglas comenzando por la categoría superior y finalizando cuando la oración ya no contiene ninguna categoría.
De esta forma, la gramática puede generar o producir cada una de las cadenas del lenguaje correspondiente y solo estas cadenas. Definición
Una Gramática Formal es una cuádrupla donde:
*N es un alfabeto de símbolos no terminales (variables).
*T es un alfabeto de símbolos terminales (constantes).
*Debe cumplirse que . denotaremos con el alfabeto de la gramática.
*es el símbolo inicial o axioma de la gramática.
*es el conjunto de reglas de producción, de la forma α → β
Es decir, la cadena α debe contener al menos una variable, que puede estar rodeada de un contexto. Derivaciones
Sea G = (N,T,P,S) una gramática, y sean α, β, δ, φ, ρ, … palabras de Σ * . Entonces
*β se deriva de α en un paso de derivación, y lo denotamos con α β si existen dos cadenas , y una producción δ → ρ tales que α = φ1 δ φ2, y β = φ1 ρ φ2

*Notamos con al cierre reflexivo y transitivo de . Es decir α β denota a una secuencia de derivaciones en un número finito de pasos desde α hasta β.

*es una forma sentencial de G, si puede obtenerse la siguiente secuencia de derivaciones . En el caso particular de que se dice que x es una sentencia

*Se denomina lenguaje formal generado por G al conjunto

2.6 CLASIFICACION DE LAS GRAMATICAS
EL CONCEPTO GRAMÁTICA
R= Es un ente formal para especificar de una manera finita el conjunto de cadenas de símbolos que constituyen un lenguaje.
2.-COMO SE ESTRUCTURA UNA GRAMÁTICA?
R= Se compone por:
G= ( VT, VN, S, P ).,
Donde:
VT= Conjunto finito de símbolos terminales.
VN= Conjunto finito de símbolos no terminales.
S= Símbolo inicial y pertenece a vn.
P= Conjunto de producciones o reglas de derivación.

LA APLICACIÓN DE LAS GRAMÁTICAS
R= Las gramaticas se clasifican de acuerdo con su complejidad. esta clasificacion conocida como jerarquia de chomsky se establece aumentando las restricciones sobre la forma de las producciones













ABRAM NOAM CHOMSKING
R= Abraham Noam Chomsky se considera critico y activista, político estadounidense es el fundador de la gramática generativa transformacional, un sistema de análisis de lenguaje que ha revolucionado la lingüística moderna.
Su aportación a la ciencia de la comunicación ha sido muy significativamente. Chomsky fuel el creador de un nuevo modelo lingüístico, la gramática generativa transformacional que expuso por primera vez en su libro estructuras sintácticas. Estableció una diferencia entre el conocimiento innato y con frecuencia inconciente que los individuos tiene de la estructura de su lengua y el modo en que se utilizan diariamente.

CLASIFICACIÓN DE LA GRAMÁTICA SEGÚN CHOMSKING

R= **GRAMATICA DE TIPO CERO O GRAMATICAS NO RESTRINGIDAS: Son las que no tienen restricciones y se pueden derivar por la izquierda y por la derecha.
**GRAMATICA DE TIPO UNO O GRAMATICAS SENSIBLES AL CONTEXTO: Por que se pueden remplazar “a” por gama siempre que estén en el contexto alfa y beta.
**GRAMATICA DE TIPO DOS O GRAMATICAS DE CONTEXTO LIBRE: Admiten tener un solo símbolo no terminal en su parte izquierda, se puede cambiar “a” por alfa, independientemente del contexto en que aparezca “a”.
**GRAMATICA DE TIPO TRES O GRAMATICAS REGULARES: Por un símbolo terminal que puede ser seguido o no por un símbolo no terminal.

CONTEXTO SENSITIVO

R= Son el tipo de gramática mas generales. Una producción u v indica que una ocurrencia de una subcadena u en una cadena puede ser reemplazada con la cadena v. la única restricción en una producción es que el lado izquierdo no sea cadena nula.
Una definición formal de una gramática sin restricciones es la siguiente:
Un cuádruple (VT, VN, P, S) donde v es un conjunto finito de variables, s (el alfabeto) es un conjunto de símbolos terminales (del alfabeto), p es un conjunto de producciones y s es el símbolo inicial de v. una producción de esta clase de gramática tiene la forma uàv, donde u es miembro de (v è s)+ y v es miembro de (v è s)* .

EJEMPLO: La gramática sin restricciones
V= {S, A, C}
S= {A,B,C}
S AABC | L
A AABC | L
CB BC
CC CC







SENSIBLE AL CONTEXTO
R= Estas gramáticas representan un paso intermedio entre las gramáticas de contexto libre y las gramáticas sin restricciones.
Para estas gramáticas no existe restricción alguna en la parte izquierda de la producción, pero la longitud de la parte derecha debe ser al menos la longitud de la parte izquierda.
Una definición formal de una gramática de contexto sensitivo es la siguiente:
Un cuádruple G= (VT, VN, S, P) donde cada producción tiene la forma u à v, donde u es un miembro de (v è s)+, v es miembro de (v è s)+ y longitud (u) >= longitud (v). Un lenguaje generado por una gramática de contexto sensitivo es llamado lenguaje de contexto sensitivo (en gramáticas sin restricciones el lenguaje también es llamado sin restricciones).
Si eliminamos las producciones de cadena vacía de la anterior gramática sin restricciones.
EJEMPLO: Tenemos una gramática de contexto sensitivo.
S AABC | ABC
A AABC | ABC

LIBRE DE CONTEXTO
R= La flexibilidad proporcionada por las gramáticas de contexto libre es tal que es la mas usada para definir la sintaxis de los lenguajes de programación.
Una definición formal de una gramática de contexto sensitivo es la siguiente:
Es un cuádruple G= (VT, VN , P, S) donde v es un conjunto finito de variables, s es un conjunto finito de símbolos terminales, p es un conjunto finito de reglas y s es el símbolo inicial.
Cada producción tiene la forma uàv, donde u es una variable del conjunto v, y v es un miembro de (v è s)* . Esto quiere decir en la parte izquierda de la producción viene siempre una variable (símbolo no terminal) y en la parte derecha pueden venir cualquier número de símbolos terminales y no terminales incluyendo la cadena nula.

Una gramática de contexto libre produce un lenguaje también de contexto libre:
G L(G).

GRAMATICAS REGULARES

R= Estas gramáticas constituyen una importante subclase de las gramáticas de contexto libre. Son también útiles en la definición de lenguajes de programación. Una gramática es regular (gr) si cada regla o producción cumple con las siguientes formas:

1.A A
2.A AB
3.A L

Donde a, b son miembros de v y a es miembro de s. Una gr g genera un lenguaje regular L(G).
EJEMPLO: La siguiente es una GCL ( L U (AB)+A* )


G: S ABSA | L
A AA | L

Una correspondiente gramática regular sería:

S AB | L
B BS | BA
A AA | L



FORMAS EN QUE SE PUEDE REPRESENTAR LA GRAMÁTICA
R= **Escalonada.
** Básica o normal.
**Árbol de derivación.
**Como la escalonada pero utilizando paréntesis angulares [<>].


DESCRICIONES DE NOTACIÓN BNF, BACKUS NAUR FORM

R= Los diagramas de tipo 2 (que incluyen en las gramáticas de tipo 3) tiene métodos matemáticos útiles para desplegar las producciones. Una alternativa que se encuentra con frecuencia es la notación BNF (Forma Backus -Nair).

Se sabe que los lados izquierdos de todas las producciones en una gramática de tipo 2 son símbolos no terminales únicos. Para cada uno de tales símbolos W, se combinan todas las producciones que tienen W como lado izquierdo. El símbolo W permanece a la izquierda y todos los lados derechos asociados con W son enumerados juntos, separándolos por el símbolo |.

El símbolo relacional se reemplaza por el símbolo ::=. Por ultimo, los símbolos no terminales cuando aparezcan serán encerrados entre paréntesis agudos <>. Esto tiene la ventaja adicional de que los símbolos no terminales pueden tener espacios dentro de ellos.

Así muestra que la cadena entre paréntesis debe considerarse como una “palabra” no como dos palabras.

EJEMPLO1: En la notación BNF, las producciones aparecen como sigue:

::=

::=

::=

::=

::=

DIAGRAMAS SINTACTICOS, COMO SE ESTRUCTURA
R= Es también un tipo de notación para especificar la sintaxis de un lenguaje. la diferencia con la notación BNF es que en esta se usan líneas y figuras en lugar de nombres.


DIAGRAMA SINTÁCTICO DE UN
SÍMBOLO NO TERMINAL

SÍMBOLO NO TERMINAL




SÍMBOLO TERMINAL


EJEMPLO: DIAGRAMAS SINTÁCTICOS PARA EXPRESIONES ARITMÉTICAS COMO A + B – 8.






+
-





*


/




-

IDENTIFICADOR
NUMERO

( )



















III AUTOMATAS FINITOS.
3.1 AUTOMATAS FINITOS DETERMINISTICOS


Autómata finito determinista que reconoce el lenguaje regular conformado exclusivamente por las cadenas con un número par de ceros y un número par de unos.


Ejemplo de AFD con dos estados. En nodo de la izquierda es inicial y de aceptación.
Un autómata finito determinista (abreviado AFD) es un autómata finito que además es unsistema determinista; es decir, para cada estado en que se encuentre el autómata, y con cualquier símbolo del alfabeto leído, existe siempre a lo más una transición posible desde ese estado y con ese símbolo.

Definición formal
Formalmente, se define como una 5-tupla (Q, Σ, q0, δ, A) donde:1
 es un conjunto de estados;
 es un alfabeto;
 es el estado inicial;
 es una función de transición;
 es un conjunto de estados finales o de aceptación.
En un AFD no pueden darse ninguno de estos dos casos:
 Que existan dos transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
 Que existan transiciones del tipo δ(q, ε), donde ε es la cadena vacía, salvo que q sea un estado final, sin transiciones hacia otros estados.

3.2 AUTOMATAS FINITOS NO DETERMINADOS


En este ejemplo, δ(q0,b)=q0 y δ(q0,b)=q1. Por lo tanto, se trata de un autómata finito no determinista, que reconoce la expresión regular(a|b)*b+.
Un autómata finito no determinista (abreviado AFND) es un autómata finito que, a diferencia de los autómatas finitos deterministas (AFD), 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.
En un AFND puede darse cualquiera de estos dos casos:
 Que existan transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
 Que existan transiciones del tipo δ(q,ε), 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 transiciónes vacías o transiciones ε (abreviado AFND-ε). Estas transiciones permiten al autómata cambiar de estado sin procesar ningún símbolo de entrada.
Formalmente, si bien un autómata finito determinista se define como un a 5-tupla (Q, Σ, q0, δ, A) donde:1
 es un conjunto de estados;
 es un alfabeto;
 es el estado inicial;
 es una función de transición;
 es un conjunto de estados finales o de aceptación.
en un AFND la función de transición se define como:

Para el caso de los AFND-ε, se suele expresar la función de transición de la forma:

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 automáta puede pasar por varios estados a la vez, generándose una ramificación de las configuraciones existentes en un momento dado. Asimismo, en un autómata finito no determinista podemos aceptar la existencia de más de un nodo inicial.

3.3 EQUIVALENCIAS ENTRE AUTOMATAS 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,8 y viceversa.9Dada una expresión regular, es posible construir un 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, para cualquier autómata finito no determinista siempre existe un autómata finito determinista equivalente, y viceversa.3
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 deterministas ya puede ser 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 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 recursivamente de la siguiente manera:10
 (Base inductiva) Para todo estado q, q ∈ clausura-ε(q).
 (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:
1. Se calcula la clausura-ε del estado inicial, formándose un conjunto A que corresponderá al estado inicial del nuevo autómata.
2. 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.
3. Se repite lo anterior para cada nuevo conjunto, hasta que no existan transiciones posibles para ningún símbolo del alfabeto.
Ejemplo
Eliminación de las transiciones vacías de un AFND-ε.

AFND-ε inicial.

En este caso se obtiene un AFD, que es un caso particular de AFND.
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 AFD, pues la única razón de no-determinismo era justamente la presencia de dichas transiciones.
Conversión de un AFND a un AFD
Conversión de un AFND a un AFD.

AFND inicial.

Proceso de conversión.

AFD final.
Todo AFND (QN, Σ, q0, δN, FN) puede convertirse en un AFD (QD, Σ, q0, δD, FD) equivalente, que mantiene el alfabeto Σ y el estado inicial q0 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:
1. Primero se redefine el conjunto de estados QN = {q0, q1, ..., qm} original, como uno conformado por todos los subconjuntos de QN. Los nuevos estados finales serán todos aquellos estados que contengan a alguno de los estados finales originales.
2. Posteriormente, se redefine el conjunto de transiciones original, por transiciones del tipo δD(S,a), donde a∈Σ, y S es la unión de todos los estados q de QN para los cuales existía la transición δN(q,a).
3. 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 (q0, q1, q2), entonces el AFD intermedio poseerá siete ({q0}, {q1}, {q2}, {q0, q1}, {q0, q2}, {q1, q2}, {q0, q1, q2}), y como el estado final original era q2, entonces los estados finales del AFD intermedio son {q2}, {q0, q2}, {q1, q2} y {q0, q1, q2}. Con respecto a las nuevas transiciones, note por ejemplo que se mantuvo la transición δN(q0,1)=q0, siendo ahora llamada δD({q0},1)={q0}; sin embargo, dado que originalmente se daba que δN(q0,0)=q0 y δN(q0,0)=q1, ahora estas dos transiciones fueron reemplazadas por δD({q0},0)={q0, q1}. Para terminar, note que los estados {q1}, {q2} y {q1, q2} no están conectados con el resto del autómata que posee el estado inicial; por tanto, son eliminados. Asimismo es eliminado también {q0, q1, q2}, pues a pesar de estar conectado con el resto del autómata, no es accesible a partir de {q0}. 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 sólo 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:
1. Eliminar los estados inaccesibles del autómata.
2. Construir una tabla con todos los pares (p, q) de estados restantes.
3. 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.
4. Para cada par (p, q) y cada símbolo a del alfabeto, tal que r = δ(p,a) y s = δ(q,a):
1. Si (r, s) ya ha sido marcado, entonces p y q también son distinguibles, por lo tanto marcar la entrada (p, q).
2. De lo contrario, colocar (p, q) en una lista asociada a la entrada (r, s).
5. 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 polinomial. De hecho, existen algoritmos más eficientes aún que el mostrado en este artículo (aunque menos intuitivos). Sin embargo, el problema de minimizar un autómata finito no determinista es NP-completo y PSPACE-completo.
Ejemplo
Minimización de un AFD.

AFD con estados redundantes.

AFD minimizado.
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
c
e
f
g
a b c e f
b
c
e
f
g
a b c e f
b
c
e
f
g
a b c e f


3.4 Generalizaciones de autómatas finitos
Ejemplo de Máquina de Mealy, un tipo de transductor de estados finitos, que generaliza los autómatas finitos.
Existes diversas generalizaciones posibles de hacer sobre los autómatas finitos, para aumentar su uso y expresividad. Así, por ejemplo, se definen los 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.14 Las máquinas de Moore y máquinas de Mealy son conocidos ejemplos de transductores, que se utilizan sobre todo para modelar sistemas secuenciales.15 16
Es incluso posible aumentar el poder de cómputo de un autómata finito, permitiendo un alfabeto adicional sobre éste, que actúe sobre una memoria de tipo pila para ser considerada en cada transición. Esta es la idea utilizada por los llamados autómatas con pila, los cuales son capaces de reconocer lenguajes libres de contexto, que están un nivel por sobre los lenguajes regulares en la