Ejercicios Autómatas

EJERCICIOS DE EXPRESIONES
REGULARES Y AUTOMATAS
1.α + (β + γ) = (α + β) + γ
2.α + β = β + α
3.α + Ø = α
4.α + α = α
5.α · λ = α
6.α · Ø = Ø
7.α · (β · γ) = (α · β) · γ
8.α · (β + γ) = αβ + αγ, (β + γ) · α = βα + γα

EJERCICIOS DE EXPRESIONES
REGULARES Y AUTOMATAS
9.λ* = λ
1O.Ø* = λ
11.α · α* = α* · α
12.α* = α* · α* = (α*)*
13.α* = λ + α · α*
14.(α + β)* = (α* + β*)*
15.(α + β)* = (α* · β*)* =(α* · β)* · α*
16.α · (β · α)* = (α · β)* · α
17. Si λЄ L(a), entonces a+λ=a

EJERCICIOS DE EXPRESIONES
REGULARES Y AUTOMATAS
Ejemplo
Sean § = {0, 1} y
L, M dos lenguajes sobre § dados por
L ={1, 10} y M = {1, 01} entonces
LM = {11, 101, 1001}.
Mientras que ML = {11, 110, 001, 0110}.

EJERCICIOS DE EXPRESIONES
REGULARES Y AUTOMATAS
Ejemplo
Dado V = {0; 1} y la ER α = 0*10*,
tenemos que:
L(0*10*) =L(0*) L(1) L(0*)
= (L(0))* L(1) (L(0))*
= {0}*.{1}.{0}*={0n10m | n, m  0}

EJERCICIOS DE EXPRESIONES
REGULARES Y AUTOMATAS
Ejemplo
Si ∑ = {a, b, c} entonces
∑2 = {aa, ab, ac, ba, bb, bc, ca, cb, cc}

Ejemplo
Sea § = {0, 1} y L = {01, 1}, entonces
L3 = {010101, 01011, 01101, 0111, 10101,
1011, 1101, 111}

EJERCICIOS DE EXPRESIONES
REGULARES Y AUTOMATAS
Ejemplo
Obtener una ER para el lenguaje enel
alfabeto {a, b, c} en que las palabras
contienen exactamente una vez dos b
contiguas.
Por ejemplo, las palabras aabb, babba,
pertenecen al lenguaje, pero no aaba,
abbba ni bbabb.

EJERCICIOS DE EXPRESIONES
REGULARES Y AUTOMATAS
Ejemplo
Dado el alfabeto Σ = {a, b, c},
(a U b*)a*(bc)*
Es una expresión regular que representa al
lenguaje

({a} U {b}*) · {a}* · {bc}*

EJERCICIOS DE EXPRESIONESREGULARES Y AUTOMATAS
Ejemplo
Dada la expresión regular (a | b)*, el
lenguaje que denota es el que puede formar
con todas las cadenas compuestas por a y b
incluida la cadena vacía. Algunos ejemplos
de sentencias de estos lenguajes son:
λ, aaa, bbb, aba, abaaa, abbaa.

EJERCICIOS DE EXPRESIONES
REGULARES Y AUTOMATAS
Ejemplo
Sea el vocabulario {1,2,3}, la expresión
regular (1|2)*3 indica el conjuntode todas
las cadenas formada por los símbolos 1 y 2,
sucediéndose cualquier Nº de veces (y en
cualquier orden), y siempre terminando la
cadena en el símbolo 3.
3, 13, 123, 11113, 22213, 23, 223, 113,
121211223, 111212213.

EJERCICIOS DE EXPRESIONES
REGULARES Y AUTOMATAS
Ejemplo
Dado el alfabeto Σ = {a, b},
(λ U a)*(a U b)*(ba)*
Es una expresión regular que representa al
lenguaje
({λ} U {a})* ·{a, b}* · {ba}*.

EJERCICIOS DE EXPRESIONES
REGULARES Y AUTOMATAS
Para resolver este problema, expresamos primero
la estructura de la ER de la manera siguiente:
< contexto1 > bb < contexto2 >
El lenguaje de < contexto1 > comprende a las
palabras que no tienen bb y además no terminan
en b. 4 Esto es equivalente a decir que toda b está
seguida de una a o una c. Esto quiere decir que la
ER de estecontexto va ser de la forma:
(. . . b(a + c) . . .)

EJERCICIOS DE EXPRESIONES
REGULARES Y AUTOMATAS
Similarmente se puede obtener la expresión
para < contexto2 >, que es
((a + c ) b)*,
Por lo que finalmente la ER del problema
es:
(b(a + c))*bb((a + c)b)*

EJERCICIOS DE EXPRESIONES
REGULARES Y AUTOMATAS
Ejemplo
Sea la ER t = a + bc + b3a.
Cuál es el lenguaje descrito por t?
Que expresión regularcorresponde al
lenguaje universal sobre el alfabeto {a, b, c?

EJERCICIOS DE EXPRESIONES
REGULARES Y AUTOMATAS
En primer lugar, esta no es estrictamente
hablando una ER, ya que no se permite b3a:
Sin embargo, aceptamos como válida la expresión
a + bc + b3a, como una simplificación de la ER
a+bc+bbba.
En ese caso, L(t) ={a; bc; bbba}, que como vemos
es un lenguaje finito sobre el alfabeto {a; b;c}.
La ER que describe el lenguaje universal sobre
este alfabeto es
(a + b + c)*

EJERCICIOS DE EXPRESIONES
REGULARES Y AUTOMATAS
Ejemplo
Simplificar la ER t = a + a (b + aa) (b*aa)* b* + a (aa + b)*.
Aplicando las propiedades de las expresiones regulares,
podemos obtener una ER equivalente con tan solo 4
operadores:
a + a (b + aa) (b*aa)* b* +a (aa + b)* (Propiedad 15)
a + a (b + aa) (b + aa)*...