En esta página encontrará ejercicios corregidos sobre: optimización de autómatas, determinación y minimización.
Determinación
Ejercicio 1
Determine los siguientes autómatas:
Ejercicio 2
Consideramos el alfabeto A formado por las letras del alfabeto de la lengua francesa y el idioma L = {w ∈ A * / w termina en man}. Encuentre un autómata determinista que genere L.
Sea x todas las letras que no son {a, m, n}. El autómata debe reconocer las palabras [az; ARIZONA]*hombre. Construyamos un autómata indeterminista con el algoritmo de Thompson (aquí notamos que las transiciones épsilons no son útiles). El autómata es el siguiente:
Después de la determinación obtenemos el siguiente autómata:
Ejercicio 3
Sea L el lenguaje aceptado por el autómata A a continuación:
Encuentre una gramática regular que genere L. Encuentre una expresión regular que denote L. Encuentre un autómata determinista que acepte L.
Aquí están las producciones gramaticales obtenidas directamente del autómata: P → aP, P → aQ, Q → bP, Q → R, R → bR, R → cQ, R → bP, R → epsilon. Los no terminales (por lo tanto, los nodos del autómata) de la gramática son {P, Q, R}, el símbolo inicial es P.
Denotando con Xpag, Xq, Xr los lenguajes aceptados de los estados P, Q y R respectivamente, el sistema de ecuaciones para estos lenguajes es:
¡Tenga cuidado, una recursividad de un no terminal dará como resultado una estrella, y una distribución con no terminales provocará una concatenación!
Determinamos el autómata:
Ejercicio 4
Consideramos la gramática regular G = (Γ, Σ, S, Π) con Γ = {S, P, R}, Σ = {a, b} y Π = {S → P, P → baR, P → aS, R → bb, R → aP}. Busque una expresión regular para este idioma. Construir un autómata A aceptando el lenguaje definido por la gramática G. Dar explícitamente A en la forma (Q, Σ, q0, F, ∆). Encuentra un autómata determinista que acepte este lenguaje.
Usamos las mismas letras S, P y R para los lenguajes aceptados de los estados S, P y R. Estos lenguajes satisfacen el sistema de ecuaciones:
La primera ecuación da S = P, al sustituir las expresiones por S y R en la segunda ecuación obtenemos P = aP + ba (aP + bb) que es equivalente a P = (a + baa) P + babb. Aquí, P actúa como un estado inicial porque solo hay una transición entre S y P.
Resolvemos esta última ecuación: P = (a + baa) ∗ babb, entonces L (A) = S = P = (a + baa) ∗ babb.
Comience desde el autómata Thompson para llegar a:
Al determinar el autómata A obtenemos B (para mayor comodidad, a veces es útil poner un estado basura tomando las interacciones sin nodos de llegada):
Ejercicio 5
Construya un autómata finito determinista correspondiente a cada autómata a continuación y calcule una expresión regular para el lenguaje aceptado usando la gramática asociada:
Ejercicio 6
Un cantinero ciego juega el siguiente juego con un cliente: tiene una bandeja frente a él con cuatro vasos dispuestos en un cuadrado. Cada uno de estos vasos puede o no girarse, sin que el bartender lo sepa. La finalidad de este último es disponer de forma que todos los vasos giren en la misma dirección. Para hacer esto, cada turno puede elegir una de las siguientes tres acciones: $
- girar uno de los vasos
- girar dos vasos vecinos
- gira dos vasos opuestos
pero para aumentar la dificultad, el cliente puede girar la bandeja cualquier número de cuartos de vuelta entre cada una de las acciones del camarero. El juego termina tan pronto como se alcanza una de las dos posiciones ganadoras.
Demuestre que podemos restringir el número de configuraciones diferentes a cuatro, luego represente las posibles acciones del juego mediante un autómata no determinista.
Determine este autómata y deduzca una estrategia ganadora para la barra.
Solo son posibles cuatro configuraciones:
-los cuatro vasos están todos en la misma dirección (configuración q0)
- tres vasos están en una dirección y el cuarto en la otra dirección (configuración q1)
-dos vasos vecinos están en una dirección y los otros dos en la otra dirección (configuración q2)
-dos vidrios opuestos están en una dirección y los otros dos en la otra dirección (configuración q3).
Denotamos por la letra:
-ha cambiado la orientación de uno de los cuatro vasos
-b cambiar la orientación de dos vasos vecinos
-c cambiar la orientación de dos vasos opuestos.
Entonces, el juego puede ser representado por el siguiente autómata no determinista:
Su determinación conduce al siguiente autómata:
Vemos que la palabra reconocida cbcacbc conduce a una posición ganadora para el bartender.
Minimización
Ejercicio 7
Consideramos el siguiente autómata A = ({a, b}, {1, 2, 3}, ∆, {1}, {1}):
Da la tabla que describe ∆. ¿La palabra baabab es aceptada por el autómata A (compruébalo desenrollando la gramática que habrás escrito previamente)? Dé el autómata finito determinista mínimo que reconoce el mismo lenguaje que A.
∆ = {(1, a, 2), (1, b, 1), (1, b, 3), (2, a, 1), (2, a, 3), (3, b, 1) }
baabab no es aceptado por la máquina. Podemos agregar un pozo, denominado #, al autómata para completarlo. El árbol de lectura es entonces el siguiente:
Ninguna hoja corresponde a un estado final, tenga en cuenta que todas las hojas terminan en el pozo.
El autómata determinista:
Los estados {1} y {1,3} tienen las mismas reglas. Por tanto, encontramos el autómata mínimo:
Ejercicio 8
Entre las siguientes expresiones regulares y autómatas, indique cuáles son los autómatas y las expresiones regulares que representan el mismo idioma:
Queremos comparar los cuatro idiomas. Calculamos el autómata mínimo de cada idioma. Entonces será suficiente comparar estos autómatas. De hecho, el autómata mínimo es un objeto canónico que depende únicamente del lenguaje, por lo que dos lenguajes son iguales si tienen el mismo autómata mínimo (módulo de cambio de nombre de estados).
1 - Expresión racional (ab ∗ a + b (a + b)) ∗. Comenzamos construyendo un autómata mediante un método de su elección:
Ahora queremos construir el autómata de lenguaje mínimo. Para hacer esto, primero debemos determinar y luego minimizar el autómata anterior. Por suerte, ya tenemos un autómata determinista, por lo que podemos ir directamente al algoritmo de minimización que nos da el siguiente resultado:
2 - Expresión racional (ab + b (a + b)) ∗. Comenzamos construyendo un autómata usando el método de Glushkov:
Asimismo, el autómata ya es determinista. Después de la minimización tenemos el siguiente autómata:
3 - Para minimizar A3, primero debemos determinarlo. Aquí está el resultado del algoritmo de determinación:
Y después de la minimización:
4 - El autómata ya es determinista, después de la minimización obtenemos:
Ahora que hemos construido el autómata mínimo para cada uno de los cuatro idiomas, podemos compararlos. Observamos que el cambio de nombre en módulo de estados, los lenguajes de A3 y (ab + b (a + b)) ∗ tienen el mismo autómata mínimo y, por lo tanto, son iguales. Lo mismo ocurre con los idiomas A4 y (ab ∗ a + b (a + b)) ∗.
Ejercicio 9
Sea Σ = {a, b}, consideramos dos lenguajes siguientes: L, el lenguaje formado por todas las palabras de Σ ∗ que contienen aba; M, el lenguaje definido por la expresión regular (b + aa ∗ bb) ∗ (ε + aa ∗ + aa ∗ b).
Dé un autómata no determinista que reconozca L. Determine el autómata mínimo A que reconozca a L.
Dé un autómata no determinista con transiciones ε que reconozcan M. Determine el autómata mínimo B que reconozca M.
Comparando los dos autómatas obtenidos A y B se deduce que L = complementario (M). En términos de un autómata, el complemento de un autómata A equivale a convertir los estados entrantes en estados terminales y viceversa.
Después de determinar el idioma o la gramática de L, entrenamos al autómata para el método de Glushkov:
Entonces lo determinamos:
Cambiamos el nombre de los estados en orden por A, B, C, D, E, F para evitar ambigüedades. Luego minimizamos:
Lo mismo ocurre con el autómata que reconoce a M:
Tenemos determinismo (notaremos que formamos un estado basura):
Cambiamos el nombre de los estados en orden por K, L, M, N para evitar ambigüedades. El autómata ya es mínimo.
Vemos que la única diferencia entre los autómatas deterministas A y B es que los estados finales de uno no son finales en el otro. De lo cual podemos deducir que sus lenguajes son complementarios.
ES 
FR 
EN