PROBLEMAS UNIDAD 1 Y 2

NOTA: Todos los trabajos podran exponerse, por tanto deben realizarlos en un formato de
exposicin (PDF, PPT, etc.). NO SE DEBEN PEGAR IMGENES cuyo contenido sean los
ejercicios resueltos.
SECCIN A):
1.- Investigar las ER del lenguaje de programacin 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]
nmeros= [0|1|2||9]
signos= [# | $ |%| & | = | + | | ? | | _ ]

[ ( ( | signos+)nmeros+( | signos+)letras+( | signos+)( | nmeros+( | signos+))

| ( | signos+)nmeros+( | signos+) | signos+ ) ( ( | nmeros+)letras+( | ( ( - | _) ( |
nmeros+)letras+( | nmeros+))+ )| nmeros+) . letras+ ]
DE2 = [ ( ( | signos+)nmeros+( | signos+)letras+( | signos+)( | nmeros+( |
signos+)) | ( | signos+)nmeros+( | signos+) | signos+ ) ( ( | nmeros+)letras+( | ( ( - |
_) ( | nmeros+)letras+( | nmeros+))+ )| nmeros+) . letras+ ]
DE3 = [( ( | signos+)nmeros+( | signos+)letras+( | signos+)( | nmeros+( |
signos+)) | ( | signos+)nmeros+( | signos+) | signos+ ) *. letras+]
DE4 = [( ( | signos+)nmeros+( | signos+)letras+( | signos+)( | nmeros+( |
signos+)) | ( | signos+)nmeros+( | signos+) | signos+ ) *. letras+]
DE=

BUSCAR = [ findstr | Findstr | FINDSTR ]

[ ( ( | nmeros+)letras+( | ( ( - | _) ( | nmeros+)letras+( | nmeros+))+ )|

nmeros+) . letras+]
EXT =

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 informacin 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) abc
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 (bc)= { , 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*bc)= { , 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 expresin regular, los siguientes lenguajes:

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

7) Considerando que = {a}, el lenguaje formado por cadenas de as de longitud impar.

a(a2)*

8) Considerando que = {a, b}, el lenguaje formado por cadenas de as y bs, de longitud
impar, en las que se van alternando los dos smbolos, es decir, nunca aparece el
mismo smbolo 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 expresin 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,,110001 n, 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 dcimo smbolo por la derecha sea
1.

| | |
|
|
|0 1 0 1 (1|0)*|0 1 0 1 (1|0)*|0 1 (1|0)*|0 1 (1|0)*|0 1 (1|0)*|0 1 (1|0)*|0 1 (1|0)*|
0 1 (1|0)*|0 1 (1|0)*|0 1 (1|0)*

0101010101 (101)31(1|0)* (010)31(1|0)* 1100* 091+ 1081(1|0)* 019(1|0)* 0212021201(1|0)*

2 2 2 4

4 6

2 2 2 4

3 7

2 8

8 2

8 2

7 3

6 4

5 5

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 nmero 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 nmero de ceros
es divisible por cinco y cuyo nmero 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)+

|(1 ) 0 (1 ) 0(1 ) |(1 ) 0 (1 ) 0 (1 ) |(1 ) 0 (1 ) 0 (1 ) |1(0 ) 1|1(0 ) 1(0 )

|1010 |10 10|10 10 |10 10
2 + 4

2 +

2 +

2 + 2

2 + 3

2 +

2 + 3

2 + 2

2 +

5 +

5 +

5 +

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, , 0000100 n1, , 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, , 00100 n1, 000101, 0001001, 00010001,
000100001, , 000100n1, 0000101, 00001001, 000010001, 0000100001, , 0000100 n1, ,
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 vaca, por cadenas de ceros que terminen con 1, cadenas
que empiecen con 1 seguido de ceros y terminen con 1 y cadenas de que empiecen con 1
seguido de ceros, seguido de 1 con ceros 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 0s, 1s y combinacin de 0s con 12 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 vaca, combinaciones de 1s, cadenas que empiecen 0 con
combinaciones de 1s y cadenas que intercalan 1s con 0s

30) El conjunto de todas las cadenas con el mismo nmero 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]
nmeros= [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+( | nmeros+) ( | = ( | nmeros+)) ( | ( ((TiposI | ) letras+( |

; | float letras+( | nmeros+) ( | = (( |

nmeros*.numeros+) | ( | nmeros+)) ( | (,((float| ) letras+( | nmeros+) ( | = (( |
nmeros*.numeros+) | ( | nmeros+)))+);| TiposII letras+( | nmeros+) ( | (=letras) |
(=letras+( | nmeros+))) ( | (,((TiposI | ) letras+( | nmeros+) ( | (=letras) |
(=letras+( | nmeros+))))+);]
TiposDatosFor = [TiposI letras+( | nmeros+) ( | = ( |letras+ | nmeros+)) ( | (,((TiposI | )
letras+( | nmeros+) ( | = ( |letras+ | nmeros+)) )+); | float letras+( | nmeros+) ( | = (( |
nmeros*.numeros+) | ( | nmeros+) | letras+) ( | (,((float| ) letras+( | nmeros+) ( | = (( |
nmeros*.numeros+) | ( | nmeros+) | letras+))+);]
nmeros+) ( | = ( | nmeros+)) )+)

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+( | nmeros+)Relacionales letras+( | nmeros+))( TiposDeDatos| Mostrar+ |

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

nmeros+)Relacionales letras+( | nmeros+)){( TiposDeDatos| Mostrar+ | Capturar+ |

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

nmeros+)Relacionales letras+( | nmeros+))( TiposDeDatos| Mostrar+ | Capturar+ | SubFor)
]
IF =[ if(letras+( | nmeros+)Relacionales letras+( | nmeros+))( TiposDeDatos| Mostrar+ |
Capturar+ | SubFor | SubIf) else ( TiposDeDatos| Mostrar+ | Capturar+ | SubFor | SubIf)
if(letras+( | nmeros+)Relacionales letras+( | nmeros+)){( TiposDeDatos| Mostrar+ |

Capturar+ | SubFor | SubIf)+ }else {( TiposDeDatos| Mostrar+ | Capturar+ | SubFor | SubIf)+}

if(letras+( | nmeros+)Relacionales letras+( | nmeros+))( TiposDeDatos| Mostrar+ |
Capturar+ | SubFor | SubIf)

SubFor =[ for (TiposDatosFor(letras+( | nmeros+))Relacionales(letras+( | nmeros+)) (

(letras+( | nmeros+))ID( | ( (letras+( | nmeros+))ID)+) | (IDletras+( | nmeros+)) ( |

( (IDletras+( | nmeros+)))+) )
{ TiposDeDatos| Mostrar+ | Capturar+ | IF }
Expresin regular

for (TiposDatosFor(letras+( | nmeros+))Relacionales(letras+( | nmeros+)) ( (letras+( |

nmeros+))ID( | ( (letras+( | nmeros+))ID)+) | (IDletras+( | nmeros+)) ( | ( (IDletras+( |

nmeros+)))+) )
{ TiposDeDatos| Mostrar+ | Capturar+ | IF | SubFor }

SECCIN B):
Simplificar las siguientes ER:

i. ( )
Aplicando teorema 9.5
( U ab)* (ab)*
De acuerdo con el teorema 9
Por tanto ( U ab)* = (ab)*

r*=( U r)*

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)+
Aplicando teorema 9.16
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
( U aa)( U aa)* = ( U aa)aa*
Teorema 8 r(sUt) = rs U rt

r*=( U r)*

( 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. ( ) ( )
Aplicando teorema 9.5
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)*

SECCIN C):
Interprete en Lenguaje Natural el significado o patrn de cada una de las siguientes ER:

i. ()
Lenguaje formado por la cadena vaca y las cadenas de 2 0s 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. Sera todas las potencias desde la 0 hasta n donde + para la cadena
'00'
Donde la potencia de una cadena sera como las concatenaciones de la cadena '00' con la cadena '00' las
veces que especifique n, pero siendo la cadena vaca 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 vaca, por todas las combinaciones de 1s, de 0s y
concatenacin de 0s con 1s.
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. Sera todas las potencias desde la 0 hasta n donde + para la cadena '0'
Donde la potencia de una cadena sera como las concatenaciones de la cadena '0' con la cadena '0' las
veces que especifique n, pero siendo la cadena vaca 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 sera como las concatenaciones de la cadena '1' con la cadena '1' las
veces que especifique n, pero siendo la cadena vaca cuando n=0.
Siendo as entonces.
(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,00001,011,0111,0111, 000111..} donde los puntos significan posibles
secuencias ms del elemento sea 1 o 0.

iii. ()
Lenguaje formado por la cadena 1, y todas las cadenas de 0s y 1s 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. Sera 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 sera las concatenaciones de la cadena '0' o '1' con la cadena '0' o '1' las
veces que especifique n, pero siendo la cadena vaca cuando n=0.
Siendo as entonces.
(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
Y como el elemento 1 se concatena con estas posibles combinaciones, quedara 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 0s, 1s y combinaciones de 0s con 1s 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. Sera todas las potencias desde la 0 hasta n donde + para la cadena '0'
o '1'.
Donde la potencia de una cadena sera las concatenaciones de la cadena '0' o '1' con la cadena '0' o '1' las
veces que especifique n, pero siendo la cadena vaca cuando n=0.
Siendo as entonces.
(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
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 0s con 1s.
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. Sera todas las potencias desde la 0 hasta n donde + para la cadena '0'
o '1'.
Donde la potencia de una cadena sera las concatenaciones de la cadena '0' o '1' con la cadena '0' o '1' las
veces que especifique n, pero siendo la cadena vaca cuando n=0.

Siendo as entonces.
(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
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 sera las concatenaciones de la cadena '0' o '1' con
la cadena '0' o '1' las veces que especifique n, pero siendo la cadena vaca cuando n=0.
Siendo as entonces.
(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 0s y 1s 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. Sera 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'.
Donde la potencia de una cadena sera las concatenaciones de la cadena '0' o '1' con la cadena '0' o '1' las
veces que especifique n, pero siendo la cadena vaca cuando n=0.
Siendo as entonces.
(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={ 0,00,01, 000.., 001, 0001, 0010, ,
010,0100,0101, 01000.., 01001, 010001, 010010, ,
01010,010100,01010101, 01000.., 01001, 010001, 010010, ,
101010,11010100,11101010101, 11101000.., 11101001, 111010001,
111010010, , }

SECCIN D):
Obtener la ER de cada uno de los siguientes casos:
1.- El lenguaje L formado por todas las cadenas de 1s (unos) y 0s (ceros) que contenga un
nmero de 0s divisible entre 3.
Solucin. 1

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

Con esta solucin no sera posible generar cadenas en este fragmento

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

Solucin 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 solucin es que acepta cadenas cuya cantidad de 0s no es divisible
entre 3.
Solucin 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 solucin acepta cadenas correctas, pero siempre mltiplos de 1 y
mltiplos de 2. Con potencias iguales (n).
2.- El lenguaje L formado por todas las cadenas de 1s y 0s que contengan a lo mucho dos
ceros.

1* 1*01* 1*01*01*
3.- El lenguaje L formado por todas las cadenas de dgitos que representen un + base
10 correctamente escrito.
Definicin 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 1s y 0s cuya longitud es mltiplo de 5.

| | | | | | | | | |
| |
(0 1 ) |(1 0 ) |(0 1 ) |(1 0 ) |(0 1 ) |(1 0 ) |(01010) |(10101) |(1 0 ) |(0 1 ) | (1 0 ) |
(0 1 ) | (1*) (0*) (1*)
(05)+ (15)+ (0515)+ (1505)+ (019)+ (190)+ (0218)+ (1802)+ (0317)+ (1703)+ (0416)+ (1406)+
8 2 +

2 8 +

3 2 +

7 3 +

3 7 +

6 4 +

4 6 +

3 2 +

2 3 +

2 3 +

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

| | | | | |

| | |

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