Instituto Tecnológico Superior de Las Choapas

Nombre de la asignatura:
Lenguajes y Autómatas I

Clave de la asignatura:
SCD - 1015

SATCA 1:
2-3-5

Carrera:
Ingeniería en Sistemas Computacionales.

Profesor:
Ing. Miguel Mateos Vasconcelos Reyes

Octubre del 2019

 Unidad III. Autómatas
Finitos

3.1 Conceptos: Definición y Clasificación de Autómata Finito

(AF).
3.2 Conversión de un Autómata Finito No Determinista (AFND)
a Autómata Finito Determinista (AFD).
3.3 Representación de ER usando AFND
3.4 Minimización de estados en un AF
3.5 Aplicaciones (definición de un caso de estudio).
 Introducción

En esta unidad definirá los conceptos básicos y

las notaciones para diseñar un autómata finito,
utilizando un lenguaje regular que acepte el
léxico de un lenguaje de programación.
3.1 Conceptos: Definición y Clasificación de Autómata
Finito (AF).
Empezaremos éste capítulo definiendo un término fundamental
para su estudio. De acuerdo con el diccionario de la Real Academia
Española de la Lengua, entendemos por autómata:

1. Instrumento o aparato que encierra dentro de sí el mecanismo

que le imprime determinados movimientos.
2. Máquina que imita la figura y los movimientos de un ser
animado.
Cuando hablamos de autómatas finitos nos referimos a que el
mecanismo definido como tal termina, de alguna manera, las
acciones que ejecuta. Los autómatas finitos son de utilidad tanto en
el software como en el hardware, y se pueden encontrar en:

• Los circuitos digitales de productos electrónicos.

• Compiladores e intérpretes de lenguajes de programación.
• Protocolos de comunicación.
• Software de análisis de textos, ya sea en web o en programas
de edición.
• Software donde el seguimiento y reconocimiento de patrones es
relevante para continuar un proceso.
Los autómatas finitos consisten en un conjunto de estados
controlados por un proceso que se mueve de uno a otro de ellos,
respondiendo a las entradas que le correspondan. Se dice que son
finitos porque la máquina tiene una cantidad determinada de
estados.

El autómata cuenta con un estado inicial y un estado final, excepto

cuando la máquina tiene un estado de inicio que también es estado
final, lo cual significa que acepta una cadena sin símbolos (vacía),
que representamos con el símbolo λ.
Para diseñar un autómata finito se requieren las siguientes
herramientas, que también se utilizan en la primera fase del
compilador:

• Definiciones regulares
• Diagramas de transiciones
• Matriz de transiciones
Diagramas de transiciones

Una vez que se tienen las definiciones regulares, se procede al

diseño de los autómatas finitos.

Los autómatas finitos tienen una representación gráfica

desarrollada a partir de definiciones regulares, mejorando la
comprensión del lenguaje de programación mediante un grafo
dirigido.

En la figura 3.1 se observan los elementos empleados para

formar un diagrama de transiciones.
Estados
Cada estado está representado por un círculo. Los círculos pueden etiquetarse para mejorar la
referencia del control de flujo.

Estado inicial
Es el estado en donde el autómata inicia los cálculos.

Aristas, arcos o flechas

Representan la transición, o el control de flujo entre un estado (p) y otro (q). Los arcos o flechas
se etiquetan con un símbolo o categoría de símbolos que pueden estar presentes en la cadena
de entrada.
x
p q
Estado final o de aceptación
Representado por un doble círculo; un autómata puede tener varios de ellos.

Figura 3.1 Elementos gráficos del diagrama de transiciones de un autómata finito

Pasos para elaborar un diagrama de transiciones
Paso 1. Definir el patrón que debe seguir la cadena para ser válida.
El nombre de la variable o identificador debe iniciar con una letra, seguida por otra
letra, un dígito o guion bajo, cero o más veces de estos 3 símbolos:

Identificador = Letra (Letra|Dígito | _ )*

En donde | significa “o”.

Paso 2. Definir el alfabeto aceptado por el diagrama de transiciones.

∑ = ( Letra, Dígito, _ )

En este caso, dos de los elementos del alfabeto se agrupan en categorías:

Categoría “Letra”, en donde están todas las letras mayúsculas o minúsculas del
abecedario.
Letra →(a, b, c, d, …, z, A, B, C, D, …, Z)
Categoría “Dígito”, que agrupa todos los dígitos de la notación decimal.

Dígito → (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

El último símbolo del alfabeto es el guion bajo:

Identificador → Letra (Letra|Dígito | _ )*

Paso 3. Realizar el diagrama (vea la figura 3.2).

Letra
Dígito
Letra
q1 q2

Figura 3.2 Diagrama de transiciones para identificadores válidos

Observaciones:

• El primer símbolo que se lee de la cadena debe ser una letra para llegar al
estado q2, que es un estado de aceptación. Esto significa que si la cadena
consta de un solo símbolo, el diagrama acepta esta cadena. Por ejemplo, las
siguientes cadenas (w) son aceptadas: w = G, w = H, w = J.
• Los símbolos que pueden seguir en la cadena son cualquier dígito, cualquier
letra o el guion bajo. La cadena prosigue al estado q2.
• El autómata se detendrá cuando exista un fin de cadena (FDC). Si el estado en
donde se quedó el control del autómata es de aceptación, la cadena de más de
un símbolo se acepta.
• Pero, ¿qué pasa cuando el primer símbolo de la cadena no es una letra? En tal
caso se canalizaría a otro estado, el cuál sería de error debido a que el análisis
que estamos realizando solo es para identificadores válidos. Si la cadena tiene
secuencias de símbolos como 3nombre, _edad, 67mes, el autómata no la
aceptará, porque la expresión regular para nombres de identificadores válidos
no coincide con la que se ha definido.
Concatenación

• Paso 1: ER = L D
• Paso 2: ∑ = {L, D}
• Paso 3: Si presentamos L D significa que podemos recibir una letra seguida de
dígito; en consecuencia, el diagrama de transiciones sería como sigue:

L D DEL
0 1 2 3

Observación: El control comienza en el estado cero, y no se mueve hasta recibir

una letra como entrada. Cuando recibe la entrada adecuada, el control se
traslada al estado 1 y, al recibir un dígito como entrada, se traslada al estado 2.
Cuando recibe el delimitador (esto es, el término de la cadena de entrada), el
control llega al estado final o de aceptación.
Método alternativo
ER1=X→L|D
ER2=CE→(“|’)

L DEL L DEL
0 1 3 0 1 3

D DEL D DEL
2 4 2

DT1 DT2

Observación: La diferencia en estas dos opciones es el manejo del estado final.

Ambas son válidas, pero la DT1 se utiliza cuando los dos elementos de entrada
(letra o dígito) tienen diferentes aplicaciones y, por lo tanto, deben ser tratados de
manera diferente y enviados a diferentes estados de aceptación para poder
detectarlos. En cambio, la DT2 muestra el caso en que lo único que se debe saber
es la categoría en que se encuentran los elementos de entrada; como no es
necesario mantenerlos separados, se les asigna a un solo estado de aceptación.
Unario
Opción 1

Para mejor comprensión de este operador, tomaremos como referencia la definición

regular del identificador:
L→[a-z A-Z]
D→[0-9]
IDEN →L(L|D)*

L
L DEL
0 1 2

D
Observación: En el diagrama de la figura anterior se visualizan los 3 operadores
definidos hasta el momento (concatenación, alternativo y unario). En ésta opción el
operador unario (cero o más casos) incluye al operador alternativo; sin embargo,
puede tener las siguientes variaciones.
Opción 2ɛ

D
X → (LD)*
L D
1 2 3

Observación: La opción 2 muestra como se puede integrar una

concatenación dentro del operador unario.
Opción 3

D
X → D* DEL
0 1

Observación: En la opción 3 se muestra el funcionamiento del operador

unario original.
Sumario

Para la mejor comprensión de este operador se utilizará la definición

regular de una constante numérica básica. En este caso se aceptan uno o
más dígitos.

D
D→[0-9] D DEL
CONE→D+ 0 1 2

Observación: En este operador se utiliza la definición regular de una

constante numérica básica.
Interrogación

D
S→+|- S D DEL
D →[0-9] 0 1 2 3
CNE→S?D+
D

Observación: Este operador se debe utilizar cuando aparece la

especificación “puede”; por ejemplo, se puede aceptar un signo en una
constante numérica. En el diagrama de transiciones es posible observar
que el estado 1 se utiliza solamente cuando aparece un signo.
Potencia
L →[a-z A-Z]
D →[0-9]
IDE→L(L|D)4

L L|D L|D L|D L|D DEL

0 1 2 3 4 25 6

Observación: Este operador se utiliza cuando un elemento de entrada debe

recibirse un determinado número de veces, por ejemplo, si un identificador
debe recibir una letra seguida de 4 caracteres (ya sean letras o dígitos). El
diagrama de transiciones correspondiente presenta una serie de
concatenaciones.
Otro ejemplo del diseño de diagramas de transiciones es una expresión
aritmética con dos operandos, en donde el resultado se asigna a un
identificador. Los operandos pueden ser constantes numéricas o
identificadores válidos. El patrón que define la expresión aritmética es
como sigue:
Id = (cn|id) op-ar (cn|id)

El operador de asignación es =. Con id abreviamos el nombre del

identificador válido:

Id = Letra (Letra|Dígito|_)*

Letra → (a, b, c, d, …, z, A, B, C, D, …, Z). Cn nos sirve para abreviar la

constante numérica, compuesta por dígitos:

Dígito → (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
cn→Dígito*
Abreviemos los operadores aritméticos con op-ar:

op-ar→ (+, -, *, /)

Dígito Dígito

Letra 4 7
Dígito
Dígito op-ar Dígito FDC

Letra
1 2 3 Letra Dígito 6 Letra Dígito 9
=
_
Letra op-ar Letra FDC
5 8
_ _

Figura 3.3 Diagrama de transiciones para una expresión aritmética.

Ejemplo: Si analizamos la cadena Edad = 2013 – año, iniciamos en el
estado 1 y el primer símbolo es “E”. El control pasa entonces al estado 2; el
siguiente símbolo es “d”. El control permanece en el estado 2 hasta que se
lee el símbolo “=“, y entonces cambia al estado 3. En ese momento el
control del AF va hacia el estado 4. Los siguientes símbolos de la cadena
son “0”, “1”, “3”, cada uno de los cuales provoca que el control permanezca
en el estado 4. El control cambia al estado 8 cuando se lee “E”; para los
siguientes símbolos “d”, “a”, “d”, permanece en el estado 8 hasta que se lee
un delimitador o FDC.
Tabla o matriz de transiciones
Es la manera lógica de expresar la información de un diagrama de
transiciones , a través de un arreglo bidimensional de filas y columnas,
donde:

• Cada fila representa un estado del diagrama de transiciones.

• Cada columna corresponde a uno de los símbolos o categorías de
símbolos que componen el alfabeto.
• El valor de la celda corresponde a la fila m y columna n es el número
de estado al que se llegaría en un diagrama de transiciones con el
símbolo x de la cadena y el estado actual.
• En la última columna de la matriz están representados el FDC (fin de
cadena) o el del (delimitador de la cadena), que normalmente
corresponden a un espacio en blanco. Los valores que contienen son
“ACEPTAR” (si el estado donde quedó el control del autómata es doble
círculo o estado de aceptación) o “ERROR” (cuando se llegó al fin de la
cadena leída pero en el diagrama de transiciones no quedó en un
estado de aceptación).
 Matrices de transiciones por operador
Concatenación

L
L DEL
0 1 2

Caracteres de entrada

Estados a b c …z A B C …Z 0 1 2 …9 FDC o del CAT

0 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 La cadena IDE
se acepta identificador
En la figura anterior se muestra la manera en que cada celda de la
matriz toma un valor según la entrada recibida. Al principio el
control se encuentra en el estado 0; al recibir cualquier letra
(independientemente de que sea mayúscula o minúscula) el control
pasa al estado (fila) número 1, en el cuál puede recibir letras o
dígitos con el operador unario. En consecuencia, en todos estos
casos el control se mantiene en el mismo estado. Cuando se recibe
el delimitador (del) o el fin de cadena (FDC), se debe asignar la
clave TOKEN correspondiente al elemento evaluado, mismo que se
encuentra en la columna CAT (conversión a token). Las celdas en
blanco indican que no existe relación entre el símbolo del alfabeto y
algún estado del DT por lo tanto, indican un error.
 Sumario e interrogación S?D+

D
S D DEL
0 1 2 3
D

0 1 2 3 4 5 6 7 8 9 + - del CAT

0 2 2 2 2 2 2 2 2 2 2 1 1

1 2 2 2 2 2 2 2 2 2 2

2 2 2 2 2 2 2 2 2 2 2 La cadena CNE
se acepta Constante
numérica entera
Potencia
En este caso se utiliza el número de filas o estados cuyo número esté indicado por
el operador L(L|C)4:
del
L L|D L|D L|D L|D
0 1 2 3 4 25

L
a b …z A B …Z 0 1 2 …9 del CAT

0 1 1 1 1 1 1

1 2 2 2 2 2 2 2 2 2 2

2 3 3 3 3 3 3 3 3 3 3

3 4 4 4 4 4 4 4 4 4 4

4 5 5 5 5 5 5 5 5 5 5

La cadena IDE
5 se acepta
Otras matrices
Matriz de transiciones de los identificadores válidos de la figura 3.2

Letra Dígito _ del CAT

1 2 Error Error Error

2 2 2 2 Acepta ID válido

Observaciones:

• La cantidad de filas de la matriz corresponde al número de estados del diagrama

de transiciones.
• A cada columna se le asigna un símbolo o categoría de símbolos
correspondiente al alfabeto requerido.
• Al iniciar la lectura de la cadena, el carácter leído es una letra y el estado es 1. El
valor del nuevo estado debe ser 2, de lo contrario, el valor se marca como error.
• Después del primer carácter de la cadena (una letra) puede ser otra letra, un
dígito o un guión bajo. Por lo tanto, la transición permanece en 2 (con esto se
hace referencia al operador unario).
• Al finalizar el recorrido de la cadena, el FDC puede tomar dos valores. En el
estado 1 es error, porque el identificador válido debe iniciar por lo menos con
un símbolo. En el estado 2 el FDC es aceptado, porque la cadena leída recorrió la
matriz sin llegar a un estado de error. Esto significa que la cadena cumplió con el
formato requerido para ser aceptada como un identificador válido.
Matriz de transiciones de la expresión aritmética del diagrama de
transiciones de la figura 3.3

Letra Dígito _ = op-ar del CAT

1 2 Error Error Error Error Error

2 2 2 2 3 Error Error

3 5 4 Error Error Error Error

4 Error 4 Error Error 6 Error

5 5 5 5 Error 6 Error

8 7 Error Error Error Error

6
7 Error 7 Error Error Error 9

8 8 8 8 Error Error 9

9 Error Error Error Error Error Acepta Exp-ar

Clasificación de AF
Los AF (autómatas finitos) se utilizan para el reconocimiento del lenguaje de un
autómata definido. Las cadenas definidas por el AF son analizadas de manera
consecutiva, como una secuencia de símbolos, uno a la vez. Sin embargo, el AF
no tiene forma de recordar cuáles son los símbolos que ha leído.

La validación del símbolo es responsabilidad del control del autómata, y se

determina a partir de los estados que alcanza –un estado, varios estados o
ninguno- antes de continuar con la lectura del siguiente símbolo de la cadena,
siempre y cuando existan otro(s) símbolo(s) o el AF llegue a un estado de
aceptación. La cantidad de estados que se pueden tener en un AF depende de
las diferentes cadenas que sea posible obtener del alfabeto.

El cabezal de lectura es el que lleva el seguimiento de la celda leída: una vez

que se lee el símbolo, el cabezal se mueve a la siguiente posición. En la figura
3.4, los estados se representan secuencialmente en el sentido de las manecillas
del reloj; la cantidad de números que pueden aparecer en la carátula está
determinada por la cantidad de estados del autómata, representados por n.
La ubicación del mecanismo de control entre los distintos estados depende del
símbolo leído, y valida que el carácter siga el flujo en el autómata y continúe así
con la lectura del siguiente símbolo de la cadena, siempre y cuando exista(n)
otro(s) símbolo(s) o el AF llegue a un estado de aceptación.
Cadena del alfabeto dividida en celdas.
La lectura es de izquierda a derecha

Cabezal de lectura
Indicado por una marca
que señala el símbolo
0 Leído de la cadena
n 1

ESTADOS

Mecanismo de control
Figura 3.4 Representación de un AF
Existen dos tipos de autómatas finitos:

1. Deterministas: Tienen solo un camino a seguir dentro del

mecanismo de control para cada símbolo leído del flujo de
entrada.
2. No determinista. Son las máquinas que, al leer un símbolo del
flujo de entrada, tienen más de una opción (o ninguna) para
continuar su camino dentro del control del autómata.
Autómatas finitos deterministas (AFD)

Son autómatas finitos que tienen una y solo una acción por símbolo
leído de la cadena de entrada (o flujo de entrada) bajo análisis.
Cada uno de éstos símbolos pertenece al alfabeto definido, y el
examen de los mismos se realiza en orden y de manera secuencial,
un símbolo a la vez.

El procedimiento de reconocimiento determina la lectura del símbolo

del flujo de entrada y el consecuente cambio de estado (uno entre
una cantidad finita de ellos) o permanecer en el estado actual: no
hay cabida para la ambigüedad, ya que solo se puede tomar un
estado. A este proceso se le llama transición y, como ya se
comentó, el cambio o permanencia del estado dependerá del
estado actual y el símbolo leído, llamado mecanismo de control de
la máquina.
Al final de la cadena, el resultado del análisis puede desembocar en dos
resultados: si se llega a un estado de aceptación, significa que la cadena
cumple las condiciones estipuladas; si se alcanza un estado de error,
significa que no es así.

Los autómatas finitos deterministas están compuestos por cinco elementos:

Q, ∑, &, q0, F.
Elemento Descripción
Q Es un conjunto finito de estados.
∑ Es el alfabeto que acepta la máquina o autómata finito.
& Es la transición que está en algún estado y llegará a otro dependiendo del
siguiente símbolo leído de la cadena:
Qnuevo =Qactual x ∑*

q0 Es el estado inicial, donde comienzan los cálculos; es un elemento del

conjunto de estados Q: q0 ∈ Q
F Es el conjunto de estados de aceptación , que están incluidos en el conjunto
de estados del autómata: F ∈ Q
En el diagrama de transiciones de la figura 3.5 se observa que en casa
estado existe una salida para cada uno de los símbolos del alfabeto.
a

a
q0 q1

b
b
a

q2

Figura 3.5 Diagrama de transiciones de un AFD con ∑ = {a, b}.

Ahora bien, de acuerdo con la tabla siguiente, no todas las cadenas que
recorre el AFD se aceptan:

Cadena (w) Recorrido en el AFD ¿Se acepta?

ɛ Ninguno, ya que el estado inicial es de aceptación Sí
aa q0, q1, q0 Sí
ababababab q0, q1, q2, q1, q2, q1, q2, q1, q2, q2 Sí
bbbbb q0, q2, q2, q2, q2 Sí
baaa q0, q2, q1, q0, q1 No
Los elementos que componen la definición del autómata finito determinista
son:

Q = {q0, q1, q2}

∑ = {a, b}
q0 = 0
F = {q0, q2}
& = función de transición de estados

a B FDC CAT
q1 q1 q2 Acepta Cadena
q0 q0 q2 Error
q1 q1 q2 Acepta Cadena
Tomando en cuenta la información anterior, calculemos las siguientes
transiciones:

1. & (q0, a)
2. & (q1, b)
3. & (q2, a)

Resultado:

4. Estado q1
5. Estado q2
6. Estado q1
Como vemos, cada transición proporciona sólo un estado a seguir. En otras palabras,
para cada par estado-símbolo existe únicamente un valor; en consecuencia, a cada
estado le daremos la notación q seguida del número del estado.

Para que el autómata de los identificadores válidos de la figura 3.2 sea determinista,
en cada estado debe existir una transición para cada símbolo del alfabeto. Si ésta no
coincide con el patrón o lexema definido para ese autómata, se genera un estado de
error. Como se observa en la figura 3.6, se agrega otro estado de “error” a donde
llegan las transiciones de cada símbolo del alfabeto que no cumple con el lexema.

Letra
Dígito

Letra
q1 q2
_ _
Dígito
Dígito
Error

_ Letra

Figura 3.6 AFD para identificadores válidos

En el diagrama de transiciones de la figura 3.3 se observa que en los
diversos estados no están representadas las transiciones que deben ocurrir
para cada símbolo del alfabeto, así que es imposible definir el autómata
finito como determinista. La razón es que no se visualizan adecuadamente
los elementos que describen al autómata, que en este caso son:

Q = {q1, q2, q3, q4, q5, q6, q7, q8, q9}

∑ = {a, b, c, …, z, A, B, C, …, Z, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, _, =, +, -, *, /}
q0 = q1
F = {q9}
& = función de transición de estados, es la matriz de transiciones
correspondiente.
Autómatas finitos no deterministas (AFND)

Con una estructura similar a los AFD, los AFND tienen dos
características particulares. La primera es la ambigüedad, ya que la
transición entre un símbolo leído de la cadena de entrada y el
siguiente existen diferentes caminos a elegir. La segunda
característica es que se omite hacia que estado dirigir el control del
flujo de datos cuando se lee el carácter de entrada.

Así pues, a semejanza de los AFD, los autómatas finitos no

deterministas están compuestos por una quíntupla de elementos (Q,
∑, &, q0, F). La diferencia estriba en la función de transición.
Elemento Descripción
Q Es un conjunto finito de estados.
∑ Es el alfabeto que acepta la máquina o autómata finito.
& Es la función de transición de estados, que puede estar dentro de 3
situaciones.
1. Qnuevo =Qactual x ∑*: el control se ubica dentro del estado actual; luego, al
leer el siguiente símbolo, la transición lo conduce a un nuevo estado.
2. {Qnuevos} = Qactual x ∑*: el control se ubica en el estado actual; luego, al leer
el siguiente símbolo, la transición lo conduce a un conjunto de estados.
3. Qɛ = Qactual x ∑*: el control se ubica en el estado actual; luego, al leer el
siguiente símbolo, la transición no conduce a estado alguno.
Estas dos últimas posibilidades diferencian al AFND del AFD.
q0 Es el estado inicial, donde comienzan los cálculos; es un elemento del
conjunto de estados Q: q0 ∈ Q
F Es el conjunto de estados de aceptación , que están incluidos en el conjunto
de estados del autómata: F ∈ Q
Se tiene el siguiente diagrama de transiciones:
a

a
q0 q1

a
b a

q2

b
Figura 3.7 Diagrama de transiciones de un AFND con ∑ = {a, b}
En la tabla se determina la secuencia del recorrido en AFND para algunas
cadenas:

Cadena Recorrido en el AFND ¿Se

(w) acepta?
ɛ Ninguno, ya que el estado Sí
inicial es de aceptación
aa q0, q1, q0 Sí Se tienen 2 direcciones
para la misma cadena
aa q0, q2, q1 No
bbbbb q0. No existe una ruta No
para b en el estado 0
abbaa q0, q2, q2, q2, q1, q0 Sí Se tienen 2 direcciones
para la misma cadena
abbaa q0, q1. No existe una ruta No
para b en el estado 1
Y los elementos que componen al autómata finito determinista.

Q = {q0, q1, q2}

∑ = {a, b}
q0 = q0
F = {q0, q2}
& = función de transición de estados:

a b FDC
q0 {q1, q2} q2 Acepta
q1 q0 ɛ Error
q2 q1 {q0, q2} Acepta
Con base en la información anterior, calculemos las siguientes transiciones:

1. & (q0, a)
2. & (q1, b)
3. & (q2, a)

Resultado:

4. Conjunto de estados {q1, q2}

5. Omisión de estado
6. Estado q1
3.2 Conversión de un AFND a un AFD
Es posible convertir un AFND a un AFD a través del procedimiento
siguiente:

1. Identificar el autómata.

x x
y x
q0 q1 q2

Figura 3.8 Diagrama de transiciones de un AFND con ∑ = (x, y)

Éste es un AFND, ya que en q1 solo tiene salida para algunos símbolos del alfabeto,
y en q2 no existe ninguna.

2. Definir los elementos que lo componen.

Q = {q0, q1, q2}

∑ = {x, y}
q0 = q0
F = {q2}

3. Aplicar el conjunto potencia al conjunto de estados (S) proporcionado por

todos los subconjuntos del S. La cantidad de subconjuntos está representada
por |P(Q)|=2|Q|.

|Q| = 3
|P(Q)| = 23 = 8
P(Q) = {ɛ, {q0}, {q1}, {q2}, {q0, q1}, {q0, q2}, {q1, q2}, {q0, q1, q2}}
4. Realizar la tabla de transiciones, integrando los elementos
obtenidos de P(Q), incluyendo el conjunto vacío, &(ɛ, ∑) = ɛ.

Es importante observar que en cada estado (filas) existen

transiciones por símbolos (columna). Por ejemplo, para el conjunto
de estados {q0, q1}, teniendo como referencia la fila 5:

Con el símbolo x en el estado q0, llega al estado {q0}

Con el símbolo x en el estado q1, llega a los estados {q1, q2}
Se hace la operación de unión de conjunto para estos estados,
resultando {q0, q1, q2}
Conjunto de estados x y
ɛ ɛ ɛ
{q0} {q0} {q1}
{q1} {q1, q2} ɛ
{q2} ɛ ɛ
{q0, q1} {q0, q1, q2} {q1}
{q0, q2} {q0} {q1}
{q1, q2} {q1, q2} ɛ
{q0, q1, q2} {q0, q1, q2} {q1}
5. Obtener de P (Q) las transiciones correspondientes a cada
símbolo del alfabeto.

&(P(Q), ∑) = UP en q de cada &(q, símbolo)

El proceso se desarrolla por fila de la matriz de transiciones para

cada símbolo.

&({q0}, x) = {q0}
&({q0}, y) = {q1}

&({q1}, x) = {q1, q2}

&({q1}, y) = ɛ
&({q2}, x) = ɛ
&({q2}, y) = ɛ

&({q0, q1}, x) = &({q0}, x) U &({q1}, x) = {q0} U {q1, q2} = {q0, q1, q2}
&({q0, q1}, y) = &({q0}, y) U &({q1}, y) = {q1} U ɛ = {q1}

&({q0, q2}, x) = &({q0}, x) U &({q2}, x) = {q0} U ɛ = {q0}

&({q0, q2}, y) = &({q0}, y) U &({q2}, y) = {q1} U ɛ = {q1}

&({q1, q2}, x) = &({q1}, x) U &({q2}, x) = {q1, q2} U ɛ = {q1, q2}

&({q1, q2}, y) = &({q1}, y) U &({q2}, y) = ɛ U ɛ = ɛ

&({q0, q1, q2}, x) = &({q0}, x) U &({q1}, x) U &({q2}, x) = {q0} U {q1, q2} U ɛ = {q0, q1, q2}
&({q0, q1, q2}, y) = &({q0}, y) U &({q1}, y) U &({q2}, y) = {q1} U ɛ U ɛ = {q1}
6. Realizar una tabla de transiciones con los conjuntos de estados
obtenidos, identificando cuales son los que tienen el estado de
aceptación del AFND y asignando a cada conjunto de estados-
símbolo el nombre Ce (conjunto de estados).
Nombre del Conjunto de
x y
conjunto estados
ɛ ɛ ɛ ɛ
Ce0 {q0} Ce0 Ce1
Ce1 {q1} Ce5 ɛ
Ce2 {q2} ɛ ɛ
Ce3 {q0, q1} Ce6 Ce1
Ce4 {q0, q2} Ce0 Ce1
Ce5 {q1, q2} Ce5 ɛ
Ce6 {q0, q1, q2} Ce6 Ce1

Así, los nombres de las agrupaciones de conjuntos que tienen los estados de
aceptación son los siguientes; Ce2, Ce4, Ce5 y Ce6.
7. Dibujar el diagrama de transiciones resultante del paso 6.

y
Ce3
x
y
x x
x x
y Ce6
x
Ce0 Ce1 Ce5

y y y
x x
x
Ce4 Ce2 ɛ
y
y

Figura 3.9 DT con estados resultantes de estados-símbolo.

8. Eliminar estados a los que no llega ningún símbolo o estados
inaccesibles: Ce2, Ce3, Ce4, Ce6.
x x x

y x
Ce0 Ce1 Ce5

y
y

x
ɛ
y
Figura 3.10 AFD convertido de un AFND

Finalmente, obtenemos el autómata finito determinista, ya que en todos los

elementos del conjunto de estados existe una salida para cada símbolo del
alfabeto.
3.3 Representación de ER usando un AFND
Como ya se vio en el tema de diagramas de transiciones, las
expresiones regulares (E) son una forma mas de expresar las
cadenas (L) que se aceptan, L (E).
Es posible construir un AFND para cualquier L(E). A continuación
se presentan algunas variantes:

E = Ø. No hay una cadena que pueda ser representada ´por la

expresión; por lo tanto, no existe AF que lo pueda representar.
E = ɛ. Las cadenas que acepta esta expresión son las vacías ( es
decir, las que no contienen símbolo alguno), y en el AF el estado
inicial también es el estado de aceptación.
E = {x; x pertenece al alfabeto}. Si cumple con las condiciones de la
expresión, la cadena se acepta.
Para la expresión regular (x|y)* xy, el ∑ = {x, y}

x y
q0 q1 q2
y

Figura 3.11 Diagrama de transiciones para (x|y)* xy.

Las cadenas que acepta el AFND pueden ser: L(AFND) = (ER) = {xy,
xxyyxy, yyyyxy…}

La cadena xy hace el recorrido al estado de aceptación iniciando en q0. A

partir de ahí sigue por la arista con etiqueta x, que corresponde al primer
símbolo de la cadena, llega a q1, se lee el siguiente símbolo (y) el cual
tiene una salida a q2. No hay mas símbolos en la cadena, y el control de
AF está en q2; por lo tanto, la cadena xy se acepta en este AFND y su
expresión.
Para la ER = (a|b|c)ca*, L(ER) = {aca, bcaa, cca, cc} y su diagrama de
transiciones:
a a

b c
q0 q1 q2
c

Figura 3.12 AFND para ER=(a|b|c)ca*

Para ER = Letra(Letra|Dígito)*;

Letra → (a, b, c, d..., z, A, B, C, D, …, Z)

Dígito → (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
L(ER) = {sol23;, E1d2a3d; x;}
Y su AFND:

Letra

Letra ;
q0 q1 q2

Dígito

Figura 3.13 AFND para ER=Letra(Letra|Dígito)*

3.4 Minimización de estados en un AFD
El objetivo de la minimización de estados en AFD es encontrar otro
AFD pero con menor o igual cantidad de estados, capaz de aceptar
el mismo lenguaje que el AFD original. Para lograrlo se realizan los
siguientes pasos: x
y
x y x
q1 q2 q3 q4
x y
y x y
x
y y y
q5 q6 q7 q8

y
x
Figura 3.14 AFD para aplicar la eliminación de estados.
Paso 1. Eliminar los estados que no son accesibles y los arcos que
provienen de ellos. En el caso del AFD que estamos analizando
(vea la figura 3.14), eliminamos el estado 4.

Paso 2. Realizar la partición inicial. Para ello le asignaremos un

número consecutivo a la cantidad de particiones que se obtengan
(Pn; n>=0); por ejemplo, en este caso definiremos Pn como la
partición inicial:
Pn = {{q1, q2, q5, q6, q7}, {q3}}
La partición consiste en agrupar los estados en bloques, donde:
Bloque n = Q-F y bloque n+1 = F
Los bloques son los conjuntos de las particiones. Entonces:
B1 = {q1, q2, q5, q6, q7, q8}
B2 ={q3}
Paso 3. Obtener la partición n+1. Se realiza el DT para obtener la
siguiente partición, en donde agruparemos nuevamente en bloque
los estados que tengan coincidencia en los símbolos con el mismo
número de bloque de la partición anterior, en este caso agregamos
para cada símbolo una columna más, llamada bloque, para
visualizarlo mejor.
Estado x y
Estado Bloque Estado Bloque
q1 q2 B1 q6 B1
q2 q7 B1 q3 B2
B1 q5 q8 B1 q6 B1
Estados del
bloque 1

q6 q3 B2 q7 B1
q7 q7 B1 q5 B1
q8 q7 B1 q3 B2
B2 q3 q1 B1 q3 B2 Estados del
bloque 2
Se observa que en q1 el símbolo de entrada x conduce a q2, lo cual
corresponde al bloque 1; con el símbolo de entrada y se llega al estado 6, que
es el del bloque 1. Así se asigna el valor de la columna bloque para cada
símbolo-estado.

Agrupamos en nuevos conjuntos los estados que tienen el mismo bloque,

independientemente del símbolo del alfabeto. El subconjunto de estados F se
suma a la partición para obtener la partición n+1.

P1 = {{q1, q5, q7}, {q2, q8}, {q6}, {q3}}

Como podemos ver, en la P n+1 los subconjuntos no son iguales a los de P n-1.
Por lo tanto, se tienen 4 subconjuntos, y esto determina la cantidad de bloques.
A continuación, se asignan los elementos a cada bloque:

B1 = {q1, q5, q7}

B2 = {q2, q8}
B3 = {q6}
B4 = {Q3}
 Estado x y
Estado Bloque Estado Bloque
q1 q2 B2 q6 B3
B1 q5 q8 B2 q6 B3
q7 q7 B1 q5 B1
q2 q7 B1 q3 B4
B2
q8 q7 B1 q3 B4
B3 q6 q3 B4 q7 B1
B4 q3 q1 B1 q3 B4

Agrupamos nuevamente los subconjuntos de estados que tienen el mismo

bloque, independientemente del símbolo del alfabeto. El subconjunto de
estados F se suma a la partición para obtener la partición n+1:
P2 = {{q1, q5}, {q7}, {q2, q8}, {q6}, {q3}}
Se obtiene:

P3 = {{q1, q5}, {q7}, {q2, q8}, {q6}, {q3}}

B1 = {q1, q5}
B2 = {q7}
B3 = {q2, q8}
B4 = {q6}
B5 = {q3}

Como P3 = P2, el proceso termina.

Paso 4. Procedemos a la realización del DT, con un AFD

optimizado a partir del AFD de la figura 3.14 y con base en los
bloques de estados. Entonces la transición es bloque n-símbolo.
 x
x
x
y y
B1 B2 B3
x

y
y
y x

x
B4 B5 y

Figura 3.15 Resultado de reducción de estados del AFD de la figura 3.14

3.5 Aplicaciones(definición de un caso de estudio)
1. Definir un AFD para la alarma de una casa, conectada a una
central que da aviso al dueño o al departamento de seguridad para
intervenir cuando se detecta un intruso que ha quebrantado la
seguridad. Existen 2 tipos de sensores: de movimiento y de puerta
y ventana. El estado inicial es la activación.
2. Diseñar un AF para un interruptor eléctrico.
3. Diseñar un AFD y su matriz de transiciones para una máquina
expendedora de refrescos. El valor del producto es de 10 pesos; la
máquina solo acepta monedas y no tiene manera de regresar
cambio por el excedente de dinero depositado ni por la
cancelación del proceso.
4. Elaborar los diagramas y las matrices de transiciones
correspondientes para cada una de las expresiones regulares
definidas para el diseño del lenguaje de programación de estudio.
Bibliografía:

Cantú Treviño, T (2015). Teoría de autómatas, un enfoque práctico (1ra ed.)

Pearson Educación.