http://es.wikipedia.org/wiki/Teor%C3%ADa_de_aut%C3%B3matas
Es una rama de las ciencias de la computacion 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 maquina 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 que 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 esta 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.
Autómatas finitos
Existen tres tipos de autómatas finitos
1. Automata finito determinado (AFD)
- Cada estado de un autómata de este tipo tiene una transición por cada símbolo del alfabeto.
www.scrigroup.com/limba/spaniola/346/CONVERTIR-UN-AFN-EN-AFD13233.php
- 2. Automata finito no determinada (AFND)
- Los estados de un autómata de este tipo pueden, o no, tener una o más transiciones por cada símbolo del alfabeto. El autómata acepta una palabra si existe al menos un camino desde el estado q0 a un estado final F etiquetado con la palabra de entrada. Si una transición no está definida, de manera que el autómata no puede saber como continuar leyendo la entrada, la palabra es rechazada.
- 3. Automata finito no determinado con transiciones ε (AFND-ε)
- Además de ser capaz de alcanzar más estados leyendo un símbolo,
permite alcanzarlos sin leer ningún símbolo. Si un estado tiene
transiciones etiquetadas con
, entonces el AFND puede encontrarse en cualquier de los estados alcanzables por las transiciones
, directamente o a través de otros estados con transiciones
. El conjunto de estados que pueden ser alcanzados mediante este método desde un estado q, se denomina la clausura
de q. 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.
http://es.wikipedia.org/wiki/Aut%C3%B3mata_finito_no_determinista

No hay comentarios:
Publicar un comentario