Automatas finitos
Páginas: 2 (366 palabras)
Publicado: 19 de febrero de 2010
Resumen de Automatas finitos
Un reconocedor es un programa toma una cadena y responde si o no de acuerdo a si ésta es una frase del programa, esta cadena puede crearse en un diagrama de flujo elcual puede ser determinista o no determinista, y este último se caracteriza por que en un símbolo de entrada se puede dar el caso de tener mas de una transición.
Ambos tipos de autómatas puedenconvertirse en expresiones regulares, los autómatas finitos deterministas (AFN) pueden ser representados mediante un grafo de transiciones, en el cual los nodos son los estados y en las aristas se detallanlos elementos del alfabeto que sirven para avanzar al siguiente estado.
Para diferenciar un AFN de un AFD se busca si el autómata tiene ambigüedad, o lo que es lo mismo, buscar si para llegar a variosestados de transición existe un solo elemento del alfabeto que conduzca esta rutas, por lo que un elemento del alfabeto tiene varias salidas aunque el resultado puede ser el mismo al llegar a unestado de aceptación y verificar que la cadena resultante es idéntica por cualquier camino.
La representación por medio de un diagrama de transiciones puede tener la ventaja de encontrar las transicionesde un determinado estado con mayor rapidez pero cuando el alfabeto es extenso el diagrama puede ser muy grande.
Los autómatas finitos deterministas (AFD) tienen a lo sumo una transición desde cadaestado con cualquier entrada, en la representación por medio de un diagrama de transiciones cada entrada es un solo estado por lo que es muy sencillo determinar si este tipo de autómatas acepta o no unacadena.
Se puede convertir un AFN en AFD, mediante la unificación en conjuntos de los estados del AFN que llevan a la aceptación de la misma cadena, la cual es representada en el AFD como un estadopor cada símbolo del alfabeto.
Las construcciones de AFN pueden darse de varias maneras, como dividir en subconjunto los estados de un AFD, y mediante una expresión regular, la cual se puede...
Un reconocedor es un programa toma una cadena y responde si o no de acuerdo a si ésta es una frase del programa, esta cadena puede crearse en un diagrama de flujo elcual puede ser determinista o no determinista, y este último se caracteriza por que en un símbolo de entrada se puede dar el caso de tener mas de una transición.
Ambos tipos de autómatas puedenconvertirse en expresiones regulares, los autómatas finitos deterministas (AFN) pueden ser representados mediante un grafo de transiciones, en el cual los nodos son los estados y en las aristas se detallanlos elementos del alfabeto que sirven para avanzar al siguiente estado.
Para diferenciar un AFN de un AFD se busca si el autómata tiene ambigüedad, o lo que es lo mismo, buscar si para llegar a variosestados de transición existe un solo elemento del alfabeto que conduzca esta rutas, por lo que un elemento del alfabeto tiene varias salidas aunque el resultado puede ser el mismo al llegar a unestado de aceptación y verificar que la cadena resultante es idéntica por cualquier camino.
La representación por medio de un diagrama de transiciones puede tener la ventaja de encontrar las transicionesde un determinado estado con mayor rapidez pero cuando el alfabeto es extenso el diagrama puede ser muy grande.
Los autómatas finitos deterministas (AFD) tienen a lo sumo una transición desde cadaestado con cualquier entrada, en la representación por medio de un diagrama de transiciones cada entrada es un solo estado por lo que es muy sencillo determinar si este tipo de autómatas acepta o no unacadena.
Se puede convertir un AFN en AFD, mediante la unificación en conjuntos de los estados del AFN que llevan a la aceptación de la misma cadena, la cual es representada en el AFD como un estadopor cada símbolo del alfabeto.
Las construcciones de AFN pueden darse de varias maneras, como dividir en subconjunto los estados de un AFD, y mediante una expresión regular, la cual se puede...
Leer documento completo
Regístrate para leer el documento completo.