a. Indique si el lenguaje La = { #xy, x ∈ {0,1}*, y ∈ {0,1}*, |x|0 < |y|1} es regular.
Justifique.
La solucion dice:
R: El lenguaje es regular. Es el lenguaje que tiene al menos un "1" (notar que puede
asumirse que x=ε; en ese caso, basta con que y tenga un "1" para que se cumpla la
condición). La expresión regular que lo denota es (0|1)*1(0|1)*
Pero no me queda claro porque se puede asumir que x=ε, x no debe ser cualquier tira?
hola:
sí, en principio x es cualquiera, pero no es ese el punto de la demostración.
te lo planteo así:
¿{ xy, x ∈ {0,1}*, y ∈ {0,1}*, |x|0 < |y|1} ≤ L ((0|1)*1(0|1)*) ?
esto es claramente cierto porque |y|1 >0, luego debe estar en el conjunto de las tiras con al menos un 1.
¿ L ((0|1)*1(0|1)*) ≤ { xy, x ∈ {0,1}*, y ∈ {0,1}*, |x|0 < |y|1} ?
sí, porque si una tira w pertenece al lenguaje L ((0|1)*1(0|1)*), cumple que existen u y v tales que w= u.1.v
ahora:
w= u.1.v = ε . (u.1.v) porque ε es neutro de la concatenación
y |ε |0 = 0 < 1≤ |u.1.v|1 (tomo x=ε, y=w)
=> w cumple las condiciones del lenguaje.
entonces los conjuntos son iguales.
el "puedo tomar x= ε" es una forma un poco informal de decir lo que está arriba (siempre puedo descomponer a cualquier tira del lenguaje de "al menos un 1" en dos subtiras que cumplen las condiciones, básicamente porque la primera es épsilon y la segunda es la tira misma).
saludos,
d.-
Ahora lo entendí, muchas gracias!