Automata finito
Páginas: 2 (462 palabras)
Publicado: 21 de agosto de 2010
AUTÓMATA FINITO
Un autómata finito o máquina de estado finito es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadenapertenece al lenguaje que el autómata reconoce.
Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en unafunción de transición, que recibe en un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado aotro, para finalmente detenerse en un estado final o de aceptación, que representa la salida.
La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a loslenguajes formales más simples según la Jerarquía de Chomsky.
Generalizaciones de autómatas finitos.-
Existes diversas generalizaciones posibles de hacer sobre los autómatas finitos, para aumentarsu uso y expresividad. Así, por ejemplo, se definen los transductores de estados finitos como autómatas finitos que están dotados además de un alfabeto de salida, distinto al de entrada, y que puedenposeer más de un estado inicial. Las máquinas de Moore y máquinas de Mealy son conocidos ejemplos de transductores, que se utilizan sobre todo para modelar sistemas secuenciales.
Es inclusoposible aumentar el poder de cómputo de un autómata finito, permitiendo un alfabeto adicional sobre éste, que actúe sobre una memoria de tipo pila para ser considerada en cada transición. Esta es la ideautilizada por los llamados autómatas con pila, los cuales son capaces de reconocer lenguajes libres de contexto, que están un nivel por sobre los lenguajes regulares en la Jerarquía de Chomsky.Descripción informal de su funcionamiento.-
En el comienzo del proceso de reconocimiento de una cadena, el AF se encuentra en el estado inicial y a medida que procesa cada símbolo de la cadena va...
Un autómata finito o máquina de estado finito es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadenapertenece al lenguaje que el autómata reconoce.
Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en unafunción de transición, que recibe en un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado aotro, para finalmente detenerse en un estado final o de aceptación, que representa la salida.
La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a loslenguajes formales más simples según la Jerarquía de Chomsky.
Generalizaciones de autómatas finitos.-
Existes diversas generalizaciones posibles de hacer sobre los autómatas finitos, para aumentarsu uso y expresividad. Así, por ejemplo, se definen los transductores de estados finitos como autómatas finitos que están dotados además de un alfabeto de salida, distinto al de entrada, y que puedenposeer más de un estado inicial. Las máquinas de Moore y máquinas de Mealy son conocidos ejemplos de transductores, que se utilizan sobre todo para modelar sistemas secuenciales.
Es inclusoposible aumentar el poder de cómputo de un autómata finito, permitiendo un alfabeto adicional sobre éste, que actúe sobre una memoria de tipo pila para ser considerada en cada transición. Esta es la ideautilizada por los llamados autómatas con pila, los cuales son capaces de reconocer lenguajes libres de contexto, que están un nivel por sobre los lenguajes regulares en la Jerarquía de Chomsky.Descripción informal de su funcionamiento.-
En el comienzo del proceso de reconocimiento de una cadena, el AF se encuentra en el estado inicial y a medida que procesa cada símbolo de la cadena va...
Leer documento completo
Regístrate para leer el documento completo.