Automata

INSTITUTO TECNOLÓGICO DE LA COSTA GRANDE

ING. EN SISTEMAS COMPUTACIONALES

TEORÍA DE LA COMPUTACIÓN


AUTÓMATA,COMPUTABILIDAD, COMPLEJIDAD

IV SEMESTRE

MICHAEL VALDOVINOS TORRES

28-Junio-2011
Índice

Autómata……………………………………………………………I
Computabilidad……………………………………………………IIComplejidad………………………………………………………III
Referencias Bibliográficas………………………………………IV

I. AUTOMATA
Es una rama de las ciencias de la computación que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver. La teoría de autómatas estáestrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capaces de reconocer.
Un autómata es un modelomatemático para una máquina de estado finita (FSM sus siglas en inglés). Una FSM es una máquina que, dada una entrada de símbolos, "salta" a través de una serie de estados de acuerdo a una función detransición (que puede ser expresada como una tabla). En la variedad común "Mealy" de FSMs, esta función de transición dice al autómata a que estado cambiar dados un determinado estado y símbolo.
La entrada esleída símbolo por símbolo, hasta que es "consumida" completamente (piense en esta como una cinta con una palabra escrita en ella, que es leída por una cabeza lectora del autómata; la cabeza se mueve alo largo de la cinta, leyendo un símbolo a la vez) una vez la entrada se ha agotado, el autómata se detiene.
Dependiendo del estado en el que el autómata finaliza se dice que este ha aceptado orechazado la entrada. Si este termina en el estado "acepta", el autómata acepta la palabra. Si lo hace en el estado "rechaza", el autómata rechazó la palabra, el conjunto de todas las palabras aceptadaspor el autómata constituyen el lenguaje aceptado por el mismo.

I
II. COMPUTABILIDAD
Es la parte de la computación que estudia los problemas de decisión...