Departamento de Ciencias de la Computación
Licenciatura en Informática - Ingeniería en Informática
Matemática discreta – 2022
TP Nº 7
TEMA: Lenguajes y gramáticas
1. Describa en palabras los lenguajes siguientes para A={a,b}:
a) L1 = {a, ab, ab 2 , ab 3 , ab 4 ,…}
b) L2 = {a m b n : m>0, n>0}
c) L3 = { a m b m : m>0}
d) L4 = { a m ab n : m>0}
2. *Determine si cada una de las gramáticas G con las producciones siguientes es sensible al contexto,
libre al contexto, regular o de ningún tipo. También indique las razones:
a) SàA; SàAAB; AaàAba; Aàaa; BbàABb; ABàABB; Bàb
b) SàBAB; SàABA; AàAB; BàBA; AàaA; Aàab; Bàb
c) <S>:: b <S>| a <A >| a; <A>::a < S > l b <B>; <B> :: = b <A>|a <S>| b
3. Sean K={a, ab, a2} y L= {b2, aba} lenguajes sobre A= {a, b}, hallar:
a) KL
b) LL
c) KK
d) L0
4. En los ejercicios siguientes se especifica una gramática G. En cada caso describa con precisión el
lenguaje L (G) producido por la gramática.
a) G = (V, T, P, S) donde: V = {S, A, B}; T = {a, b}; P = {SàaB; SàbA; Aàa; AàaS; A
àbAA; Bàb; BàbS; BàaBB}
b) G = ( V, T, &0 , à ) donde: V = ( &0 , &1 , &2, a, + , ( , ) ) ; T = { ( , ) , a , + }; P= {&0 à
( &0 ) //donde los paréntesis ( , ) son símbolos de T; &0 à a + &1; &1 à a + &2; &2 à a
+ &2; &2 à a
c) *G1 = ({0,1}, {A, B}, A, {A ::= B1 | 1, B ::= A0})
d) *G2 = ({0,1}, {A, B}, A, {A ::= 1B | 1, B ::= 0A})
e) *G3 = ({a,b}, {S, A}, S, {S ::= bA, A ::= aS | a})
5. *Crear una gramática que genere los siguientes lenguajes:
a) L = { an | n ∈ [1, 3] }
b) L = { an | n > 0 }
c) L = { an | n ∈ [0, 3] }
d) L = { an | n ≥ 0 }
6. *Decir cuales son las posibles cadenas del lenguaje que corresponden a la expresión regular
a) ab| c*
b) ab*|ab*c
c) (0 |1 | 2)+
d) a(b|c|d)e
e) (01)*
f) (01)*+0+10
g) (ab*+b*a)ab+
Departamento de Ciencias de la Computación
Licenciatura en Informática - Ingeniería en Informática
Matemática discreta – 2022
TP Nº 7
TEMA: Lenguajes y gramáticas
h) Para indagar:
i. ^(1[0-2]|0[1-9])/(3[01]|[12][0-9]|0[1-9])/[0-9]{4}$
7. *Encuentre las expresiones regulares que corresponden a los siguientes lenguajes, definidos sobre
el alfabeto S = {a, b}
a) Lenguaje de todas las cadenas tal que cada b esta precedida por lo menos por una a.
b) Lenguajes de todas las cadenas que comienzan con b y terminan con a.
c) Lenguajes de todas las cadenas que tienen un numero par de símbolos ( cadenas de longitud par)
d) Lenguajes de todas las cadenas que tienen un número par de aes.
e) Ahora el alfabeto es el alfabeto S = {0, 1}:
i. Lenguajes con cadenas que tengan exactamente dos 0.
ii. Lenguajes con cadenas que el penúltimo símbolo de izquierda a derecha sea 0.
8. *Una puerta blindada dispone de una única cerradura. Para abrirla es necesario hacer girar en ella
tres llaves diferentes (denominadas a, b y c), en un orden predeterminado, que se describe a
continuación:
• Llave a, seguida de llave b, seguida de llave c, o bien
• Llave b, seguida de llave a, seguida de llave c.
Si no se respeta este orden, la puerta se bloquea, y es imposible su apertura; por ejemplo, si se hace
girar la llave a, se retira la misma, se introduce de nuevo y se hace girar.
Una vez abierta la puerta, la introducción de las llaves en su cerradura, en cualquier orden, no afecta
al mecanismo de cierre (la puerta permanece abierta).
Considérese que las denominaciones de las llaves son símbolos de un alfabeto, sobre el que define el
lenguaje L cuyas palabras son las secuencias permitidas de apertura de la puerta. Por ejemplo, abcbc
es una palabra del referido lenguaje.
Generar la gramática que genera las palabras de L.
9. *Definir una gramática para núemeros enteros. Determinar cada componente de las gramática.
Un entero se define como una cadena consistente en un signo opcional (+ o −) seguido de una
cadena de dígitos (0 al 9). La siguiente gramática genera todos los enteros.
10. *Definir una gramática que permita generar identificadores, es decir, una secuancia de letras y
dígitos que empiezan siempre con una letra.
[Manos en el código]
11. *Desarrollar un script en el lenguaje de programación que más familiarizado esté, que
mediante el uso de expresiones regulares, permita contar la cantidad de ocurrencias de
alguna palabra (determinada por un usuario por ejemplo) en el archivo
“21_leyes_del_liderazgo.txt'”.
