examen

ENUNCIADOS DE PROBLEMAS.
Asignatura: Teoría de Autómatas y Lenguajes Formales
Escuela Universitaria de Informática (UPM)
TEMA 1 (Lenguajes formales y gramáticas)
Ejercicio 1
Dados los siguientes lenguajes formales definidos sobre el alfabeto = {a, b}:
• L0={}
• L1={ε}
• L2={a}
• L3={a,b}
• L4={(ab)n | 0= 0 }
• L6={anbn | n>=0 }
• L7 ={lenguaje formado por las palabras que tienen unnúmero impar de aes}
Determinar para cada uno de ellos L0, L3 y L*
Ejercicio 2
Sean las siguientes operaciones con los anteriores lenguajes formales:
L0n L1n, L0n| L1n, L 0n |L0n, L3n L1n, L3n | L1n, L3n L0n, L3n| L0n, L7n  L5n, L7n| L5n
1. Determinar qué lenguajes definen suponiendo que n = 0.
2. Determinar qué lenguajes definen suponiendo que n = 3
3.Determinar qué lenguajes definen suponiendo que n = *
Ejercicio 3
Sea  un alfabeto cualquiera y L un lenguaje cualquiera definido sobre el alfabeto anterior. Para cada una de las siguientes igualdades, justificar si siempre son ciertas o no.

• L*=L+
• *=L+
• +=L+
• L+=L*-ε
• +=∑*- ε
• ∑*=(∑*)-1
• Φ*= ε=Φ+
• L =*- L = L*-L
• L1-L2 = L1 ∩ L2 = L1L2
• (L*)*=(L+)*=(L*)+=L*=(L+)+• (L*)I=(LI)*
• L1-(∑*-L1)=L1
• L1-∑*-L1= Φ



Ejercicio 4
Obtener una gramática para cada uno de los siguientes lenguajes:
1.  = {a, b, c}, L = {an bm cn | n, m >= 1}
2.  = {a, b, c}, L = {an bm cn+2m | n >=0, m >= 1}
3.  = {a, b, c}, L = {an bn+m cm | n >= 1, m >= 0}
4.  = {a, b}, L = {an bm | n >= m >= 1}
5.  = {a, b}, L = {an bm | n > m >= 0}
6.  = {a, b, c}, L = {ambn ck | m > n + k ; n, k >=0}
7.  = {a, b}, L = { anbm  m 0}
Ejercicio 5
Construir una gramática que especifique el siguiente lenguaje:
L = { w  {0, 1, 2}* | w contiene exactamente dos o tres símbolos 0 en cualquier posición}.
¿Sería posible obtener una gramática regular o de tipo 3?
Ejercicio 6
Dado el alfabeto = {a, +, = } y el siguiente lenguaje: L={an+am=an+m | n, m > 0},construir una gramática de tipo 2 que defina dicho lenguaje.
Ejercicio 7
Para el alfabeto  = {a, b, c} construir una gramática que genere el lenguaje L cuyas palabras cumplen las siguientes condiciones:
• Empiezan y terminan por a.
• Entre los dos símbolos a sólo hay símbolos b y c, con la peculiaridad de que deben aparecer de forma alterna y en cuantía indeterminada (de cero a infinito). Además,esta subcadena de símbolos b y c alternos puede empezar por cualquiera de los dos y puede tener longitud par o impar.
Ejercicio 8
Sea el lenguaje de sumas de números naturales sobre  = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, + }.
Ejemplos de palabras del lenguaje: 2+67+9870 ó 35
Ejemplos de palabras no válidas: 34+ ó 34++23
Representar mediante una gramática de tipo 2 en notación BNFlos siguientes lenguajes.
1. Sea L1 el lenguaje de sumas en el que los números naturales no pueden tener ceros a la izquierda. El número 0 se representará por un único cero, nunca por una secuencia de ceros.
Ejemplo:10+0
Ejemplo de palabra no válida: 03+12
2. Sea L2 el lenguaje de sumas en el que los números naturales pueden empezar por 0, aunque no sea el número 0, pero en cada sumase cumple siempre la condición de que el primer y el último número tienen siempre la misma longitud (al menos habrá dos números).
Ejemplo: 10+1+01
Ejemplos de palabras no válidas: 03+129 , 1
3. Sea L3 el lenguaje de sumas en el que los números naturales pueden empezar por 0, aunque no sea el número 0, pero en el que se cumple la condición de que al menos dos números tienen la mismalongitud.
Ejemplo: 0503+30+450+89+203+03
Ejercicio 9
Para las gramáticas que se proponen a continuación, determinar el tipo de las mismas y el lenguaje generado.
1. S  0S  A
A  0B  0
B  1A
2. S abA  bbB
A  bC
B  a
C  cS  
3. S  0A
A  0A | 1S | 0
Ejercicio 10
Dada la siguiente gramática:
S ---> aAa
Aa ---> bAa | ba
Determinar de forma...