robot de la enciclopedia para niños

Teoría de autómatas para niños

Enciclopedia para niños
Sistema combinacional Autómata finito Autómata con pila Máquina de Turing Teoría de autómatasTeoría de autómatas.svg


La teoría de autómatas es una rama de la teoría 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. También son de gran utilidad en la teoría de la complejidad computacional.

Un autómata es un modelo matemático para una máquina de estado finito (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 de transició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 qué estado cambiar dados unos determinados estado y símbolo.

La entrada es leída símbolo por símbolo, hasta que es "consumida" completamente (piense en ésta como una cinta con una palabra escrita en ella, que es leída por una cabeza lectora del autómata; la cabeza se mueve a lo 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 o rechazado 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 aceptadas por el autómata constituyen el lenguaje aceptado por el mismo.

Vocabulario

Los conceptos básicos de símbolos, palabras, alfabetos y strings son comunes en la mayoría de las descripciones de los autómatas. Estos son:

Autómatas finitos

Formalmente, un autómata finito (AF) puede ser descrito como una 5-tupla \langle Q, \Sigma, \delta, S_0, F\rangle.

Existen tres tipos de autómatas finitos

Autómata finito determinista (AFD)
Cada estado de un autómata de este tipo puede o no tener una transición por cada símbolo del alfabeto.
Archivo:DFAexample
AFD.

Sin embargo, puede observarse que todos estos tipos de autómatas pueden aceptar los mismos lenguajes. Siempre se puede construir un AFD que acepte el mismo lenguaje que el dado por un AFND.

Archivo:NFAexample
AFND con transiciones vacías.

Extensiones a los autómatas finitos

Los lenguajes aceptados por los autómatas descritos más arriba se denominan lenguajes regulares. Autómatas más potentes pueden aceptar lenguajes más complejos. Algunos de estos autómatas son:

Véase también

Kids robot.svg En inglés: Automata theory Facts for Kids

kids search engine
Teoría de autómatas para Niños. Enciclopedia Kiddle.