Teoria De La Computacion

1. ¿Qué es la teoría de la computación?

-La teoría de la computación es una rama de la matemática y la computación que centra su interés en las limitaciones y capacidades fundamentales de las computadoras. Específicamente esta teoría busca modelos matemáticos que formalizan el concepto de hacer un cómputo y la clasificación de problemas.

-Es la búsqueda y utilización de modelos matemáticos para la definición formal de cómputos.

-Ejemplo: La Máquina de Turing, la cual es la base de la Teoría de la Computación actual.

2. ¿Qué es la teoría de autómatas?

-La teoría de autómatas 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 es el estudio de dispositivos de cálculo abstractos, es decir, de las “máquinas”

-Ejemplo:

Un autómata finito es un vector de tres elementos

M = (I,S,δ, F) donde I es el conjunto finito de entradas, S es el conjunto finito de estados (no vacío), δ es la función de transición de estados y F es el conjunto finito de estados finales (incluidos en S).

3. ¿Qué es un autómata finito?

-Un autómata finito 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 de transición (que puede ser expresada como una tabla).

-Un autómata es un modelo matemático para una máquina de estado finito.

-Ejemplo:

Un autómata finito es un vector de tres elementos

M = (I,S,δ, F) donde I es el conjunto finito de entradas, S es el conjunto finito de estados (no vacío), δ es la función de transición de estados y F es el conjunto finito de estados finales (incluidos en S).

...