teoria de lenguaje

Teoría de Lenguajes

Práctico 1

Práctico 1: Expresiones Regulares. Relación RL.
Básicos: 1, 2, 3, 4, 5, 9.
Intermedios: 6, 7.
Avanzado: 8.

Ejercicio 1 [Julio 98]
Completar el siguientecuadro, indicando la pertenencia o no de cada tira en cada
uno de los lenguajes denotados por las expresiones regulares :
a*ba*

(a|b)*a*

(a|b)(a*|b)

(b*a)*

ab
aabb

b*a(a*b)*(b|ε)(ba|a)

ε

ba
bba
babab
b
abaa

Ejercicio 2
Escriba expresiones regulares para representar los siguientes lenguajes:
a)
b)
c)
d)
e)
f)

Números enteros (sin ceros no significativos).Identificadores en Pascal.
Matrículas de autos de Rocha.
Matrículas de autos de Uruguay.
Números de teléfono de Paysandú.
Tiras definidas sobre ∑={a,b} cuyo antepenúltimo símbolo de la derecha esuna a.
g) {x / x es de la forma ambncj, con m>0, j>0, n≥0}.
h) Tiras definidas sobre ∑={a,b} con a los sumo dos b’s.
i) Tiras definidas sobre ∑={a,b} con cantidad par de b’s.
j) Tiras definidassobre ∑={a,b} que tienen una sola vez el substring ab o
(exclusivo) una sola vez el substring ba.
k) Tiras definidas sobre ∑={a,b} que tienen a lo sumo dos a’s consecutivas
(eventualmente más de unavez).
l) Tiras definidas sobre ∑={a,b} que tienen exactamente una vez, tres a’s
consecutivas.
Ejercicio 3
Sean r, s y t expresiones regulares tales que R=L(r), S=L(s) y T=L(t). Escribaexpresiones regulares correspondientes a los lenguajes:
L1 = {x / x=w1w2…wn, con n≥1, (wi ∈ R) ∨ (wi ∈ S) ∨ (wi ∈ T)}
L2 = {x / x=w1w2…wn, n≥1, (n mod 3)=0, wi ∈ R si (i mod 3)=0,
wi ∈ S si (i mod 3)=1, wi∈ T si (i mod 3) = 2}
L3 = {x / x=w-h… w-1w1…wn, n≥1, h≥1, y ∀ i≥1 wi ∈ R y w-i ∈ S}
L4 = {x / x=w-h… w-1w1…wn, n≥1, h≥1, y ∀ i≥1 w-2i ∈ R, w2i ∈ S,
w-2i+1 ∈ S, w2i-1 ∈ T}

Página 1 de 2

Teoríade Lenguajes

Práctico 1

Ejercicio 4
Describa en lenguaje natural el conjuntos denotado por la siguientes expresiones
regulares
1. ((11)*1 0)* (11)* 1
2. (11 | 0)* (00 | 1)*
3. (1 | 01...