Nombre: Juan Miguel Hernández Mora

C.I: 27.229.408

1- ¿Cuál es el proceso de conversión de un Autómata Finito No Determinista (AFN)

a un Autómata Finito Determinista (AFD)? Enfoque su respuesta en la
construcción de estados y transiciones en el AFD a partir del AFN. ¿Cómo
garantiza este proceso que el AFD reconozca el mismo lenguaje que el AFN
original? Proporcione un ejemplo y discuta posibles casos problemáticos.(5pts)

El proceso consiste en identificar todos los estados alcanzables del AFN. Luego se debe crear nuevos
estados en el AFD que representen combinaciones de estados del AFN. Estos nuevos estados
respresentarán el conjunto de estados del AFN que comparten transiciones similares, después se debe
determinar las transiciones del AFD basadas en las transiciones del AFN, asegunrándose de que cada
estado en el AFD tenga transcisiones definidas para cada simbolo del alfabeto. Finalmente se debe
marcar un estado de aceptación en el AFD si contiene al menos un estado de aceptación del AFN. La
construcción de los subconjuntos se inicia a partir de un AFN N = {Qn, Σ, δn, q0, Fn} con el objetivo
de describir un AFD D = (Qd, Σ, δd, {qo}, Fd) tal que ambos acepten la misma clase de lenguaje, L(N)
= L(D), se puede detallar que en ambos autómatas se tiene el mismo lenguaje y el estado inicial (en
forma de conjunto para el determinista), los demás componentes se construyen con lo siguiente:

 Qd = Qn* (conjunto potencia) considerando solamente los estados accesibles a partir del
estado inicialde Qd (osea desde q0)
 Fd es el conjunto de subconjuntos de S de Qn tal que S ∩ Fn ≠ vacio. Es decir Fd está formado
por todos los conjuntos de los estados de N que incluyen al menos un estado de aceptación de
N.
 Para cada conjunto de S perteneciente a Qn y para cada símbolo de entrada a perteneciente a Σ,

es decir, para calcular δd (S, a) nos fijamos en todos los estados de p de S, vemos qué estados de
N pasan a p con la entrada a, y calculamos la únion de todos estos estados.

Este proceso garantiza que el AFD reconozca el mismo lenguaje que el AFN original debido a la forma
en que se construyen los estados y las transiciones. Al identificar todos los estados alcanzables del AFN
y crear nuevos estados en el AFD que representen combinaciones de estados del AFN, se asegura que el
AFD contenga la misma información que el AFN.

Ejemplo: Calcular un AFD que reconozca el mismo lenguaje que el siguiente AFN (figura 1)
 figura 1 | Un AFD

el cual tiene la siguiente tabla de transición

f 0 1
q0 {q0, q1} {q0}
q1 {q2} {q0,q2}
q2 Vacio vacio

Comenzamos a partir de la imagen de {q0} con cada uno de los símbolos del alfabeto. La imagen {q0}
con el símbolo 0 es el conjunto de estados {q0, q1}(f(q0, 0) = {q0, q1}) y su imagen con el símbolo 1
es el conjunto de estados {q0}. Como el conjunto {q0, q1} no tiene asociada ninguna fila en la tabla, se
etiqueta una fila con él.

f 0 1
{q0} {q0, q1} {q0}
{q0, q1}

Para calcular la imagen de {q0, q1} con el simbolo 0, se debe calcular f(q0, 0) U f(q1, 0). Si se consulta
en la tabla de trasición de AFN o en el grafo (figura 1) se obtiene que es {q0, q1} U {q2} = {q0, q1,
q2}. Este resultado se escribe en la tabla en la entrada [{q0, q1}, 0].

f 0 1
{q0} {q0, q1} {q0}
{q0, q1} {q0,q1,q2}

De forma similar se calcula la imagen de {q0, q1} con el simbolo 1: f(q0, 1) U f(q1, 1) = {q0} U {q0,
q2} = {q0, q2}

f 0 1
{q0} {q0, q1} {q0}
{q0, q1} {q0,q1,q2} {q0, q2}
Una vez completada la fila etiquetada como {q0, q1} se observa que aparecen dos conjuntos de estados
nuevos, por lo tanto, se procede a crear dos nuevas filas en la tabla, cada una etiquetada con cada uno
de los nuevos conjuntos:

f 0 1
{q0} {q0, q1} {q0}
{q0, q1} {q0,q1,q2} {q0, q2}
{q0, q1,q2}
{q0, q2}

ahora la fila {q0, q1, q2}

f({q0, q1, q2}, 0) = f(q0, 0) U f(q1, 0) U f(q2, 0) = {q0, q1} U {q2} U vacio = {q0,q1,q2}
f({q0, q1, q2}, 1) = f(q0, 1) U f(q1, 1) U f(q2, 1) = {q0} U {q¿, q2} U vacio = {q0, q2}

f 0 1
{q0} {q0, q1} {q0}
{q0, q1} {q0,q1,q2} {q0, q2}
{q0, q1,q2} {q0, q1, q2} {q0, q2}
{q0, q2}
Al no aparecer ningún nuevo conjunto de estados, pasamos a completar la fila con etiqueta {q0, q2}

f({q0, q2}, 0) = f(q0, 0) U f(q2, 0) = {q0, q1} U vacio = {q0, q1}

f({q0, q2}, 1) = f(q0, 1) U f(q2, 0) = {q0} U vacio = {q0}

f 0 1
{q0} {q0, q1} {q0}
{q0, q1} {q0,q1,q2} {q0, q2}
{q0, q1,q2} {q0, q1, q2} {q0, q2}
{q0, q2} {q0, q1} {q0}

Al no aparecer otros nuevos conjuntos, damos por terminado la equivalencia del AFN a AFD.
Al final renombramos los conjuntos, {q0} como q0’, el {q0,
q1} como q1’, el {q0, q1, q2} como q2’ y {q0, q2} como q3’,
como los conjuntos {q0, q1, q2} y {q0, q2}contienen estados
finales del AFN original, entonces los estados q2’ y q3’ serán
estados finales en el AFD.

¿Qué es la función de transición extendida en un

autómata? Describa su definición formal y
explique cómo se utiliza para analizar el
comportamiento de un autómata. Proporcione ejemplos que ilustran su uso.(3pts)

La función de transición extendida es una extensión de la función de transición que permite al autómata
realizar transiciones basadas en cadenas de entradas más largas. En lugar de realizar una transición a la
vez, esta permite al autómata procesar y consumir múltiples símbolos de entrada al mismo tiempo.
Definimos como sigue:

base: δ’(q, ε ) = {q}. Es decir, si no leemos, ningún símbolo de entrada, estaremos en el estado en el
que hayamos comenzado

paso inductivo: Supongamos que w tiene la forma w = xa, donde a es el símbolo final de w y x es el
resto de w. Supongamos que tambien δ’(q, x) = {p1, p2, …, pk}. Sea

Entonces δ’(q, w) = {r1, r2, … ,rm} menos formalmente, para calcular δ’ (q, w) obtenemos primero
δ’(q, x), y después seguimos todas las transiciones de estos estados que estén etiquetadas con a.

¿Cuál es el método de la silla en la teoría de los autómatas? Describa su proceso

paso a paso y discuta sus ventajas y desventajas, así como casos en los que podría
no ser adecuado.(3pts)
El método de la silla en la teoría de los autómatas se refiere a un enfoque para analizar y diseñar
autómatas finitos. Este método utiliza un enfoque de tabla o matriz para representar el comportamiento
del autómata en diferentes estados y con diferentes entradas. Al utilizar el método de la silla, es posible
determinar la equivalencia entre diferentes autómatas finitos, simplificar autómatas existentes y diseñar
nuevos autómatas para cumplir con ciertas especificaciones.

Su proceso es el siguiente
1. Identificar los diferentes estados posibles del autómata
2. Enumerar las entradas posibles posibles
 3. Crear una tabla o matriz que representará el comportamiento del autómata en diferentes estados
y con diferentes entradas
4. Completar las celdas de la tabla con la información correspondiente a las transicioens del
autómata
5. Una vez completa la tabla, se analiza para determinar la equivalencia entre diferentes
autómatas, simplificar los existentes y diseñar nuevos autómatas para cumplir con ciertas
especificaciones.
Entre sus ventajas está la de poder representar de manera clara y concisa el comportamiento del
autómata en diferentes estados y con diferentes entradas. Sin embargo, una desventaja es que puede
volverse complicado y laborioso en el caso para un autómata con gran número de estados y entradas,
siendo a tabla resultando dificil de manejar y comprender.

En la práctica, se observa que los autómatas finitos no deterministas (AFN) son

ampliamente utilizados en lugar de los autómatas finitos deterministas (AFD).
¿Cuáles podrían ser algunas razones fundamentales detrás de esta preferencia en
aplicaciones del mundo real? Compare y contraste las ventajas y desventajas de los
AFN en términos de flexibilidad, expresividad y eficiencia computacional en
comparación con los AFD. Proporcione ejemplos concretos de situaciones en las
que los AFN son preferibles y explique por qué.(5pts)

Algunas de las razones fundamentales de que se prefiera los AFN sobre los AFD es que suelen ser más
económicos (menor número de estados , menor número de transiciones), tambien la capacidad para
manejar ciertos tipos de lenguajes de manera más facil, y su capacidad de simplificar ciertos procesos
de diseño y análisis de software. Comparando ambos tipos de autómatas tenemos que en términos de
flexibilidad, los AFN son más flexibles, ya que pueden expresar una mayor variedad de patrones y
estructuras de datos, por otro lado, en términos de expresividad, los AFD son más expresivos, ya que
pueden expresar de manera más precisa ciertos tipos de lenguajes formales. En cuanto a eficiencia
computacional, los AFD tienden a ser más eficientes, a que su estructura deterministica les permite
realizar ciertas operaciones de manera más rápida.

Una situación en la que los AFN son preferidos es en el reconocimiento de patrones de imagenes. Los
AFN son más flexibles como se mencionó antes y pueden manejar más eficientemente la variedad de
patrones y estructuras que pueden aparecer en una imagen, lo que lo hace el más adecuado para este
tipo de aplicación en comparación a los AFD que son más limitados en cuando a flexibilidad.

En la teoría de autómatas, las transiciones-ε agregan una capa adicional de

complejidad a los autómatas finitos. ¿Podría explicar en detalle cómo funcionan las
transiciones-ε y cómo afectan el comportamiento del autómata? Además, discuta
cómo las transiciones-ε impactan la definición formal de un autómata finito y
proporcionar un ejemplo concreto de un autómata con transiciones-ε que ilustre su
uso y su impacto en la aceptación de cadenas de entrada.(4pts)

Una transición -ε es una caracteristica especial de los AFN. Estas permiten que el autómata pase de un
estado a otro sin consumir ningún símbolo de la entrada. Es decir, son transiciones que se hacen de
manera “gratuita”. La “ ε” representa la cadena vacía, es decir, ausencia de simbolos.