Ejercicios corregidos en el teoría del lenguaje, 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)posee. Para esto puedes hacer un árbol 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

Dé todas las palabras de longitud 0, 1, 2, 3 y 4 reconocidas por los siguientes autómatas. Esta pregunta puede responderse sistemáticamente mediante el uso de matrices. Para ello, representamos al autómata (que podemos ver como un grafico) por la matriz de adyacencia. Así, el coeficiente í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.

Ejercicios corregidos sobre teoría de lenguajes, autómatas y gramáticas. Los ejercicios van seguidos de una corrección.

Para el autómata A1, basta con evaluar (1,3) y (1,4) de las siguientes matrices:

Ejercicios corregidos sobre teoría del lenguaje, autómatas y gramáticas.

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:

Ejercicios corregidos sobre teoría del lenguaje, autómatas y gramáticas.

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:

Ejercicios corregidos sobre teoría del lenguaje, autómatas y gramáticas.

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

Ejercicios corregidos sobre teoría del lenguaje, autómatas y gramáticas.

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

Ejercicios corregidos sobre teoría del lenguaje, autómatas y gramáticas.

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:

Ejercicios corregidos sobre teoría del lenguaje, autómatas y gramáticas.

Ejercicio 7

 Estar allí 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 }.

Encuentre el sistema de ecuaciones (deexpresiones regulares) coincidencia. 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:

Ejercicios corregidos sobre teoría del lenguaje, autómatas y gramáticas.

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.

Ejercicios corregidos sobre teoría del lenguaje, autómatas y gramáticas.

El sistema de ecuaciones regulares asociado con A:

Ejercicios corregidos sobre teoría del lenguaje, autómatas y gramáticas.

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 *.

Compartir, repartir
es_ESES