Teoria de la computacion

Ciencias de la Computación
Teoría de Autómatas.
Trata del estudio de máquinas de computación abstractas.
Teoría de la Computación.
Trata del estudio de la computabilidad y de la complejidad.Lenguajes y Gramáticas.
Trata del estudio y formalización de los lenguajes

Historia (I)
En 1930´s, A. Turing desarrolló una máquina abstracta denominada Máquina de Turing para el estudio de lacomputabilidad.
En 1940´s y 1950´s, se desarrollan unas máquinas simples, en cuanto su funcionamiento, que fueron conocidas como autómatas finitos, para modelar el funcionamiento del cerebro.
Tambiénen los 1950´s, N. Chomsky comienza el estudio formal de las gramáticas (generadoras de lenguajes).

Historia (II)
En 1969, S. Cook extiende el estudio de Tuning. Cook separa aquellos problemas quepueden ser solucionados de aquellos que en principio pueden ser solucionados pero que en la práctica toman demasiados recursos.
Autómatas finitos y ciertas clases de gramáticas formales son usadas enel diseño y construcción de software.
La Máquina de Turing ayuda a comprender que es lo que podemos esperar de nuestro software.

¿Por qué estudiar TALF?
Autómatas Finitos son modelos útiles paramuchos elementos hardware y software:

Software para diseñar y chequear la conducta de circuitos digitales.
El analizador léxico de un compilador.
Software para escanear grandes volúmenes detexto para encontrar patrones.
Software para verificar sistemas que tengan un número finito de estados, tales como protocolos de comunicación o de intercambio seguro de información.

Autómatas sonesenciales para el estudio de los límites de la computación:

¿Qué puede hacer un computador? Problema de la decibilidad.
¿Qué puede hacer un computador eficientemente? Problema de la tratabilidad.Los lenguajes nos permiten comunicarnos con la máquina, parte de lo que puede hacer la máquina depende del poder descriptivo del lenguaje.

Compiladores.
Traductores.
Diseño de lenguajes de...