Automatas

Autómatas
Los autómatas vienen a ser mecanismos formales que "realizan'' derivaciones en gramáticas formales. La manera en que las realizan es mediante la noción de reconocimiento. Una palabra será generada en una gramática si y sólo si la palabra hace transitar al autómata correspondiente a sus condiciones terminales. Por esto es que los autómatas son analizadores léxicos (llamados en inglés "parsers'') de las gramáticas a que corresponden.
Autómatas finitos
Autómata: Conjunto de estados + Control + Cambio de estados en respuesta a una entrada.
Tipo de Control
• Determinístico: Para cada entrada, hay sólo un estado al que el autómata puede ir desde el estado en que se encuentre.
• No determinístico: Un autómata finito es no-determinístico cuando se permite que el AF tenga0 o más estados siguientes para cada par estado-entrada.
• Si añadimos la propiedad de no-determinismo, no añadimos poder al autómata.
o No podemos definir ningún lenguaje que no se pueda definir con el autómata determinístico.
• Con la propiedad de no-determinismo se agrega eficiencia al describir una aplicación.
o Permite programar soluciones en un lenguaje de másalto nivel.
o Hay un algoritmo para compilar un N-DFA en un DFA y poder ser ejecutado en una computadora convencional.
• Extensión del N-DFA para hacer saltos de un estado a otro espontáneamente.
o Con la cadena vacía como entrada
o ÎN-DFA
o Estos autómatas también aceptan lenguajes regulares
Computabilidad
Es la acción de ser computable, esto es, dadoun determinado problema, existe un algoritmo representable en una computadora que puede hallar su solución; entendiéndose un algoritmo como una secuencia o receta de pasos finitos que solucionan el problema.
La teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que pueden ser resueltos con un algoritmo o equivalentemente con una máquina de Turing.Qué cosas pueden ser computadas por un ser humano que simplemente siga una lista de instrucciones con lápiz y papel, durante el tiempo que sea necesario, con ingenuidad y sin conocimiento previo del problema. Parte de la motivación para este trabajo era el desarrollar máquinas que computaran, y que pudieran automatizar el tedioso y lleno de errores trabajo de la computación humana.
Complejidad
Estetérmino está ligado únicamente al algoritmo. Operaciones básicas son las que constituyen el trabajo realizado para resolver el problema. En ningún momento con la velocidad de la computadora o con las facilidades de eficiencia que presenta un lenguaje de programación, ni con la habilidad del programador.
Complejidad computacional
La complejidad, es el estudio de la cantidad de tiempo y deespacio en memoria que toma la ejecución de un cómputo dado. La teoría de la complejidad computacional es la parte de la teoría de la computación que estudia los recursos requeridos durante el cálculo para resolver un problema. Los recursos comúnmente estudiados son el tiempo (número de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (cantidad de memoria utilizada pararesolver un problema).
Clases de complejidad
Los problemas de decisión se clasifican en conjuntos de complejidad comparable llamados clases de complejidad. La clase de complejidad P es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina determinista en tiempo poli nómico, lo que corresponde intuitivamente a problemas que pueden ser resueltos aun en el peor de sus casos. Laclase de complejidad NP es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina no determinista en tiempo poli nómico. Esta clase contiene muchos problemas que se desean resolver en la práctica, incluyendo el problema de satisfacibilidad booleana, el problema del camino de Hamilton y el problema de la cobertura de vértices. Todos los problemas de esta clase tienen...