problemas unidad 1y2 (1)

PROBLEMAS UNIDAD 1 Y 2 NOTA: Todos los trabajos podrían exponerse, por tanto deben realizarlos en un formato de exposición (PDF, PPT, etc.). NO SE DEBEN PEGAR IMÁGENES cuyo contenido sean los ejercicios resueltos. SECCIÓN A): 1.- Investigar las ER del lenguaje de programación de su preferencia, al menos para:

Estructuras condicionales

Estructuras de control y/o repetitivas

Identificadores (Variables, Constantes)

Tipos de Datos definidos por los usuarios. 2.- Construir la ER para el comando findstr del Sistema Operativo DOS, al menos para 20 llamadas del comando que sean validas.

∑= { (,), a, b, c, …, z, A, B, C, …, Z, 0, 1, 2, …, 9, :, ., *, -, /, _, “, >, !,@, #, $,%, &, =, +, ¿, ?,

¡} Definiciones regulares: letras= [a|b|c|…|z|A|B|C|…|Z] números= [0|1|2|…|9] signos= [# | $ |%| & | = | + |¿ | ? | ¡ | _ ]

DE= [ “( ( 𝛆 | signos+)números+( 𝛆 | signos+)letras+( 𝛆 | signos+)( 𝛆 | números+( 𝛆 | signos+))

| ( 𝛆 | signos+)números+( 𝛆 | signos+) | signos+ )” ( ( 𝛆 | números+)letras+( 𝛆 | ( ( - | _) ( 𝛆 |

números+)letras+( 𝛆 | números+))+ )| números+) . letras+ ] DE2 = [ ( ( 𝛆 | signos+)números+( 𝛆 | signos+)letras+( 𝛆 | signos+)( 𝛆 | números+( 𝛆 |

signos+)) | ( 𝛆 | signos+)números+( 𝛆 | signos+) | signos+ ) ( ( 𝛆 | números+)letras+( 𝛆 | ( ( - |

_) ( 𝛆 | números+)letras+( 𝛆 | números+))+ )| números+) . letras+ ] DE3 = [“( ( 𝛆 | signos+)números+( 𝛆 | signos+)letras+( 𝛆 | signos+)( 𝛆 | números+( 𝛆 |

signos+)) | ( 𝛆 | signos+)números+( 𝛆 | signos+) | signos+ )” *. letras+] DE4 = [( ( 𝛆 | signos+)números+( 𝛆 | signos+)letras+( 𝛆 | signos+)( 𝛆 | números+( 𝛆 |

signos+)) | ( 𝛆 | signos+)números+( 𝛆 | signos+) | signos+ ) *. letras+] BUSCAR = [ findstr | Findstr | FINDSTR ]

EXT = [ ( ( 𝛆 | números+)letras+( 𝛆 | ( ( - | _) ( 𝛆 | números+)letras+( 𝛆 | números+))+ )| números+) . letras+]

Expresiones regulares:

1. BUSCAR ( DE | DE2 | DE3 | DE4) 2. BUSCAR / (B|b) ( DE | DE2 | DE3 | DE4) 3. BUSCAR / (E|e) ( DE | DE2 | DE3 | DE4) 4. BUSCAR / (L|l) ( DE | DE2 | DE3 | DE4) 5. BUSCAR / (R|r) ( DE | DE2 | DE3 | DE4) 6. BUSCAR / (I|i) ( DE | DE2 | DE3 | DE4) 7. BUSCAR / (X|x) ( DE | DE2 | DE3 | DE4) 8. BUSCAR / (V|v) ( DE | DE2 | DE3 | DE4) 9. BUSCAR / (N|n) ( DE | DE2 | DE3 | DE4) 10. BUSCAR / (M|m) ( DE | DE2 | DE3 | DE4) 11. BUSCAR / (O|o) ( DE | DE2 | DE3 | DE4) 12. BUSCAR / (P|p) ( DE | DE2 | DE3 | DE4) 13. BUSCAR / (offline|OFFline) ( DE | DE2 | DE3 | DE4) 14. BUSCAR / (C|c):( DE | DE2 | DE3 | DE4) 15. BUSCAR ( DE | DE2 | DE3 | DE4) > EXT 16. BUSCAR / (B|b) / (L|l) ( DE | DE2 | DE3 | DE4) 17. BUSCAR / (B|b) / (L|l) / (N|n) ( DE | DE2 | DE3 | DE4) 18. BUSCAR / (E|e) / (L|l) / (N|n) ( DE | DE2 | DE3 | DE4) 19. BUSCAR / (I|i) / (N|n) ( DE | DE2 | DE3 | DE4) 20. BUSCAR / (I|i) / (N|n) / (B|b) ( DE | DE2 | DE3 | DE4)

3.- En fuentes de información FORMALES investigar y resolver 30 ejercicios de ER como los vistos en clase.

1) El conjunto de cadenas del alfabeto {a,b,c} que contienen al menos una a y al menos una b.

a|b|ac*b|c*|bc*a

Describir el lenguaje representado por las siguientes expresiones regulares definidas

sobre el alfabeto Σ={a,b,c}.

2) (aUb)∗c

L (a)= {a} L (b)= {b} L (c)= {c} L (aUb) = L(a) U L (b) = {a, b}

L (aUb)*= (L(a) U L (b))* = {a, b}* = { ε, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba,

bbb, {a,b}n } donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+

3) (aa+)(bb∗) L (a)= {a}

L (a+) = {a,aa,aaa,…,an} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (b)= {b}

L (b*)= { ε , b, bb, bbb, …, bn} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+

L (aa+)= {aa,aaa,aaaa,…,aan} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (bb*)= {b,bb,bbb,…bbn} = L(b+) donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L ((aa+)(bb∗)) = {aab, aabb, aabbb,…, aabn, aaab, aaabb, aaabbb,…, aaabn, aaaab, aaaabb, aaaabbb,…, aaaabn, …, aanb, aanbb, aanbbb, aanbn} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+

4) (aa+)U(bb∗) L (a)= {a}

L (a+) = {a,aa,aaa,…,an} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (aa+)= {aa,aaa,aaaa,…,aan} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (b)= {b}

L (b*)= { ε , b, bb, bbb, …, bn} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+

L (bb*)= {b,bb,bbb,…bbn} = L(b+) donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L ((aa+)U(bb∗)) = { aa,aaa,aaaa,…,aan, b,bb,bbb,…bn} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+

5) a∗b∗c∗ L (a)= {a}

L (a*)= { ε , a, aa, aaa, …, an} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (b)= {b}

L (b*)= { ε , b, bb, bbb, …, bn} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (c)= {c}

L (c*)= { ε , c, cc, ccc, …, cn} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (b∗c∗)= { ε , c, cc, ccc, …, cn, b, bc, bcc, bccc, …, bcn, bb, bbc, bbcc, bbccc, …, bbcn, bbb, bbbc, bbbcc, bbbccc, …, bbbcn, …, bn, bnc, bncc, bnccc, …, bncn} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+

L (a*b∗c∗)= { ε , c, cc, ccc, …, cn, b, bc, bcc, bccc, …, bcn, bb, bbc, bbcc, bbccc, …, bbcn, bbb, bbbc, bbbcc, bbbccc, …, bbbcn, …, bn, bnc, bncc, bnccc, …, bncn, a, ac, acc, accc, …,

acn, ab, abc, abcc, abccc, …, abcn, abb, abbc, abbcc, abbccc, …, abbcn, abbb, abbbc, abbbcc, abbbccc, …, abbbcn, …, abn, abnc, abncc, abnccc, …, abncn, aa, aac, aacc, aaccc, …, aacn, aab, aabc, aabcc, aabccc, …, aabcn, aabb, aabbc, aabbcc, aabbccc, …, aabbcn, aabbb, aabbbc, aabbbcc, aabbbccc, …, aabbbcn, …, aabn, aabnc, aabncc, aabnccc, …, aabncn, aaa, aaac, aaacc, aaaccc, …, aaacn, aaab, aaabc, aaabcc, aaabccc, …, aaabcn, aaabb, aaabbc, aaabbcc, aaabbccc, …, aaabbcn, aaabbb, aaabbbc, aaabbbcc, aaabbbccc, …, aaabbbcn, …, aaabn, aaabnc, aaabncc, aaabnccc, …, aaabncn , an, anc, ancc, anccc, …, ancn, anb, anbc, anbcc, anbccc, …, anbcn, anbb, anbbc, anbbcc, anbbccc, …, anbbcn, anbbb, anbbbc, anbbbcc, anbbbccc, …, anbbbcn, …, anbn, anbnc, anbncc, anbnccc, …, anbncn } donde

𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+

Representar, mediante una expresión regular, los siguientes lenguajes:

6) Considerando que Σ= {a}, el lenguaje formado por cadenas de a’s de longitud par. (a2)+

7) Considerando que Σ= {a}, el lenguaje formado por cadenas de a’s de longitud impar. a(a2)*

8) Considerando que Σ= {a, b}, el lenguaje formado por cadenas de a’s y b´s, de longitud impar, en las que se van alternando los dos sımbolos, es decir, nunca aparece el mismo símbolo dos veces seguidas. Por ejemplo: abababa o bab.

b(ab)+| a(ba)+

Dadas las siguientes expresiones regulares escribir, para cada una de ellas, una

palabra que pertenezca al lenguaje que la expresión representa y otra que no pertenezca a dicho lenguaje.

9) (1*U0*)(1*U0*)(1*U0*) L (0)= {0} L (1)= {1}

L (0*)= { ε, 0, 00, 000, …, 0n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (1*)= { ε, 1, 11, 111, …, 1n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (1*U0*)= { ε, 1, 11, 111, …, 1n, ε, 0, 00, 000, …, 0n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (1*U0*) (1*U0*)= { ε, 1, 11, 111, …, 1n, 0, 00, 000, …, 0n, 1, 11, 111, 1111, …, 11n, 10, 100, 1000, …, 10n, 11, 111, 1111, 11111, …, 111n, 110, 1100, 11000, …, 110n, 111, 1111, 11111,

111111, …, 1111n, 1110, 11100, 111000, …, 1110n, …,1n, 1n1, 1n11, 1n 111, …, 1n1n, 1n0, 1n00, 1n000, …, 1n0n, 0, 01, 011, 0111, …, 01n, 00, 000, 0000, …, 00n, 00, 001, 0011, 00111, …, 001n, 000, 0000, 00000, …, 000n, 000, 0001, 00011, 000111, …, 0001n, 0000, 00000, 000000, …, 0000n, …,0n, 0n1, 0n11, 0n 111, …, 0n1n, 0n0, 0n00, 0n000, …, 0n0n } donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (1*U0*) (1*U0*) (1*U0*)= { ε, 1, 11, 111, …, 1n, 0, 00, 000, …, 0n, 1, 11, 111, 1111, …, 11n, 10, 100, 1000, …, 10n, 11, 111, 1111, 11111, …, 111n, 110, 1100, 11000, …, 110n, 111, 1111,

11111, 111111, …, 1111n, 1110, 11100, 111000, …, 1110n, …,1n, 1n1, 1n11, 1n 111, …, 1n1n, 1n0, 1n00, 1n000, …, 1n0n, 0, 01, 011, 0111, …, 01n, 00, 000, 0000, …, 00n, 00, 001, 0011,

00111, …, 001n, 000, 0000, 00000, …, 000n, 000, 0001, 00011, 000111, …, 0001n, 0000, 00000, 000000, …, 0000n, …,0n, 0n1, 0n11, 0n 111, …, 0n1n, 0n0, 0n00, 0n000, …, 0n0n , …} donde 𝒏 ≥ 𝟒;

𝒏 ∈ ℤ+ (1n0n1n) ∈ L (1*U0*) (1*U0*) (1*U0*)

(1n0n1n0n) L (1*U0*) (1*U0*) (1*U0*)

10) (1U0)*10(1U0)∗ L (0)= {0} L (1)= {1} L (10)= L(1) · L(0) = {10} L (1U0)= {1,0}

L (1U0)*= {1,0}* = { ε, 1,0 ,11, 10, 01, 00, 111, 110, 101, 100, 011, 010, 001, 000, {1,0}n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (10(1U0)*)= {10} · {1,0}* = {10} · { ε, 1,0 11, 10, 01, 00, 111, 110, 101, 100, 011, 010, 001, 000, {1,0}n} = {10,101, 100, 1011, 1010, 1001, 1000, 10111, 10110, 10101, 10100, 10011, 10010, 10001, 10000, 10{1,0}n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+

L ((1U0)*10(1U0)*)= {10,101, 100, 1011, 1010, 1001, 1000, 10111, 10110, 10101, 10100, 10011, 10010, 10001, 10000, 10{1,0}n, 110, 1101, 1100, 11011, 11010, 11001, 11000, 110111, 110110, 110101, 110100, 110011, 110010, 110001, 110000, 110{1,0}n, 010, 0101, 0100, 01011, 01010, 01001, 01000, 010111, 010110, 010101, 010100, 010011, 010010, 010001, 010000, 010{1,0}n, {1,0}m10, {1,0}m101, {1,0}m100, {1,0}m1011, {1,0}m1010, {1,0}m1001, {1,0}m1000, {1,0}m10111, {1,0}m10110, {1,0}m10101, {1,0}m10100, {1,0}m10011, {1,0}m10010, {1,0}m10001, {1,0}m10000, {1,0}m10{1,0}n } donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ y 𝒎 ≥ 𝟐; 𝒎 ∈ ℤ+ 110100 ∈ L ((1U0)*10(1U0)*)

111111 L ((1U0)*10(1U0)*)

11) 1*(0U10*)1* L (0)= {0} L (1)= {1}

L (0*)= { ε ,0, 00, 000,…,0n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (1*)= { ε , 1, 11, 111,…,1n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (10*) = {1,10, 100,1000, …,10n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (0U10*) = {0,1, 10, 100, 1000, …,10n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L ((0U10*)1*) = {0, 01, 011, 0111, …, 01n, 1 , 11, 111, 1111,…,11n, 10 , 101, 1011, 10111,…,101n, 100, 1001, 10011, 100111,…,1001n, 1000, 10001, 100011, 1000111,…,10001n, 10n, 10n1, 10n11, 10n111,…, 10n1n } donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (1*(0U10*)1*) = {0, 01, 011, 0111, …, 01n, 1 , 11, 111, 1111,…,11n, 10 , 101, 1011, 10111,…,101n, 100, 1001, 10011, 100111,…,1001n, 1000, 10001, 100011, 1000111,…,10001n, 10n, 10n1, 10n11, 10n111,…, 10n1n, 10, 101, 1011, 10111, …, 101n, 11 , 111, 1111, 11111,…,111n, 110 , 1101, 11011, 110111,…,1101n, 1100, 11001, 110011, 1100111,…,11001n, 11000, 110001, 1100011, 11000111,…,110001n, 110n, 110n1, 110n11, 110n111,…, 110n1n, …, 1m0, 1m01, 1m011, 1m0111, …, 1m01n, 1m1 , 1m11, 1m111, 1m1111,…, 1m11n, 1m10 , 1m101, 1m1011, 1m10111,…, 1m101n, 1m100, 1m1001, 1m10011, 1m100111,…, 1m1001n, 1m1000, 1m10001, 1m100011, 1m1000111,…, 1m10001n, 1m10n, 1m10n1, 1m10n11, 1m10n111,…, 1m10n1n } donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ y 𝒎 ≥ 𝟐; 𝒎 ∈ ℤ+

111100000 ∈ (1*(0U10*)1*)

000000000 (1*(0U10*)1*)

12) 10*U01* L (0)= {0} L (1)= {1}

L (0*)= { ε , 0, 00, 000,…,0n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (1*)= { ε , 1, 11, 111,…,1n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (01*)= L (0) · L (1*) = {0} · { ε , 1, 11, 111,…,1n} = {0, 01, 011, 0111,…,01n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ℤ+

L (10*)= L (1) · L (0*) = {1} · { ε , 0, 00, 000,…,0n} = {1, 10, 100, 1000,…,10n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ℤ+

L ((10*) U (01*)) = {0, 01, 011, 0111,…,01n, 1, 10, 100, 1000,…,10n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+

0111111 ∈ ((10*) U (01*))

0000000 ((10*) U (01*))

Simplificar las siguientes expresiones regulares:

13) (a U b U ab U ba)∗ Aplicando teorema 10.2

(a U b U ab U ba)∗ 𝞝 ((a U b)*(ab U ba)*)*

14) (a U ε)* Aplicando teorema 1

(a U ε)* 𝞝 (ε U a)* Aplicando teorema 9.5

(ε U a)* 𝞝 a*

15) a(a*a U a*) U a* Aplicando teorema 15.2

a(a*a U a*) U a*𝞝 a(a+ U a*) U a* 𝞝 aa* U a* Aplicando teorema 15

aa* U a* 𝞝 a+ U a* 𝞝 a*

16) (a U b)* ba (a U b)* U a*b* Aplicando teorema 10.3

(a*b*)* ba (a*b*)* U a*b*

Dadas dos expresiones regulares:

α=0* U 1* β=01* U 10* U 1*0 U (0*1)* L (0)= {0} L (1)= {1}

L (0*)= { ε , 0, 00, 000,…,0n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (1*)= { ε , 1, 11, 111,…,1n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+

L (01*)= L (0) · L (1*) = {0} · { ε , 1, 11, 111,…,1n} = {0, 01, 011, 0111,…,01n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ℤ+

L (10*)= L (1) · L (0*) = {1} · { ε , 0, 00, 000,…,0n} = {1, 10, 100, 1000,…,10n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ℤ+

L (1*0)= L (1*) · L (0) = { ε , 1, 11, 111,…,1n} · {0} = {0, 10, 110, 1110, …, 1n0} donde 𝒏 ≥ 𝟒;

𝒏 ∈ ℤ+

L (0*1)= L (0*) · L (1) = { ε , 0, 00, 000,…,0n} } · {1} = {1, 01, 001, 0001, …, 0n1} donde 𝒏 ≥ 𝟒;

𝒏 ∈ ℤ+

L (0*1)*= (L (0*) · L (1))* = { ε ,1, 01, 001, 0001, …, 0n1, 11,101, 1001, 10001, …, 10n1, 011, 0101, 01001, 010001, …, 010n1, 0011, 00101, 001001, 0010001, …,0010n1, 00011, 000101, 0001001, 00010001, …, 00010n1,…, 0n11, 0n101, 0n1001, 0n10001, …, 0n10n1 } donde 𝒏 ≥ 𝟒;

𝒏 ∈ ℤ+

L (α) = { ε , 0, 00, 000,…,0n, 1, 11, 111,…,1n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+

L (β) = {0, 01, 011, 0111,…,01n, 1, 10, 100, 1000,…,10n, 0, 10, 110, 1110, …, 1n0, ε ,1, 01, 001, 0001, …, 0n1, 11,101, 1001, 10001, …, 10n1, 011, 0101, 01001, 010001, …, 010n1, 0011, 00101, 001001, 0010001, …,0010n1, 00011, 000101, 0001001, 00010001, …, 00010n1,…, 0n11, 0n101, 0n1001, 0n10001, …, 0n10n1} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+

Encontrar:

17) Una palabra que pertenezca a α pero no a β 000000000

18) Una palabra que pertenezca a β pero no a α 101

19) Una palabra que pertenezca a α y a β 11

20) Una palabra que no pertenezca a α ni a β 111111000000111111000000111111

Escriba expresiones regulares para los siguientes lenguajes:

21) El conjunto de cadenas formadas por 0s y 1s cuyo décimo símbolo por la derecha sea 1.

0101010101|(101)31(1|0)*|(010)31(1|0)*|1100*|091+|1081(1|0)*|019(1|0)*|0212021201(1|0)* |02120214(1|0)*|02120214(1|0)*|0812(1|0)*|0812(1|0)*|0713(1|0)*|0614(1|0)*|0515(1|0)*| 0416(1|0)*|0317(1|0)*|0218(1|0)*

22) El conjunto de cadenas formadas por 0s y 1s con a lo mucho una pareja de 1s consecutivos.

(01)+|(10)+| (01)*(101)+ (01)*| (01)* (010)+ (01)* |0+110+|(0+110+110+)*|0+11|110+

23) El conjunto de cadenas formadas por ceros y unos cuyo número de ceros es divisible

por cinco.

1*(05)+1*|1*(05)+ 1*(05)+1*|1*01*01*01*01*01*|1*01*041*|1*041*01*|1*021*031*|1*031*021*

24) El conjunto de todas las cadenas formadas por ceros y unos tales que cada pareja de 0s adyacentes aparece antes que cualquier pareja de 1s adyacentes.

00(01)+11|00(10)+11|00(1|0)*11

25) El conjunto de todas las cadenas formadas por ceros y unos que contienen 101 como subcadena.

(01)*101(01)* |(10)*101(10)* |(1|0)*101(1|0)*

26) El conjunto de todas las cadenas formadas por ceros y unos cuyo número de ceros

es divisible por cinco y cuyo número de unos es par.

(12)+(05)+ (12)+| (12)+(05)+ 1*(05)+1* |(12)+0(12)+0(12)+0(12)+0(12)+0(12)+ |(12)+0(12)+04(12)+

|(12)+04(12)+0(12)+ |(12)+02(12)+03(12)+ |(12)+03(12)+02(12)+ |1(05)+1|1(05)+1(05)+ |10104|10410|102103|103102

Proporcione las descripciones informales de los lenguajes correspondientes a las

siguientes expresiones regulares:

27) (1 U ε )(00*1)*0* L (1)= {1}

L (0*) = { ε, 0, 00, 000, …, 0n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (00*1)= {01, 001, 0001, 00001, …, 00n1} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+

L (00*1)*= { ε , 01, 001, 0001, 00001, …, 00n1, 0101, 01001, 010001, 0100001, …, 0100n1, 00101, 001001, 0010001, 00100001, …, 00100n1, 000101, 0001001, 00010001, 000100001, …, 000100n1, 0000101, 00001001, 000010001, 0000100001, …, 0000100n1, …, 00n101, 00n1001, 00n10001, 00n100001, …, 00n100n1} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+

L (1 U ε ) = { 1, ε }

L ((1 U ε ) (00*1)*0*) = { ε , 01, 001, 0001, 00001, …, 00n1, 0101, 01001, 010001, 0100001, …, 0100n1, 00101, 001001, 0010001, 00100001, …, 00100n1, 000101, 0001001, 00010001, 000100001, …, 000100n1, 0000101, 00001001, 000010001, 0000100001, …, 0000100n1, …, 00n101, 00n1001, 00n10001, 00n100001, …, 00n100n1, 1, 101, 1001, 10001, 100001, …, 100n1, 10101, 101001, 1010001, 10100001, …, 10100n1, 100101, 1001001, 10010001, 100100001, …, 100100n1, 1000101, 10001001,100010001, 1000100001, …, 1000100n1, 10000101, 100001001, 1000010001, 10000100001, …, 10000100n1, …, 100n101, 100n1001, 100n10001, 100n100001, …, 100n100n1} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ Lenguaje formado por la cadena vacía, por cadenas de ceros que terminen con 1, cadenas que empiecen con 1 seguido de cero’s y terminen con 1 y cadenas de que empiecen con 1 seguido de ceros, seguido de 1 con cero’s y terminen con 1.

28) (0*1*)*000(0 U 1)* L (0)= {0} L (1)= {1}

L (0*)= { ε , 0, 00, 000,…,0n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (1*)= { ε , 1, 11, 111,…,1n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (0U1)*= {0,1}* = { ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, {0,1}n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (000(0U1)*)= {000, 0000, 0001, 00000, 00001, 00010, 00011, 000000, 000001, 000010, 000011, 000100, 000101, 000110, 000111, 000{0,1}n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+

L (0*1*)= { ε , 1, 11, 111,…,1n, 0, 01, 011, 0111,…,01n, 00, 001, 0011, 00111,…,001n, 000, 0001, 00011, 000111,…,0001n, 0n, 0n1, 0n11, 0n111,…, 0n1n } donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ Todas las cadenas de 0’s, 1’s y combinación de 0’s con 1’2 que tengan como subcadena 000.

29) (0 U 10)*1* L (0) = {0} L (10)= {1} · {0} = {10} L (1)= {1}

L (1*)= { ε , 1, 11, 111,…,1n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (0U10)= {0} U {10} = {0, 10}

L (0U10)*= {0, 10}* = { ε, 0, 10, 00, 010, 100, 1010, 000, 0010, 0100, 01010, 1000, 10010, 10100, 101010, {0, 10}n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+

L (0U10)*1*= { ε , 1, 11, 111,…,1n, 0, 01, 011, 0111,…, 01n, 10, 101, 1011, 10111,…, 101n, 00, 001, 0011, 001111,…, 001n, 010, 0101, 01011, 010111,…, 0101n, 100, 1001, 10011, 100111, …, 1001n,1010, 10101, 101011, 1010111, …, 10101n, 000, 0001, 00011, 000111, …, 0001n, 0010, 00101, 001011, 0010111, …, 00101n, 0100, 01001, 010011, 0100111, …, 01001n, 01010, 010101, 0101011, 01010111, …, 010101n,1000, 10001, 100011, 1000111, …, 10001n,10010, 100101, 1001011, 10010111, …, 100101n,10100, 101001, 1010011, 10100111, …, 101001n, 101010, 1010101, 10101011, 101010111, …, 1010101n,{0, 10}n, {0, 10}n1, {0, 10}n11, {0, 10}n111, …, {0, 10}n1n } donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+

Lenguaje formado por la cadena vacía, combinaciones de 1’s, cadenas que empiecen 0 con combinaciones de 1’s y cadenas que intercalan 1’s con 0’s

30) El conjunto de todas las cadenas con el mismo número de ceros que de unos.

((02)+(12)+)+|((12)+(02)+)+ | (0(02)+1(12)+)+|(1(12)+0(02)+)+

4.- Construir la ER del ciclo for del lenguaje C (ANSI C)

∑= { (,), a, b, c, …, z, A, B, C, …, Z, 0, 1, 2, …, 9, :, ;, %, ,, *, +, -, /, \, =, “, $, &, |, ¿, ?, ¡, !,

{, } } Definiciones regulares: letras= [a|b|c|…|z|A|B|C|…|Z] números= [0|1|2|…|9] ID= [++|--] Signo= [ : | = | ? | ¿ | ¡ | ! | , | . | + | - | * | $ | ; | % ] TiposI= [Int|float|double|long|short|long double] TiposII= [char] Secuencias= [\b|\t|\v|\n] Identificadores= [%d| %c| %s| %f | %e| %g| %u| %o| %x] Relacionales= [<|>|<=|>=|==|!=]

TiposDatos = [TiposI letras+( ε | números+) ( ε | = ( ε | números+)) ( ε | (,((TiposI | ε) letras+( ε |

números+) ( ε | = ( ε | números+)) )+); | float letras+( ε | números+) (ε | = ((ε |

números*.numeros+) | ( ε | números+)) ( ε | (,((float| ε) letras+( ε | números+) (ε | = ((ε |

números*.numeros+) | ( ε | números+)))+);| TiposII letras+( ε | números+) ( ε | (=’letras’) | (=”letras+( ε | números+)”)) ( ε | (,((TiposI | ε) letras+( ε | números+) ( ε | (=’letras’) | (=”letras+( ε | números+)”)))+);] TiposDatosFor = [TiposI letras+( ε | números+) ( ε | = ( ε |letras+ | números+)) ( ε | (,((TiposI | ε)

letras+( ε | números+) ( ε | = ( ε |letras+ | números+)) )+); | float letras+( ε | números+) (ε | = ((ε |

números*.numeros+) | ( ε | números+) | letras+) ( ε | (,((float| ε) letras+( ε | números+) (ε | = ((ε |

números*.numeros+) | ( ε | números+) | letras+))+);] Mostrar= [printf(“Signo*letras+Signo*( ε | Secuencias+)Signo*”); |

printf(“Signo*letras+Signo*Identificadores+( ε | Secuencias+)Signo*”); | printf(“ ε “); | printf(“Signo*letras+Identificadores+( ε | Secuencias+)Signo*”,letras+); | printf(“Signo*letras+Signo*Identificadores+ Signo*letras+Signo* ( ε | Secuencias+)Signo*”); |

printf(“Signo*letras+Signo*Identificadores+ Signo*letras+ Signo*( ε |

Secuencias+)Signo*”,letras+); | printf(“Identificadores+( ε | Secuencias+)”,letras+); ] Capturar =[ scanf(“Identificadores+”, ( ε | &) letras+( ε | (, ( ε | &) letras+)+); SubIf =[if(letras+( ε | números+)Relacionales letras+( ε | números+))( TiposDeDatos| Mostrar+ |

Capturar+ | SubFor) else ( TiposDeDatos| Mostrar+ | Capturar+ | SubFor) | if(letras+( ε |

números+)Relacionales letras+( ε | números+)){( TiposDeDatos| Mostrar+ | Capturar+ |

SubFor)+ }else {( TiposDeDatos| Mostrar+ | Capturar+ | SubFor)+} | if(letras+( ε |

números+)Relacionales letras+( ε | números+))( TiposDeDatos| Mostrar+ | Capturar+ | SubFor) ]

IF =[ if(letras+( ε | números+)Relacionales letras+( ε | números+))( TiposDeDatos| Mostrar+ |

Capturar+ | SubFor | SubIf) else ( TiposDeDatos| Mostrar+ | Capturar+ | SubFor | SubIf) | if(letras+( ε | números+)Relacionales letras+( ε | números+)){( TiposDeDatos| Mostrar+ |

Capturar+ | SubFor | SubIf)+ }else {( TiposDeDatos| Mostrar+ | Capturar+ | SubFor | SubIf)+} | if(letras+( ε | números+)Relacionales letras+( ε | números+))( TiposDeDatos| Mostrar+ | Capturar+ | SubFor | SubIf)

SubFor =[ for (TiposDatosFor(letras+( ε | números+))Relacionales(letras+( ε | números+));( (letras+( ε | números+))ID( ε | (,(letras+( ε | números+))ID)+) | (IDletras+( ε | números+)) ( ε |

(,(IDletras+( ε | números+)))+) )

{ TiposDeDatos| Mostrar+ | Capturar+ | IF } Expresión regular

for (TiposDatosFor(letras+( ε | números+))Relacionales(letras+( ε | números+));( (letras+( ε |

números+))ID( ε | (,(letras+( ε | números+))ID)+) | (IDletras+( ε | números+)) ( ε | (,(IDletras+( ε |

números+)))+) ) { TiposDeDatos| Mostrar+ | Capturar+ | IF | SubFor } SECCIÓN B): Simplificar las siguientes ER:

i. (𝛆 ∪ 𝐚𝐛)∗ Aplicando teorema 9.5

(ε U ab)* Ξ (ab)* De acuerdo con el teorema 9 r*=( ε U r)* Por tanto (ε U ab)* = (ab)*

ii. 𝐚(𝛆 ∪ 𝐚𝐚)∗𝐚 ∪ 𝛆

Aplicando teorema 9.5

a(ε U aa)*a U ε Ξ a(aa)*a U ε Aplicando teorema 11

a(aa)*a U ε Ξ (aa)*aa U ε Aplicando teorema 15.2

(aa)*aa U ε Ξ (aa)+ U ε Aplicando teorema 1

(aa)+ U ε Ξ ε U (aa)+


ε U (aa)+ Ξ (aa)*

iii. (𝐚 ∪ 𝛆)𝐚∗𝐛 Aplicando teorema 9.7

(a U ε)a*b Ξ a*b De acuerdo al teorema 9 (r U ε) r* = r* Por tanto (a U ε) a*b = a*b

iv. (((𝐚∗𝐚)𝐛) ∪ 𝐛)

Aplicando teorema 15.2 (((a*a)b) U b) Ξ ((a+b) U b) Aplicando el teorema 15 r+ = r*r Por tanto (((aa*)b) U b) = ((a+b) U b) = (a+b) U b

v. (𝛆 ∪ 𝐚𝐚)(𝛆 ∪ 𝐚𝐚)∗ Aplicando teorema 9.5

(ε U aa) (ε U aa)* Ξ (ε U aa)(aa)* Aplicando teorema 1

(ε U aa)(aa)* Ξ (aa U ε)(aa)* Aplicando teorema 9.7

(aa U ε)(aa)* Ξ (aa)* Aplicando el teorema 15 r+ = rr* (ε U aa)( ε U aa)* = (ε U aa)+

Teorema 9.15 r*= (ε U r)+

(ε U aa)+ = (aa)+

Ahora aplicando el teorema 9 r*=( ε U r)* (ε U aa)( ε U aa)* = (ε U aa)aa* Teorema 8 r(sUt) = rs U rt

(ε U aa)aa* = (εaa* U aaaa*) Teorema 9 r+ = rr* & Teorema 3 εr = r (aa* U aa+) Y como aa* contiene las cadenas de aa+, tenemos que: (aa* U aa+) = aa*

vi. (𝐚𝐚)∗𝐚 ∪ (𝐚𝐚)∗ Aplicando teorema 8.1

(aa)*a U (aa)* Ξ (aa)* (a U ε) Aplicando el Teorema 8 r(sUt) = rs U rt (aa)*a U (aa)* = (aa)*(a U ε)

vii. (𝐚 ∪ 𝐛)∗𝐚(𝐚 ∪ 𝐛)∗ Aplicando teorema 10.3 (a U b)*a(a U b)* Ξ (a*b*)*a(a*b*)* Aplicando Teorema 10 (r U s)* = (r*s)*r* = r*(sr*)* (a u b)* a (a U b)* = (a*b)* a* a a* (ba*)* Aplicando el teorema 15 rr* = r+ (a*b)* a* a a* (ba*)* = (a*b)* a* a+ (ba*)* Aplicando el teorema 15 r+ r* = r+ (a*b)* a* a+ (ba*)* = (a*b)* a+ (ba*)*

viii. 𝐚(𝛆 ∪ 𝐚𝐚)∗(𝛆 ∪ 𝐚𝐚) ∪ 𝐚


a(ε U aa)*(ε U aa) U a Ξ a(aa)*(ε U aa) U a Aplicando teorema 1

a(aa)*(ε U aa) U a Ξ a(aa)*(aa U ε) U a Aplicando teorema 9.6

a(aa)*(aa U ε) U a Ξ a(aa)* U a Aplicando teorema 2 a(aa)*

ix. ⦰∗ ∪ 𝐚∗ ∪ 𝐛∗ ∪ (𝐚∗ ∪ 𝐛∗)+ Aplicando teorema 5 Ø* U a* U b* U (a* U b*)+ Ξ a* U b* U (a* U b*)+ Aplicando teorema 15.1 a* U b* U (a* U b*)+ Ξ a* U b* U (a* U b*)(a* U b*)*

Aplicando teorema 2 a* U b* U (a* U b*)(a* U b*)* Ξ (a* U b*)(a* U b*)* Aplicando teorema 15.3 (a* U b*)(a* U b*)* Ξ (a* U b*)+

x. ((𝐚∗𝐛∗)∗(𝐛∗𝐚∗)∗)

Aplicando teorema 10 (a U b)*(b U a)* Aplicando el teorema 10 ((a*b*)* (b*a*)*) = (a b)* (b a)*

SECCIÓN C): Interprete en Lenguaje Natural el significado o patrón de cada una de las siguientes ER:

i. (𝟎𝟎)∗ Lenguaje formado por la cadena vacía y las cadenas de 2 0’s consecutivamente. L (0)= {0} L (00)= L (0) · L (0) = {00}

L (00) += (L (0) · L (0))* = {00}* = { ε, 00, 0000, 000000, … , 00n| 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+} Otra manera de explicarlo. Sería todas las potencias desde la 0 hasta n donde 𝒏 ∈ ℤ+ para la cadena '00'

Donde la potencia de una cadena sería como las concatenaciones de la cadena '00' con la cadena '00' las veces que especifique n, pero siendo la cadena vacía ε cuando n=0.

Siendo así entonces.

(00)0 = ε

(00)1 = 00 (00)0 = 00

(00)2 = 00 (00)1 (00)0 = 0000

Y así consecutivamente… Dando como resultado

L*(00) = { ε,00,0000,000000,…}

ii. 𝟎∗𝟏∗ Lenguaje formado por la cadena vacía, por todas las combinaciones de 1’s, de 0’s y concatenación de 0’s con 1’s. L (1)= {1}

L (1*)= { ε, 1, 11, 111,…,1n| 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+} L (0)= {0}

L (0*) = { ε, 0, 00, 000,…,0n| 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+} L (0*1*)= { ε , 1, 11, 111,…,1n, 0, 01, 011, 0111,…,01n, 00, 001, 0011, 00111,…, 001n, 000, 0001, 00011, 000111,…, 0001n,…, 0 n, 0 n1, 0 n11, 0 n111,…,0 n1n }

Otra manera de explicarlo. Sería todas las potencias desde la 0 hasta n donde 𝒏 ∈ ℤ+ para la cadena '0'

Donde la potencia de una cadena sería como las concatenaciones de la cadena '0' con la cadena '0' las veces que especifique n, pero siendo la cadena vacía ε cuando n=0. Todo lo anterior concatenado con

todas las potencias desde la 0 hasta n donde 𝒏 ∈ ℤ+ para la cadena '1'

Donde la potencia de una cadena sería como las concatenaciones de la cadena '1' con la cadena '1' las veces que especifique n, pero siendo la cadena vacía ε cuando n=0.


(0)0 = ε

(0)1 = 0 (0)0 = 0

(0)2 = 0 (0)1 (0)0 = 00

Y así consecutivamente…

Concatenado con

(1)0 = ε

(1)1 = 1 (1)0 = 1

(1)2 = 1 (1)1 (1)0 = 11

Y así consecutivamente… Dando como resultado

L= { εε, ε1,0ε,01,001,0001,0000…1,011,0111,0111…, 000…111..} donde los puntos significan posibles secuencias más del elemento sea 1 o 0.

iii. 𝟏(𝟎│𝟏)∗ Lenguaje formado por la cadena 1, y todas las cadenas de 0’s y 1’s que empiecen con 1. L (0)= {0} L (1)= {1} L (0|1) = {0,1}

L (0|1)* = {0,1}* = { ε, 0,1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, …, {0,1}n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L 1(0|1)* = 11{0,1}* = {1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101,

1110, 1111, …, 1{0,1}n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+

Otra manera de explicarlo. Sería el elemento 1 concatenado con (0|1)* que son todas las potencias

desde la 0 hasta n donde 𝒏 ∈ ℤ+ para la cadena '0' o '1'.

Donde la potencia de una cadena sería las concatenaciones de la cadena '0' o '1' con la cadena '0' o '1' las veces que especifique n, pero siendo la cadena vacía ε cuando n=0.


(0)0 = ε

(1)0 = ε

(0 o 1)1 = ( 0 o 1)(0 o 1)0 = 0 o 1

(0 o 1)2 = 0 o 1 (0 o 1)1 (0 o 1)0 = 00 o 01 o 10 o 11


Y como el elemento 1 se concatena con estas posibles combinaciones, quedaría de la siguiente manera.

L= { εε, ε0, ε1, ε00, ε000, ε0…, ε11, ε111, ε1…,1ε,10,11,100,101,110,111,…}

iv. (𝟎│𝟏)∗𝟎𝟎 Lenguaje formado por todas las cadenas de 0’s, 1’s y combinaciones de 0’s con 1’s que terminen con 00.

L (0)= {0} L (1)= {1} L (0|1) = {0,1}

L (0|1)* = {0,1}* = { ε, 0,1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, …, {0,1}n}

donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (0|1)*00 = {0,1}*00 = {00, 000, 100, 0000, 0100, 1000, 1100, 00000, 00100, 01000, 01100,

10000, 10100, 11000, 11100, …, {0,1}n00} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+

Otra manera de explicarlo. Sería todas las potencias desde la 0 hasta n donde 𝒏 ∈ ℤ+ para la cadena '0' o '1'.



(0)0 = ε

(1)0 = ε

(0 o 1)1 = ( 0 o 1)(0 o 1)0 = 0 o 1

(0 o 1)2 = 0 o 1 (0 o 1)1 (0 o 1)0 = 00 o 01 o 10 o 11


Todos estos elementos y los posibles concatenados con la cadena '00', quedando de la siguiente manera:

L = { ε00,000,100,0000,0100,1000,1100,…}

v. (𝟎│𝟏)∗𝟏𝟎(𝟎│𝟏)∗ Lenguaje formado por todas las combinaciones de 0’s con 1’s. L (0)= {0} L (1)= {1} L (10) = {10} L (0|1) = {0,1}

L (0|1)* = {0,1}* = { ε, 0,1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111,…, {0,1}n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (10(0|1)*) = 10{0,1}* = {10, 100, 101, 1000, 1001, 1010, 1011, 10000, 10001, 10010, 10011,

10100, 10101, 10110, 10111,…, 10{0,1}n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L ((0|1)*10(0|1)*) = {10, 100, 101, 1000, 1001, 1010, 1011, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111, …, 10{0,1}n, 0, 010, 0100, 0101, 01000, 01001, 01010, 01011, 010000, 010001, 010010, 010011, 010100, 010101, 010110, 010111, …, 010{0,1}n , 1, 110, 1100, 1101, 11000, 11001, 11010, 11011, 110000, 110001, 110010, 110011, 110100, 110101, 110110, 110111, …, 110{0,1}n, …, {0,1}m, {0,1}m10, {0,1}m100, {0,1}m101, {0,1}m1000, {0,1}m1001, {0,1}m1010, {0,1}m1011, {0,1}m10000, {0,1}m10001, {0,1}m10010, {0,1}m10011, {0,1}m10100, {0,1}m10101, {0,1}m10110, {0,1}m10111, …, {0,1}m10{0,1}n} donde

𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ y 𝒎 ≥ 𝟐; 𝒎 ∈ ℤ+

Otra manera de explicarlo. Sería todas las potencias desde la 0 hasta n donde 𝒏 ∈ ℤ+ para la cadena '0' o '1'. Donde la potencia de una cadena sería las concatenaciones de la cadena '0' o '1' con la cadena '0' o '1' las veces que especifique n, pero siendo la cadena vacía ε cuando n=0.


(0)0 = ε

(1)0 = ε

(0 o 1)1 = ( 0 o 1)(0 o 1)0 = 0 o 1

(0 o 1)2 = 0 o 1 (0 o 1)1 (0 o 1)0 = 00 o 01 o 10 o 11


Esto concatenado con la cadena '10' para cada elemento resultante.

Y todo lo anterior concatenado nuevamente con todas las potencias desde la 0 hasta n donde para la cadena '0' o '1'. Donde la potencia de una cadena sería las concatenaciones de la cadena '0' o '1' con la cadena '0' o '1' las veces que especifique n, pero siendo la cadena vacía ε cuando n=0.


(0)0 = ε

(1)0 = ε

(0 o 1)1 =( 0 o 1)(0 o 1)0 = 0 o 1

(0 o 1)2 = 0 o 1 (0 o 1)1 (0 o 1)0 = 00 o 01 o 10 o 11

y así consecutivamente…

Lo que nos da como resultado:

L={ ε10ε, ε100,010ε,0100,0101,01000,01001,01010,01011, … ,1100,1101,11000,11001,11010,11011, …}

vi. 𝟏∗𝟎𝟏∗𝟎(𝟎│𝟏)∗ Lenguaje formado por todas las cadenas de combinaciones de 0’s y 1’s que empiecen con 1. L (0)= {0} L (1)= {1} L (0|1) = {0,1}

L (0|1)* = {0,1}* = { ε, 0,1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111,…, {0,1}n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (0(0|1)*) = 0{0,1}* = {0, 00, 01, 000, 001, 010, 011, 0000, 0001, 0010, 0011, 0100, 0101,

0110, 0111,…, {0,1}n} donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ L (1)= {1}

L (1*)= { ε, 1, 11, 111,…,1n| 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+} L (0(1*))= {0, 01, 011, 0111,…,01n| 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+} L (01*0(0|1)*) = {00, 000, 001, 0000, 0001, 0010, 0011, 00000, 00001, 00010, 00011, 00100, 00101, 00110, 00111,…, 0{0,1}n, 010, 0100, 0101, 01000, 01001, 01010, 01011, 010000, 010001, 010010, 010011, 010100, 010101, 010110, 010111,…, 01{0,1}n, …, 01m0, 01m00, 01m01, 01m000, 01m001, 01m010, 01m011, 01m0000, 01m0001, 01m0010, 01m0011, 01m0100,

01m0101, 01m0110, 01m0111,…, 01m{0,1}n } donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ y 𝒎 ≥ 𝟐; 𝒎 ∈ ℤ+ L (1*01*0(0|1)*) = {00, 000, 001, 0000, 0001, 0010, 0011, 00000, 00001, 00010, 00011, 00100, 00101, 00110, 00111,…, 0{0,1}n, 010, 0100, 0101, 01000, 01001, 01010, 01011, 010000, 010001, 010010, 010011, 010100, 010101, 010110, 010111,…, 01{0,1}n, …, 01m0, 01m00, 01m01, 01m000, 01m001, 01m010, 01m011, 01m0000, 01m0001, 01m0010, 01m0011, 01m0100, 01m0101, 01m0110, 01m0111,…, 01m{0,1}n, 100, 1000, 1001, 10000, 10001, 10010, 10011, 100000, 100001, 100010, 100011, 100100, 100101, 100110, 100111,…, 10{0,1}n, 1010, 10100, 10101, 101000, 101001, 101010, 101011, 1010000, 1010001, 1010010, 1010011, 1010100, 1010101, 1010110, 1010111,…, 101{0,1}n, …, 101m0, 101m00, 101m01,

101m000, 101m001, 101m010, 101m011, 101m0000, 101m0001, 101m0010, 101m0011, 101m0100, 101m0101, 101m0110, 101m0111,…, 101m{0,1}n, 1m00, 1m000, 1m001, 1m0000, 1m0001, 1m0010, 1m0011, 1m00000, 1m00001, 1m00010, 1m00011, 1m00100, 1m00101, 1m00110, 1m00111,…, 1m0{0,1}n, 1m010, 1m0100, 1m0101, 1m01000, 1m01001, 1m01010, 1m01011, 1m010000, 1m010001, 1m010010, 1m010011, 1m010100, 1m010101, 1m010110, 1m010111,…, 1m01{0,1}n, …, 1m01m0, 1m01m00, 1m01m01, 1m01m000, 1m01m001, 1m01m010, 1m01m011, 1m01m0000, 1m01m0001, 1m01m0010, 1m01m0011, 1m01m0100, 1m01m0101,

1m01m0110, 1m01m0111,…, 1m01m{0,1}n } donde 𝒏 ≥ 𝟒; 𝒏 ∈ ℤ+ y 𝒎 ≥ 𝟐; 𝒎 ∈ ℤ+ Otra manera de explicarlo. Sería todas las posibles series de la cadena '1' y ε (potencias de la cadena 1), ejemplo { ε,1,11,111,1111,11111…}.

Concatenadas con todas las posibles series de la cadena '01' y ε(potencias de la cadena 01),

ejemplo { ε,01,0101,010101,01010101..}.

Concatenadas con la cadena '0'.

Todo lo anterior concatenado con todas las potencias desde la 0 hasta n donde para la cadena '0' o '1'.



(0)0 = ε

(1)0 = ε

(0 o 1)1 =( 0 o 1)(0 o 1)0 = 0 o 1

(0 o 1)2 = 0 o 1 (0 o 1)1 (0 o 1)0 = 00 o 01 o 10 o 11


Lo que nos da como resultado:

L={ εε0ε,εε00,εε01, εε000.., εε001…, εε0001…, εε0010…, …,

ε010ε,ε0100,ε0101, ε01000.., ε01001…, ε010001…, ε010010…, …,

ε01010ε,ε010100,ε010101…01, ε01…000.., ε01…001…, ε01…0001…, ε01…0010…, …,

101010ε,11010100,111…010101…01, 111…01…000.., 111…01…001…, 111…01…0001…, 111…01…0010…, …, }

SECCIÓN D): Obtener la ER de cada uno de los siguientes casos: 1.- El lenguaje L formado por todas las cadenas de 1’s (unos) y 0’s (ceros) que contenga un número de 0’s divisible entre 3. Solución. 1

1*(03)+1*|1*(03)+1*(03)+1*| (1*021*01*)+| (1*01*021*)+| (1*01*01*01*)+

Con esta solución no sería posible generar cadenas en este fragmento

(1*021*01*)+| (1*01*021*)+ Para cuando necesitemos un número arbitrario de 0´s en el primer cero (01) y un número arbitrario en el segundo cero (02), pero que estos sumados den un número que se divisible entre 3. Para esto hemos implementado la solución 2.

Solución 2:

1*(03)+1*|1*(03)+1*(03)+1*| (1*(02)+1*(0)+1*)+| (1*(0)+1*(02)+1*)+| (1*01*01*01*)+

El problema de esta solución es que acepta cadenas cuya cantidad de 0’s no es divisible entre 3. Solución 3:

1*(03)+1*|1*(03)+1*(03)+1*| (1*(02)n1*(0)n1*)+| (1*(0)n1*(02)n1*)+| (1*01*01*01*)+

Para 𝒏 ∈ ℤ+. Con esta solución acepta cadenas correctas, pero siempre múltiplos de 1 y múltiplos de 2. Con potencias iguales (n). 2.- El lenguaje L formado por todas las cadenas de 1’s y 0’s que contengan a lo mucho dos ceros.

1*|1*01*|1*01*01*

3.- El lenguaje L formado por todas las cadenas de dígitos que representen un 𝒏 ∈ ℤ+ base

10 correctamente escrito. Definición regular: Digito= [1|2|3|4|5|6|7|8|9] Digito2= [0|1|2|3|4|5|6|7|8|9] Digito+·Digito2* 4.- El lenguaje L formado por todas las cadenas de 1’s y 0’s cuya longitud es múltiplo de 5.

(05)+|(15)+|(0515)+|(1505)+|(019)+|(190)+|(0218)+|(1802)+|(0317)+|(1703)+| (0416)+|(1406)+|

(0812)+|(1208)+|(0713)+|(1307)+|(0614)+|(1406)+|(01010)+|(10101)+|(1302)+|(0213)+| (1203)+|

(0312)+| (1*)5 (0*)5 (1*)5

5.- El lenguaje L formado por todas las cadenas de 1’s y 0’s donde se cumpla para todas las

cadenas que │𝒘│ ≤ 𝟓.

0n|1n|01m|1m0|0m1|10m|12012|101|010|02102|1031|0130|1021|0120

𝒏 ≥ 𝟓; 𝒏 ∈ ℤ+ y 𝒎 ≥ 𝟒; 𝒎 ∈ ℤ+

problemas unidad 1y2 (1)

Documents