Práctico 1: Lenguajes y Expresiones Regulares
Año 2023
Ejercicio 1. Sea Σ = {a, b} un alfabeto y α = aa, β = bb, obtener las pal-
abras αϵ, αα, αβ, β 0 , β 4 , α4 β 4 , (αβ)4 , (αβ)R y el conjunto Σ∗ .
Ejercicio 2. Sea Σ = {a, b, c, d} un alfabeto y α = bcbaadb, listar todos los
prefijos y sufijos de α indicando si son propios o no.
Ejercicio 3. Sea α, β, γ ∈ Σ∗ , probar que α(βγ) = (αβ)γ, es decir, la con-
catenación de cadenas es asociativa. Luego, probar que la concatenación de
cadenas no es conmutativa.
Ejercicio 4. Sean Σ un alfabeto, α ∈ Σ∗ y n, m ≥ 0, probar que |αn+m | =
|α | + |αm |.
n
Ejercicio 5. Sea Σ un alfabeto, α, β ∈ Σ∗ , probar que (αβ)R = β R αR .
Ejercicio 6. Sea Σ = {a, b} un alfabeto, definir los siguientes lenguajes por
enumeración, y luego, por comprensión:
• L1 es el lenguaje de todas las palabras de longitud 2.
• L2 es el lenguaje de todas las palabras de longitud a lo sumo 3.
• L3 es el lenguaje de todas las palabras que comienzan con dos a’s.
• L4 es el lenguaje de todas las palabras que tienen exactamente una sola b.
• L5 es el lenguaje de todas las palabras que comienzan y terminan con a.
• L6 es el lenguaje de todas las palabras que contienen solamente b’s.
• L7 es el lenguaje de todas las palabras que tienen una cantidad par de a’s.
• L8 es el lenguaje de todas las palabras tal que la cantidad de a’s es multiplo
de la cantidad de b’s.
Ejercicio 7. Sea Σ = {a, b, c} un alfabeto, L1 = {b, ab, ac}, L2 = {b, b2 },
L3 = {ba, bc} y , L4 = {bn : n ≥ 0} lenguajes, obtener los lenguajes L1 ∪ L2 ,
∗
L1 ∩ L2 , L1 L2 , LR 2
1 , L3 , L3 L4 y L3 .
Ejercicio 8. Sea Σ = {a, b} un alfabeto, probar que los siguientes lenguajes
son regulares utilizando la definición recursiva de los lenguajes regulares:
1
• L1 = {a, abb, ba}.
• L2 = {aabm : m ≥ 0} el lenguaje de todas las palabras que comienzan con
dos a’s.
• L3 = {an bm : n, m ≥ 0} el lenguaje de todas las palabras que son un
tramo de inicial de a’s seguido de un tramo final de b’s.
• L4 = {bn abm : n, m ≥ 0} el lenguaje de todas las palabras que tienen
exactamente una a.
• L5 = {bα : α ∈ Σ∗ } el lenguaje de todas las cadenas que comienzan con b.
• L6 = {αbaβ : α, β ∈ Σ∗ } el lenguaje de todas las cadenas que contienen
la cadena ba.
• L7 = {bαa : α ∈ Σ∗ } el lenguaje de todas las cadenas que comienzan con
b y terminan con a.
• L8 = {α : |α| es par} el lenguaje de todas las cadenas de longitud par.
• L9 = {α : |α|a es par} el lenguaje de todas las cadenas que tienen una
cantidad par de a’s.
• L10 = {α : aa no ocurre en alpha} es el lenguaje de todas las palabras
que no contienen dos a’s consecutivas.
Ejercicio 9. Para cada uno de los lenguajes Li del ejercicio 7, dar una ex-
presion regular Ei tal que L(Ei ) = Li y chequear que se verifica la igualdad.
Ejercicio 10. Para cada uno de las siguientes expresiones regulares, obtener
el lenguaje regular que denotan:
• E1 = b∗ ab∗
• E2 = b(a + b)∗
• E3 = (a + b)∗ ba(a + b)∗
• E4 = (aa + ab + ba + bb)∗
• E5 = c∗ (b + ac∗ )∗
• E6 = (a + b∗ )a∗ (bc)∗
• E7 = (ϵ + a)∗ (a + b)∗ (ba)∗
• E8 = (a + bb∗ a)∗ b∗
