Sistemas

INSTITUTO TECNOLOGICO DE DURANGO

TEORIA DE LA COMPUTACIÓN

UNIDAD 1

Un automata es:
• Una maquina (mecanismo) de naturaleza formal (solo existe como un mecanismo matematico)
• Que acepta una información de entrada (input),
• La procesa
(La somete a transformaciones simbolicas que pueden adoptar la forma de un calculo o computación )
• y genera un resultado osalida (output)
Definir un autómata equivaldría a definir el proceso de transformación del input en un output, lo que equivale a definir una funcion cuyos argumentos son el input y cuyo valor es el output

TIPOS DE AUTOMATAS(1)

• Hay muchos tipos de autómatas
• Cada tipo de autómata se asocia a una potencia computacional determinada, es decir a una capacidad dada de resolución deproblemas
• De hecho, podemos clasificar los problemas algorítmicamente solubles asociándolos al tipo de autómata que resuelve
• Estos tipos se ordenan en jerarquia de menor a mayor potencial computacional
• Jerarquia de autómatas:
Autómatas finitos (Redes Logicas)
Autómatas intermedios:
Autómatas de memoria depila
Autómatas de memoria linealmente limitada
Maquinas de Turing
TIPOS DE AUTOMATAS (2)
• Ademas, podemos clasificar los autómatas:
Por el tipo de proceso que ejecutan
Aceptación o reconocimiento
Generación
Por su tipo de causalidad:Determinista
No – Determinista
Por el tipo de su almacenamiento de información:
De tamaño fijo
De tamaño creciente
De tamaño infinito
Por el tipo de la información que manejan
DiscretaContinua

TIPOS DE AUTOMATAS (3)

• Autómatas aceptadores o reconocedores:
Resuelven problemas con respuestas si- no que se modeliza normalmente como la identificación de dos estados finales uno de aceptación y otro de rechazo.
• Autómatas generadores o transductores:
Construyen una respuesta especifica (una salida) parael problema planteado
• Autómatas determinista:
La solución del problema viene unívocamente determinada por las entradas y los estados internos del autómata
• Autómatas no-deterministas:
La respuesta no esta unívocamente determinada

1. NOCIONES MATEMÁTICAS

1. CONJUNTOS

Un conjunto es una colección de objetos llamados elementosdel conjunto.
Si A es un conjunto y a es un elemento de A utilizaremos la notación a ( A (se lee “a es un elemento de A”). Se usa la notación b ( A cuando b no es un elemento de A.

Si A contiene exactamente los elementos a1, a2, . . . . ., an, lo indicamos escribiendo A={a1,a2, . . . . ., an}.

Un conjunto solo se caracteriza por suselementos y no por el orden en el cual se listan.

Los conjuntos A y B son iguales si contienen los mismos elementos. Por lo tanto si, A={1,2,3} y B={2,1,3} se puede escribir que A=B.

Algunas veces es conveniente describir el contenido de un conjunto en términos de un propiedad que sea característica de todos los elementos del conjunto.Sea P(x) una proposición sobre x. La notación {x( P(x)}, que se interpreta como “ el conjunto de todas las x tales que P(x) ”, denota el conjunto de todos los x para los cuales P(x) es una proposición verdadera. (Todas las x tienen la propiedad P).

Notación de Conjuntos

P = { x ( P(x)}. See lee “x tal que P(x) es verdadero”.

A= { x ( x es una letra del alfabeto}.

A= { a, b, c, d, e, ....