En esta página encontrarás ejercicios corregidos sobre la optimización de autómatas, la determinación y la minimización.

Determinación

Ejercicio 1

Determine los siguientes autómatas:

ejercicios corregidos de optimización, determinación y minimización de autómatas.

Ejercicio 2

Consideramos el alfabeto A formado por las letras del alfabeto de la lengua francesa y la lengua L = { w ∈ A* / w termina en man}. encontrar un autómata determinista que genera 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 epsilons no son útiles). El autómata es el siguiente:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

Después de la determinación obtenemos el siguiente autómata:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

Ejercicio 3

Sea L el lenguaje aceptado por el autómata A a continuación:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

Encontrar un gramática L generadora regular. Encuentre un expresión regular denotando 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!

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

Determinamos el autómata:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

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:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

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:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

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):

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

Ejercicio 5

Construir 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:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

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:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

Su determinación conduce al siguiente autómata:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

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}):

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

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:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

Ninguna hoja corresponde a un estado final, tenga en cuenta que todas las hojas terminan en el pozo.

El autómata determinista:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

Los estados {1} y {1,3} tienen las mismas reglas. Por tanto, encontramos el autómata mínimo:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

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:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

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:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

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:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

2 - Expresión racional (ab + b (a + b)) ∗. Comenzamos construyendo un autómata usando el método de Glushkov:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

Asimismo, el autómata ya es determinista. Después de la minimización tenemos el siguiente autómata:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

3 - Para minimizar A3, primero debemos determinarlo. Aquí está el resultado del algoritmo de determinación:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

Y después de la minimización:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

4 - El autómata ya es determinista, después de la minimización obtenemos:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

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:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

Entonces lo determinamos:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

Cambiamos el nombre de los estados en orden por A, B, C, D, E, F para evitar ambigüedades. Luego minimizamos:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

Lo mismo ocurre con el autómata que reconoce a M:

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

Tenemos determinismo (notaremos que formamos un estado basura):

ejercicios corregidos sobre optimización, determinación y minimización de autómatas

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.

Compartir, repartir
es_ESES