AyG Feb24-Jun24 PEC2 Enunciado Cast

Autómatas y Gramáticas
Grado de Ingeniería Informática
PEC2
Nombre estudiante
Apellidos, Nombre
Presentación
En esta Prueba de Evaluación Continua se trabajan los conceptos básicos de la
asignatura sobre alfabetos, palabras y lenguajes, así como distintos conceptos sobre
lenguajes y gramáticas regulares e incontextuales
Competencias
● Capacidad para utilizar los fundamentos matemáticos, estadísticos y físicos para
comprender los sistemas TIC.
● Capacidad para analizar un problema en el nivel de abstracción adecuado a cada

situación y aplicar las habilidades y conocimientos adquiridos para resolverlo.
Objetivos
● Conocer las operaciones sobre lenguajes y palabras (concatenación, clausuras) y
saber utilizarlos para describir lenguajes complejos.
● Conocer la relación existente entre lenguajes regulares/incontextuales y gramáticas

regulares/incontextuales.
● Saber construir gramáticas regulares e incontextuales que generen un lenguaje

determinado.
● Saber expresar una gramática en cualquiera de las formas simplificadas y normales

más habituales.
Recursos de aprendizaje
Los siguientes recursos son de utilidad para la realización de la PEC:
Básicos
● Módulo didáctico 1. Alfabetos, palabras y lenguajes.
● Módulo didáctico 2. Autómatas finitos y lenguajes regulares.
● Módulo didáctico 3. Gramáticas incontextuales.
75.579 Autómatas y Gramáticas 2023/2 pág. 2

Complementarios
● Documentos de ayuda, como exámenes, pruebas de validación y PECs de
semestres anteriores publicados en el aula por el profesorado colaborador.
● Los recursos de aprendizaje que aparecen en la bibliografía de estos tres
módulos.
Criterios de valoración
La ponderación de los ejercicios es la siguiente:
● Ejercicio 1: 20%
El uso de recursos externos (Internet, material bibliográfico, etc.) ha de estar referenciado

en la bibliografía. https://biblioteca.uoc.edu/es/pagina/Como-citar/. La PEC se tiene que
realizar de manera individual y el trabajo entregado tiene que ser original citando
adecuadamente las fuentes bibliográficas utilizadas
La copia o plagio en la realización de la PEC comportará que la prueba sea evaluada con
un suspenso (D). En caso de que se haga uso de algún tipo de herramienta que utilice
inteligencia artificial, habrá que especificarlo explícitamente, y en el caso de que los
contenidos introducidos en la práctica no hayan sido adecuadamente adaptados a la
situación propuesta por el enunciado, la prueba será evaluada con una D.
De otra parte, y siempre a criterio de los Estudios de Informática, Multimedia y

Telecomunicaciones, la reincidencia en el incumplimiento de este compromiso puede
comportar que no se permita al estudiante superar ninguna otra asignatura mediante la
evaluación continua ni en el semestre en curso ni en los siguientes.

Formato y fecha de entrega
● La PEC2 con todas las actividades claramente diferenciadas se tiene que entregar en
un único documento Word, Open Office o PDF con las respuestas a las preguntas.
● El nombre del fichero tiene que ser: Apellido1-Apellido2-Nombre-PEC1.ext donde

“ext” hace referencia a la extensión del fichero.
● Este documento se debe de entregar en el espacio de Entrega PEC1 del aula antes
de las 23:59 del martes 7 de mayo de 2024.
● No se aceptarán entregas fuera de la fecha límite.
Enunciado
Nombre y Apellidos:

Observación: Las definiciones y la notación formal empleadas en la resolución de los
ejercicios tienen que ser los mismos que los empleados en los materiales de la
asignatura (a no ser que el enunciado del ejercicio especifique lo contrario).
Ejercicio 1 (20%)
Define una gramática incontextual para cada uno de los siguientes lenguajes:
i j k
1.1. L={ a b c | i, j, k ≥ 0, i = j o i = k }
S→AB ∣ AC
A→aA ∣ ε
B→bBc ∣ ε
C→cC ∣ ε
i j k
1.2. L={ a b c | i, j, k ≥ 0, i ≠ j o i ≠ k }
S→AB ∣ AC ∣ BC
A→aA ∣ ε
B→bBc ∣ ε
C→cC ∣ ε
i j k
1.3. L={ a b c | i, j, k ≥ 0 ,i +j = k }
S→ABc
A→aA ∣ ε
B→bB ∣ ε
i j k
1.4. L={ a b c | i, j, k ≥ 0 ,i + k = j }
S→aSck ∣ Ac
A→aA ∣ ε

Ejercicio 2 (20%)
Define formalmente los lenguajes representados por las siguientes gramáticas:
1.5. Sea la gramática G = ({A, B, S}, {0, 1, 2, a}, S, P) con S el símbolo inicial y P el
siguiente conjunto de producciones:
S → AaB
A → 0A1|01
B→ 2B1|21
Razona si el lenguaje generado por la gramática es un lenguaje regular o bien se
trata de un lenguaje incontextual no regular.
El lenguaje generado por esta gramática contiene cadenas que comienzan con una
secuencia de ceros, seguida de una secuencia de unos y termina con una secuencia
de dos y unos.
Por ejemplo, una cadena válida podría ser "001211", donde A genera "001" y B
genera "21". Ahora, veamos si el lenguaje generado es regular o no. La regla general
para un lenguaje regular es que puede ser reconocido por un autómata finito, o
equivalentemente, puede ser generado por una gramática regular.
Analizando las producciones, podemos ver que A y B generan cadenas que pueden
tener un número arbitrario de ceros, unos y dos, pero siempre en el mismo orden. Sin
embargo, la gramática no tiene una manera de recordar cuántos ceros, unos o dos
ha generado, lo que significa que no puede ser generada por un autómata finito.
Por lo tanto, el lenguaje generado por esta gramática no es regular, sino incontextual
no regular.
1.6. Sea la gramática G = ({S, A, B, C, D, E}, {a, b}, S, P) con S el símbolo inicial de la
gramática y P el siguiente conjunto de producciones:
S → Aa|Ca|a
B → Aa|Ca|a
C → Bb
D → Ca
E → Cb
Razona si el lenguaje generado por la gramática es un lenguaje regular o bien se
trata de un lenguaje incontextual no regular.

Este conjunto de producciones define un lenguaje donde las cadenas pueden
contener "a" seguido de "b", pero la cantidad de "a"s antes de "b" puede ser arbitraria
y no se puede determinar con un número finito de transiciones.
El lenguaje podría generar cadenas como "aab", "aaab", "aaaab", etc. Donde el
número de "a"s puede ser cualquier cantidad, pero siempre es seguido por un "b".
La presencia de la producción C→Bb crea una recursión en la generación de "a"s

antes del "b", lo que hace que el lenguaje no pueda ser reconocido por un autómata
finito.
Por lo tanto, el lenguaje generado por esta gramática no es regular, sino incontextual
no regular.
Ejercicio 3 (20%)
Indicar si L es regular o independiente del contexto no regular:
1.7. Sea el lenguaje L = {xmyn| m, n > 0, m es par y n es impar}. Indicar si el lenguaje L es

regular o independiente del contexto no regular
Este lenguaje no es regular, ya que no se puede definir un autómata finito que lo
reconozca. Para ver esto, considera que un autómata finito no puede contar de
manera efectiva el número de "a"s y "b"s y al mismo tiempo verificar si "m" es par y
"n" es impar. Por lo tanto, el lenguaje L es independiente del contexto no regular.
1.8. Sea L el lenguaje formado por las cadenas que tienen el doble número de b’s que de
a’s. Indicar si el lenguaje L es regular o independiente del contexto no regular
Este lenguaje tampoco es regular. No se puede definir un autómata finito que cuente
efectivamente el número de "a"s y "b"s y verifique que las "b"s sean el doble que las
"a"s. Por lo tanto, este lenguaje también es independiente del contexto no regular.

Ejercicio 4 (10%)
Analiza razonadamente si las siguientes gramáticas son ambiguas o no:
1.9.
G1:
S → SBS | A
A→ a
B→ b
1.10.
G2:
S → AB | C
A → aAb | ab
B → cBd | cd
C → aCd | aDd

D → bDc | bc
Ejercicio 5 (10%)
Considera una gramática G = (N, T , S, P) donde S es el símbolo inicial de la gramática,
P es el conjunto de producciones y T = { 0, 1, (, ), + , ∗, ∅, e }.
5.1. Se pide definir las producciones de la gramática que permitan generar el lenguaje de
las expresiones regulares sobre el alfabeto {0,1}. Se supondrá que la cadena vacía
viene representada por e
∗ ∗
5.2. Derivar la cadena (0 + (10) 1)
Ejercicio 6 (20%)
5.1. Aplicando los algoritmos en el orden correcto, encontrad una gramática limpia y
pelada, equivalente a la gramática G= (V , T , S , P ) on V = { S , A , B ,C } y T = {a ,b }.
P:
S → ASB∨a
A →aAS|C| λ
B→ SbS∨bb
C→a
5.2. A partir del resultado obtenido en el apartado anterior, encontrad una gramática
simplificada en Forma Normal de Chomsky (FNC).
5.3. Encontrad una gramática simplificada en Forma Normal de Greibach (FNG)
equivalente a la gramática G= (V , T , S , P ) on V = { S , X , Y } , T ={ a , b }
P:
A1 → A 2 A3 ∨A 4 A 4
A 4 → A1 A 4 ∨b
A2 → b
A3 → a


AyG Feb24-Jun24 PEC2 Enunciado Cast

Cargado por

Copyright:

Formatos disponibles

AyG Feb24-Jun24 PEC2 Enunciado Cast

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

AyG Feb24-Jun24 PEC2 Enunciado Cast

Cargado por

Copyright:

Formatos disponibles

Autómatas y Gramáticas

Grado de Ingeniería Informática

● Capacidad para analizar un problema en el nivel de abstracción adecuado a cada

● Conocer la relación existente entre lenguajes regulares/incontextuales y gramáticas

● Saber construir gramáticas regulares e incontextuales que generen un lenguaje

● Saber expresar una gramática en cualquiera de las formas simplificadas y normales

75.579 Autómatas y Gramáticas 2023/2 pág. 2

El uso de recursos externos (Internet, material bibliográfico, etc.) ha de estar referenciado

De otra parte, y siempre a criterio de los Estudios de Informática, Multimedia y

75.579 Autómatas y Gramáticas 2023/2 pág. 3

● El nombre del fichero tiene que ser: Apellido1-Apellido2-Nombre-PEC1.ext donde

● No se aceptarán entregas fuera de la fecha límite.

75.579 Autómatas y Gramáticas 2023/2 pág. 4

75.579 Autómatas y Gramáticas 2023/2 pág. 5

75.579 Autómatas y Gramáticas 2023/2 pág. 6

La presencia de la producción C→Bb crea una recursión en la generación de "a"s

1.7. Sea el lenguaje L = {xmyn| m, n > 0, m es par y n es impar}. Indicar si el lenguaje L es

75.579 Autómatas y Gramáticas 2023/2 pág. 7

75.579 Autómatas y Gramáticas 2023/2 pág. 8

75.579 Autómatas y Gramáticas 2023/2 pág. 9

También podría gustarte