Ejercicios corregidos sobre teoría de lenguajes, autómatas y gramáticas. Los ejercicios van seguidos de una corrección.
Palabras reconocidas
Ejercicio 1
Proporcione todas las palabras de tamaños 0, 1, 2, 3 y 4 de los siguientes idiomas regulares: (a + ba)* ; a (aa + b (ab) ∗Para)∗Para. Para eso, puede hacer un árbol de posibilidades para cada uno de los idiomas.
Palabras de longitud 0: épsilon; Palabras de longitud 1: a; Palabras de longitud 2: aa, ba; Palabras de longitud 3: aaa, aba, baa; Palabras de longitud 4: aaaa, aaba, abaa, baba, baaa.
Palabras de longitud 0: ninguna; Palabras de longitud 1: ninguna; Palabras de longitud 2: aa; Palabras de longitud 3: ninguna; Palabras de longitud 4: aaaa, abaa.
Ejercicio 2
Proporcione todas las palabras de longitud 0, 1, 2, 3 y 4 reconocidas por los siguientes PLC. Es posible responder a esta pregunta de forma sistemática utilizando las matrices. Para hacer esto, representamos el autómata (que podemos ver como un gráfico) por la matriz de adyacencia. Así, el coeficiente del índice i, j de la matriz Mk corresponde a las palabras de longitud k reconocidas por el PLC, si el estado inicial fue el estado i y el estado final, el estado j. Si deseamos obtener las palabras de longitud k reconocidas por nuestro autómata, basta con multiplicar la matriz por sí misma.
Para el autómata A1, basta con evaluar (1,3) y (1,4) de las siguientes matrices:
Palabras de longitud 0: ninguna; Palabras de longitud 1: b; Palabras de longitud 2: ab + aa + ba; Palabras de longitud 3: aba + abb + aaa + baa; Palabras de longitud 4: abaa + abab + abba + abbb + aaaa + baaa.
Para el autómata A1, basta con evaluar (1,1) y (1,2) de las siguientes matrices:
Palabras de longitud 0: M0 1.1 + M0 1.2 =; Palabras de longitud 1: M1 1,1 + M1 1,2 = a; Palabras de longitud 2: M2 1,1 + M2 1,2 = aa + bb; Palabras de longitud 3: M3 1,1 + M3 1,2 = aaa + bba + abb; Palabras de longitud 4: M4 1,1 + M4 1,2 = aaaa + abba + aabb + bbaa + bbab
Ejercicio 3
Sea el siguiente autómata M:
¿Cuántos estados tiene el autómata M? Dar el conjunto de estados finales y el conjunto de estados
Iniciales. ¿Es el autómata determinista? ¿En qué estado se encuentra el controlador después de leer la palabra bbabbb? ¿Esta palabra es reconocida por el PLC / aceptada por el PLC? Las mismas preguntas para la palabra babaabba.
Completa el controlador M. ¿Este autómata reconoce la palabra baa? aceptado por esta máquina?
Sea el siguiente autómata N:
¿En qué estados puede estar el autómata N después de haber leído a babba? ¿Esta palabra es aceptada por este autómata? Misma pregunta para la palabra abbb.
Las primeras preguntas piden una descripción formal del autómata M. Cuando construimos la tabla de transición, notamos que el autómata M es determinista a diferencia del autómata N. Para completar M, debemos agregar el estado basura, se reconocen todas las palabras excepto el el lenguaje aceptado sigue siendo el mismo que incompleto.
Para leer la primera palabra: 1 ⊢ b1 ⊢ bb1 ⊢ bba2 ⊢ bbab3 ⊢ bbabb4 ⊢ bbabbb2 o 2 no es un estado final, por lo que se reconoce pero no se acepta. El principio de derivación es el mismo si el autómata es determinista; de lo contrario, se debe crear un árbol de derivación.
Para leer la última palabra:
Tenga en cuenta que el autómata puede leer la palabra abbb de dos formas, cuando una palabra ya no se puede leer en una rama, notamos # y la rama termina.
Construcción de autómatas
Ejercicio 4
Para cada uno de los idiomas a continuación, explique el idioma y dibuje un autómata que lo reconozca mediante un método de construcción.
- L es el idioma denotado por aba + bab.
- L es el idioma denotado por (aba)∗+ (bab)∗.
- L = {u ∈ {a, b}∗ tal que u contiene el factor bbb}.
- L = {u ∈ {a, b}∗ tal que u no contiene el factor bbb
Ejercicio 5
Construya con el método de su elección los autómatas que reconocen los siguientes idiomas (escriba la expresión regular que denota estos idiomas):
- El idioma de las palabras que contienen al menos una vez la letra a
- El idioma de las palabras que contienen como máximo una vez la letra a
- El lenguaje de palabras que contienen un número par de veces la letra a.
- El lenguaje de las palabras admitiendo aba como factor
Lenguaje reconocido
Ejercicio 6
Utilizando el método de su elección, determine el idioma reconocido por los siguientes PLC:
Ejercicio 7
Sea la gramática G = ({a, b, c}, {S, A}, S, P); donde P contiene las siguientes reglas: S → aS | licenciado en Letras; A → cA | ε
Determine si las palabras w1 = abac, w2 = aabccc, w3 = cabbac y w4 = ab son generadas por G. Encuentre el lenguaje generado por G (que denotamos por L (G)).
Las palabras w1 y w3 no son generadas por G; las palabras w2 y w4 son generadas por G: S ⊢ aS ⊢ aaS ⊢ aabA ⊢ aabcA ⊢ aabccA ⊢ aabcccA ⊢ w2 y para w4: S ⊢ aS ⊢ abA ⊢ ab = w4.
Para encontrar el idioma, escriba el autómata generado por la gramática y luego use el método de su elección para obtener su expresión regular: a * bc *.
Ejercicio 8
Sea la gramática g = <{a, b, c}, {S, A, B}, S, P> donde: P = {S → aA | ε; A → bA | cB; B → bB | Para }.
Encuentra el sistema de ecuaciones correspondiente (de expresiones regulares). Resuelve este sistema.
Asociaremos una variable con cada no terminal de g: X0 (asociado con S), X1 (con A) y X2 (con B). Traducimos las reglas de producción de P en ecuaciones de expresión regular:
Aplicando el teorema de Arden a la tercera ecuación, obtenemos: X2 = b * a. Reemplazando X2 en la segunda ecuación tendremos: X1 = b.X1 + cb * a; luego con el teorema de Arden obtenemos: X1 = b * cb * a. Reemplazamos en la primera ecuación y tendremos: X0 = ab * cb * a + ε que denota el lenguaje generado por g.
Ejercicio 9
Sea la gramática g = <{a, b, c}, {S, A, B}, S, P> donde: P = {S → baA | aS | ε; A → aA | bB | ε; B → cB | Automóvil club británico}.
Construya el autómata de estado finito simple A equivalente a g. Escribe el sistema de ecuaciones asociado con A. Encuentra la expresión regular que denota L (A).
Para encontrar el autómata simple asociado con g, podemos descomponer la regla S → baA en dos reglas: S → bC y C → aA; o C es un nuevo no terminal. Construimos el autómata simple equivalente A asociando un estado del autómata con cada no terminal, este estado será final cuando el no terminal asociado produzca ε. Las transiciones de A se deducirán de las reglas de producción de g.
El sistema de ecuaciones regulares asociado con A:
Para encontrar la expresión regular que denota L (A), resolvemos el sistema para encontrar el valor de X0. De la cuarta ecuación tenemos: X3 = c * aX2; reemplazamos en el tercero: X2 = aX2 + bc * aX2 + ε = (a + bc * a) X2 + ε que se resuelve con X2 = (a + bc * a) *. Reemplazamos en el segundo: X1 = a (a + bc * a) *. Luego, en el primero: X0 = aX0 + ba (a + bc * a) * + ε. Y así obtenemos la solución: X0 = a * (ba (a + bc * a) * + ε). Entonces L (A) se denota mediante la expresión regular: a * ba (a + bc * a) * + a *.
ES 
FR 
EN