Teoría de autòmatas

Teoría de autòmatas es el estudio de las máquinas y autómatas abstractos, así como los problemas de cálculo que pueden ser resueltos usando ellos. Es una teoría en ciencias de la computación teórica, bajo la matemática discreta (una sección de Matemáticas y también de Informática). Autómatas viene de la palabra griega que significa αὐτόματα "auto-actuación".
La figura de la derecha muestra una máquina de estados finitos, que pertenece a una variedad bien conocido de autómata. Este autómata consiste en estados (representados en la figura por círculos) y transiciones (representadas por flechas). A medida que el autómata ve un símbolo de la entrada, tiene una transición (o salto) a otro estado, de acuerdo con su función de transición (que toma el estado actual y el símbolo reciente como entradas).
Teoría de Autómatas también está estrechamente relacionada con la teoría del lenguaje formal. Un autómata es una representación finita de un lenguaje formal que puede ser un conjunto infinito. Autómatas se clasifican a menudo por la clase de lenguajes formales que son capaces de reconocer.
Autómatas juegan un papel importante en la teoría de la computación, diseño del compilador, la inteligencia artificial, el análisis y la verificación formal.
Autómatas se definen para estudiar máquinas útiles bajo el formalismo matemático. Por lo tanto, la definición de un autómata está abierta a variaciones según la "máquina del mundo real", lo que queremos modelar utilizando el autómata. La gente ha estudiado muchas variaciones de autómatas. La variante más estándar, que se describe más arriba, se llama un autómata finito determinista. Las siguientes son algunas variaciones populares en la definición de los diferentes componentes de los autómatas.