AUTOMATAS
¿Que es un automata?
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 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.
Un autómata es un modelo matemático para una máquina de estado finita (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 éste 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.
para mas informacion
Tipos de automata
E un modelo matemático de una maquina que acepta cadenas de un lenguaje definido sobre un alfabeto A. Consiste en un conjunto finito de estados y uno de
transiciones entre esos estados, que dependen de los símbolos de la cadena de entrada.
El Autómata finito acepta una cadena x si la secuencia de transiciones correspondientes a los
Símbolos de x conduce desde el estado inicial a un estado final.
La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de
Chomsky.
En lingüística la jerarquía de Chomsky es una clasificación jerárquica de distintos tipos de gramáticas formales que
generan lenguajes formales. Esta jerarquía
fue descrita por Noam Chomsky en 1956.
- La Jerarquía de Chomsky consta de cuatro niveles:
un no terminal, y en la parte derecha un solo terminal, posiblemente
seguido de un no terminal.
La regla también está permitida si S no aparece en la parte derecha de ninguna regla. Estos lenguajes son aquellos que pueden ser aceptados por un autómata finito.
También esta familia de lenguajes pueden ser obtenidas por medio de expresiones regulares.
Automata finito
En el comienzo del proceso de reconocimiento de una cadena de entrada, el autómata finito se encuentra en el estado inicial y a medida que procesa cada símbolo de
la cadena va cambiando de estado de acuerdo a lo determinado por la función de transición. Cuando se ha procesado el último de los símbolos de la cadena de entrada, el
autómata se detiene en el estado final del proceso. Si el estado final en el que se detuvo es un estado de aceptación, entonces la cadena pertenece al lenguaje
reconocido por el autómata; en caso contrario, la cadena no pertenece a dicho lenguaje.
Note que el estado inicial de un autómata finito siempre es único, en tanto que los estados finales pueden ser más de uno, es decir, el conjunto puede contener más
de un elemento. También puede darse el caso de que un estado final corresponda al mismo estado inicial.
mas informacion sobre los tipos de automatas
