Faustino Benjamn Rivera Lpez

Matricula: 76613
Grupo: CC18
Materia: Introduccin a la Teora de las Ciencias Computacionales
Profesor: Dra. Mara Claudia Denicia Carral
Bloque 2, Actividad 1.
Oaxaca de Jurez Oaxaca. 16 de marzo del 2016.
Objetivo:
Construir autmatas de nmeros binarios, los cuales son la base de operacin de las
computadoras para realizar todos los procesos que permiten su funcionamiento.
Instrucciones:
Analiza el siguiente planteamiento y realiza lo que se solicita:
Las computadoras entienden el lenguaje binario, por lo tanto, es necesario tener
conocimientos sobre cmo procesar cadenas de nmeros binarios, por ello:
1. Construye un autmata para reconocer cadenas, cuyo nmero de ceros sea
divisible entre 3 y el nmero de unos sea divisible entre 5.
2. Posteriormente, convierta el autmata obtenido en una expresin regular. Prueba
tus resultados con las siguientes cadenas 00011111 y 00001111100

Introduccion:
Concepto: El trmino determinista hace referencia al hecho de que para cada
entrada slo existe uno y slo un estado al que el autmata puede hacer la
transicin a partir de su estado actual. Por el contrario, un autmata finito no
determinista, puede estar en varios estados a la vez. El trmino autmata finito
hace referencia a la variedad determinista, aunque normalmente utilizaremos el
trmino determinista o la abreviatura AFD, con el fin de recordar al lector el tipo
de autmata del que estamos hablando.
Un autmata finito determinista consta de:
1. Un conjunto finito de estados, a menudo designado como Q.
2. Un conjunto finito de smbolos de entrada, a menudo designado como .

3. Una funcin de transicin que toma como argumentos un estado y un

smbolo de entrada y devuelve un estado. La funcin de transicin se designa
habitualmente como . En nuestra representacin grfica informal del
autmata, se ha representa mediante arcos entre los estados y las etiquetas
sobre los arcos. Si q es un estado y a es un smbolo de entrada, entonces (q,a)
es el estado p tal que existe un arco etiquetado a que va desde q hasta p.2
4. Un estado inicial, uno de los estados de Q.
5. Un conjunto de estados finales o de aceptacin F. El conjunto F es un
subconjunto de Q.
A menudo haremos referencia a un autmata finito determinista mediante su
acrnimo: AFD. La representacin ms sucinta de un AFD consiste en un listado
de los cinco componentes anteriores. Normalmente, en las demostraciones,
definiremos un AFD utilizando la notacin de quntupla siguiente:
A = (Q, , ,q0,F) (Hopcroft, Motwani, & Ullman, 2007)

DESARROLLO:
Como resolvermos este automata, primero que nada nos plateamos los ejercicios en
dos partes diferentes:
1. Un autmata para reconocer cadenas, cuyo nmero de ceros sea divisible entre
3
2. Un automata para reconocer cadenas, cuyo numero de unos sea divisible entre 5
Al ver estas dos expresiones encontramos que en si son dos automatas, si los tomamos
de esa manera podremos resolverlos de manera independiente y asi de esa manera
obtener al final un automata que sea un conjunto de estados donde estos dos se
encuentren.
Asi tambien definimos que si son automatas de este tipo cada uno de ellos esperaria
cadenas de caracteres donde solo se use un lenguaje, que contenga un solo simbolo
={0} o ={1}.
Resolvamos entonces de manera independiente cada uno de ellos y vamos dando con el
automata final.

La respuesta al primer automata seria lo siguiente, en donde solo acepta cadenas de 0 y

si la cadena el resto de la division es diferente de 0 no se acepta, en este caso se
generan 3 estados ya que se busca que sea divisible entre 3 sin resto de la division.
Por lo tanto el siguiente resultado para el siguiente automata seria uno donde sea divisible
entre 5, por lo tanto seran necesarios 5 estados.
En este caso se generan tantos estados como requiera la division por lo tanto serian 5
estados, si hacemos las pruebas solo aceptaria un cadenas donde en lenguaje sea
compuesto por el simbolo 1 y de esta manera solo si el resultado de la division entre 5
sea 0.

Ahora al realizar la interseccion de estos dos automatas tendremos que conjuntar todos
sus estados para que de esa manera nos de cmo resultado el estado que requerimos
El resultado seria algo asi como lo vemos en esta tabla:
Q5
Q6
Q7
Q8
Q9

Q0

Q1

Q2

Q5q0
Q6q0
Q7q0
Q8q0
Q9q0

Q5q1
Q6q1
Q7q0
Q8q1
Q9q1

Q5q2
Q6q2
Q7q2
Q8q2
Q9q2

Por lo tanto obtendremos 15 estados, en los cuales cada uno tendra 4 funciones,
recibiendo un 1 y un 0 y dando un 1 y un 0.

PARTE

Conjunto

finito

de

estados.:

Q={q0,q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12,q13,q14}
En este primer caso donde el estado inicial y el estado final son el mismo solo tenemos 15
estados, si agregamos un estado adicional para poder obtener la expresion regular
tendriamos 16 estados con un estado inicial diferente del estado final.
Algo asi:

Q={q0,q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12,q13,q14,q15}

Parte 2 Conjunto finito de simbolos de entrada o lenguaje de los

automatas: ={0,1} Para los dos casos seria el mismo lenguaje. Y las mismas
cadenas *={10,01,110,001,11100,}

Parte 3 Tabla de transiciones:

Pongo los dos casos en donde se plantean los dos automatas con y sin estados finales
separados.
Sin estado final e inicial separado:

Tablas de Transiciones:

q0
q1
q2
q3
q4
q5
q6
q7
q8
q9
q10
q11
q12
q13
q14

q1
q2
*q0
q4
q5
q3
q7
q8
q6
q10
q11
q9
q13
q14
q12

q3
q4
q5
q6
q7
q8
q9
q10
q11
q12
q13
q14
*q0
q1
q2

Con el estado final e inicial separado:

Tablas de Transiciones:

q0
q1
q2
q3
q4
q5
q6
q7

q1
q2
*q15
q4
q5
q3
q7
q8

q3
q4
q5
q6
q7
q8
q9
q10

q8
q9
q10
q11
q12
q13
q14
*q15

q6
q10
q11
q9
q13
q14
q12
q1

q11
q12
q13
q14
*q15
q1
q2
q3

Parte 4 Estados Iniciales:

En los dos casos tenemos el estado inicial q0, en el primer caso
cumple funcion de inicial y final.
Parte 5: Estados finales o de aceptacion.
En el primer caso q0 es el estado final, en el segundo caso q15 es el
estado final.
Caso 1: F Q = {q0}
Caso 2: F Q = {q15}

Diagrama de transiciones de el AFD:

Caso 1:

Caso 2:

Prueba de cadenas:

Caso 1:

Caso 2:

Conclusion y Expresion regular.

En este caso, me hizo recordar que este tipo de grafos parecieran la forma de
comunicacin dentro de las telecomunicaciones, permitiendo la entrada y salida solo de
ciertos datos, por medio de una evaluacion continua de los datos a transmitir, por ejemplo
se usa un automata en la evaluacion de los paquetes de envio y recepcion, para verificar
si estos son enviados y recibidos completamente.
Tomaremos en segundo caso planteado para realizar la expresion regular ya que JFLAP
pide que se separe El estado inicial del estado de Aceptacion.
Coloco la expresion regular correspondiente.

(000+(((11+(001+(01+10)0)(000)*01)1+((001+(01+10)0)(000)*1+
((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*01)1+
(((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)0)(000)*1+(((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)1+((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)
(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*001+((11+(001+(01+10)0)(000)*01)1+
((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)0)(000)*01)0)0)(000)*01)1+((((01+10)1+(001+(01+10)0)
(000)*001+(11+(001+(01+10)0)(000)*01)0)1+((001+(01+10)0)(000)*1+
((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*001+
((11+(001+(01+10)0)(000)*01)1+((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)
(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*01)0)1+(((001+(01+10)0)(000)*1+
((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*1+
(((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)1+((001+(01+10)0)
(000)*1+((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)
(000)*001+((11+(001+(01+10)0)(000)*01)1+((001+(01+10)0)(000)*1+
((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*01)0)0)
(000)*001+(((11+(001+(01+10)0)(000)*01)1+((001+(01+10)0)(000)*1+
((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*01)1+
(((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)0)(000)*1+(((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)1+((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)
(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*001+((11+(001+(01+10)0)(000)*01)1+
((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)0)(000)*01)0)0)(000)*01)0)(((111+(101+110)(000)*001+(101+110)(000)*010)1+
((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*001+
((101+110)(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)
(000)*010)0)(000)*01)0)1+(((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)
(000)*010)0)(000)*1+((111+(101+110)(000)*001+(101+110)(000)*010)1+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)
(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*01)0)0)(000)*001+(((101+110)(000)*011+((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*01)1+(((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*1+((111+(101+110)(000)*001+(101+110)

(000)*010)1+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*001+((101+110)(000)*011+((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*01)0)0)(000)*01)0)*(100+(((101+110)
(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*01)1+(((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*1+((111+(101+110)(000)*001+(101+110)(000)*010)1+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)
(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*01)0)0)(000)*01)1)+((((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)
(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*1+(((01+10)1+(001+(01+10)0)
(000)*001+(11+(001+(01+10)0)(000)*01)0)1+((001+(01+10)0)(000)*1+
((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*001+
((11+(001+(01+10)0)(000)*01)1+((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)
(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*01)0)0)(000)*1+
((((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)1+((001+(01+10)0)
(000)*1+((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)
(000)*001+((11+(001+(01+10)0)(000)*01)1+((001+(01+10)0)(000)*1+
((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*01)0)1+
(((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)0)(000)*1+(((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)1+((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)
(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*001+((11+(001+(01+10)0)(000)*01)1+
((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)0)(000)*01)0)0)(000)*001+(((11+(001+(01+10)0)(000)*01)1+((001+(01+10)0)
(000)*1+((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)
(000)*01)1+(((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)
(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*1+(((01+10)1+(001+(01+10)0)
(000)*001+(11+(001+(01+10)0)(000)*01)0)1+((001+(01+10)0)(000)*1+
((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*001+
((11+(001+(01+10)0)(000)*01)1+((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)
(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*01)0)0)(000)*01)0)(((111+(101+110)
(000)*001+(101+110)(000)*010)1+((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)(000)*011+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*01)0)1+(((101+110)

(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*1+((111+(101+110)
(000)*001+(101+110)(000)*010)1+((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)(000)*011+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*01)0)0)(000)*001+
(((101+110)(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)
(000)*010)0)(000)*01)1+(((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)
(000)*010)0)(000)*1+((111+(101+110)(000)*001+(101+110)(000)*010)1+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)
(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*01)0)0)(000)*01)0)*(0+(((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)
(000)*010)0)(000)*1+((111+(101+110)(000)*001+(101+110)(000)*010)1+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)
(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*01)0)0)(000)*1))(((11(000)*1+(11(000)*001+11(000)*010)0)(000)*1+
((11(000)*001+11(000)*010)1+(11(000)*1+(11(000)*001+11(000)*010)0)
(000)*001+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)0)0)(000)*1+
(((11(000)*001+11(000)*010)1+(11(000)*1+(11(000)*001+11(000)*010)0)
(000)*001+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)0)1+
((11(000)*1+(11(000)*001+11(000)*010)0)(000)*1+
((11(000)*001+11(000)*010)1+(11(000)*1+(11(000)*001+11(000)*010)0)
(000)*001+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)0)0)
(000)*001+(0+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)1+
((11(000)*1+(11(000)*001+11(000)*010)0)(000)*1+
((11(000)*001+11(000)*010)1+(11(000)*1+(11(000)*001+11(000)*010)0)
(000)*001+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)0)0)
(000)*01)0)(((111+(101+110)(000)*001+(101+110)(000)*010)1+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)
(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*01)0)1+(((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*1+((111+(101+110)(000)*001+(101+110)(000)*010)1+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)
(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*01)0)0)(000)*001+(((101+110)(000)*011+((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*01)1+(((101+110)(000)*1+(111+(101+110)

(000)*001+(101+110)(000)*010)0)(000)*1+((111+(101+110)(000)*001+(101+110)
(000)*010)1+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*001+((101+110)(000)*011+((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*01)0)0)(000)*01)0)*(0+(((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*1+((111+(101+110)
(000)*001+(101+110)(000)*010)1+((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)(000)*011+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*01)0)0)
(000)*1))*(10+(0+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)1+
((11(000)*1+(11(000)*001+11(000)*010)0)(000)*1+
((11(000)*001+11(000)*010)1+(11(000)*1+(11(000)*001+11(000)*010)0)
(000)*001+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)0)0)
(000)*01)1+(((11(000)*001+11(000)*010)1+(11(000)*1+(11(000)*001+11(000)*010)0)
(000)*001+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)0)1+
((11(000)*1+(11(000)*001+11(000)*010)0)(000)*1+
((11(000)*001+11(000)*010)1+(11(000)*1+(11(000)*001+11(000)*010)0)
(000)*001+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)0)0)
(000)*001+(0+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)1+
((11(000)*1+(11(000)*001+11(000)*010)0)(000)*1+
((11(000)*001+11(000)*010)1+(11(000)*1+(11(000)*001+11(000)*010)0)
(000)*001+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)0)0)
(000)*01)0)(((111+(101+110)(000)*001+(101+110)(000)*010)1+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)
(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*01)0)1+(((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*1+((111+(101+110)(000)*001+(101+110)(000)*010)1+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)
(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*01)0)0)(000)*001+(((101+110)(000)*011+((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*01)1+(((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*1+((111+(101+110)(000)*001+(101+110)
(000)*010)1+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*001+((101+110)(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)
(000)*010)0)(000)*01)0)0)(000)*01)0)*(100+(((101+110)(000)*011+((101+110)

(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*01)1+(((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*1+((111+(101+110)
(000)*001+(101+110)(000)*010)1+((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)(000)*011+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*01)0)0)(000)*01)1)))
(000+(((11+(001+(01+10)0)(000)*01)1+((001+(01+10)0)(000)*1+
((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*01)1+
(((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)0)(000)*1+(((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)1+((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)
(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*001+((11+(001+(01+10)0)(000)*01)1+
((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)0)(000)*01)0)0)(000)*01)1+((((01+10)1+(001+(01+10)0)
(000)*001+(11+(001+(01+10)0)(000)*01)0)1+((001+(01+10)0)(000)*1+
((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*001+
((11+(001+(01+10)0)(000)*01)1+((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)
(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*01)0)1+(((001+(01+10)0)(000)*1+
((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*1+
(((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)1+((001+(01+10)0)
(000)*1+((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)
(000)*001+((11+(001+(01+10)0)(000)*01)1+((001+(01+10)0)(000)*1+
((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*01)0)0)
(000)*001+(((11+(001+(01+10)0)(000)*01)1+((001+(01+10)0)(000)*1+
((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*01)1+
(((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)0)(000)*1+(((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)1+((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)
(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*001+((11+(001+(01+10)0)(000)*01)1+
((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)0)(000)*01)0)0)(000)*01)0)(((111+(101+110)(000)*001+(101+110)(000)*010)1+
((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*001+
((101+110)(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)
(000)*010)0)(000)*01)0)1+(((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)
(000)*010)0)(000)*1+((111+(101+110)(000)*001+(101+110)(000)*010)1+((101+110)

(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)
(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*01)0)0)(000)*001+(((101+110)(000)*011+((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*01)1+(((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*1+((111+(101+110)(000)*001+(101+110)
(000)*010)1+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*001+((101+110)(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)
(000)*010)0)(000)*01)0)0)(000)*01)0)*(100+(((101+110)(000)*011+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*01)1+(((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*1+((111+(101+110)
(000)*001+(101+110)(000)*010)1+((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)(000)*011+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*01)0)0)(000)*01)1)+
((((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)0)(000)*1+(((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)1+((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)
(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*001+((11+(001+(01+10)0)(000)*01)1+
((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)0)(000)*01)0)0)(000)*1+((((01+10)1+(001+(01+10)0)
(000)*001+(11+(001+(01+10)0)(000)*01)0)1+((001+(01+10)0)(000)*1+
((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*001+
((11+(001+(01+10)0)(000)*01)1+((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)
(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*01)0)1+(((001+(01+10)0)(000)*1+
((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*1+
(((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)1+((001+(01+10)0)
(000)*1+((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)
(000)*001+((11+(001+(01+10)0)(000)*01)1+((001+(01+10)0)(000)*1+
((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*01)0)0)
(000)*001+(((11+(001+(01+10)0)(000)*01)1+((001+(01+10)0)(000)*1+
((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*01)1+
(((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)0)(000)*1+(((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)1+((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)
(000)*001+(11+(001+(01+10)0)(000)*01)0)0)(000)*001+((11+(001+(01+10)0)(000)*01)1+

((001+(01+10)0)(000)*1+((01+10)1+(001+(01+10)0)(000)*001+(11+(001+(01+10)0)
(000)*01)0)0)(000)*01)0)0)(000)*01)0)(((111+(101+110)(000)*001+(101+110)
(000)*010)1+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*001+((101+110)(000)*011+((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*01)0)1+(((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*1+((111+(101+110)(000)*001+(101+110)
(000)*010)1+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*001+((101+110)(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)
(000)*010)0)(000)*01)0)0)(000)*001+(((101+110)(000)*011+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*01)1+(((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*1+((111+(101+110)
(000)*001+(101+110)(000)*010)1+((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)(000)*011+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*01)0)0)(000)*01)0)*(0+
(((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*1+
((111+(101+110)(000)*001+(101+110)(000)*010)1+((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)(000)*011+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*01)0)0)(000)*1))
(((11(000)*1+(11(000)*001+11(000)*010)0)(000)*1+
((11(000)*001+11(000)*010)1+(11(000)*1+(11(000)*001+11(000)*010)0)
(000)*001+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)0)0)(000)*1+
(((11(000)*001+11(000)*010)1+(11(000)*1+(11(000)*001+11(000)*010)0)
(000)*001+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)0)1+
((11(000)*1+(11(000)*001+11(000)*010)0)(000)*1+
((11(000)*001+11(000)*010)1+(11(000)*1+(11(000)*001+11(000)*010)0)
(000)*001+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)0)0)
(000)*001+(0+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)1+
((11(000)*1+(11(000)*001+11(000)*010)0)(000)*1+
((11(000)*001+11(000)*010)1+(11(000)*1+(11(000)*001+11(000)*010)0)
(000)*001+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)0)0)
(000)*01)0)(((111+(101+110)(000)*001+(101+110)(000)*010)1+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)
(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*01)0)1+(((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)

(000)*1+((111+(101+110)(000)*001+(101+110)(000)*010)1+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)
(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*01)0)0)(000)*001+(((101+110)(000)*011+((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*01)1+(((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*1+((111+(101+110)(000)*001+(101+110)
(000)*010)1+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*001+((101+110)(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)
(000)*010)0)(000)*01)0)0)(000)*01)0)*(0+(((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*1+((111+(101+110)(000)*001+(101+110)
(000)*010)1+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*001+((101+110)(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)
(000)*010)0)(000)*01)0)0)
(000)*1))*(10+(0+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)1+
((11(000)*1+(11(000)*001+11(000)*010)0)(000)*1+
((11(000)*001+11(000)*010)1+(11(000)*1+(11(000)*001+11(000)*010)0)
(000)*001+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)0)0)
(000)*01)1+(((11(000)*001+11(000)*010)1+(11(000)*1+(11(000)*001+11(000)*010)0)
(000)*001+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)0)1+
((11(000)*1+(11(000)*001+11(000)*010)0)(000)*1+
((11(000)*001+11(000)*010)1+(11(000)*1+(11(000)*001+11(000)*010)0)
(000)*001+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)0)0)
(000)*001+(0+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)1+
((11(000)*1+(11(000)*001+11(000)*010)0)(000)*1+
((11(000)*001+11(000)*010)1+(11(000)*1+(11(000)*001+11(000)*010)0)
(000)*001+(11(000)*011+(11(000)*1+(11(000)*001+11(000)*010)0)(000)*01)0)0)
(000)*01)0)(((111+(101+110)(000)*001+(101+110)(000)*010)1+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)
(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*01)0)1+(((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*1+((111+(101+110)(000)*001+(101+110)(000)*010)1+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)
(000)*011+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*01)0)0)(000)*001+(((101+110)(000)*011+((101+110)(000)*1+(111+(101+110)

(000)*001+(101+110)(000)*010)0)(000)*01)1+(((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*1+((111+(101+110)(000)*001+(101+110)
(000)*010)1+((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)
(000)*001+((101+110)(000)*011+((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*01)0)0)(000)*01)0)*(100+(((101+110)(000)*011+
((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*01)1+
(((101+110)(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*1+
((111+(101+110)(000)*001+(101+110)(000)*010)1+((101+110)(000)*1+(111+(101+110)
(000)*001+(101+110)(000)*010)0)(000)*001+((101+110)(000)*011+((101+110)
(000)*1+(111+(101+110)(000)*001+(101+110)(000)*010)0)(000)*01)0)0)(000)*01)1)))*
BIBLIOGRAFIA:

Bibliografa
Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2007). Teoria de automatas y
lenguajes de programacion. MADRID, MADRID, ESPAA: PEARSON
EDUCACIN S.A.