Free Web Hosting Provider - Web Hosting - E-commerce - High Speed Internet - Free Web Page
Search the Web

escudo.jpg (17355 bytes)

MUSICA MIENTRAS NAVEGAS CON REAL AUDIO

sacanimado.GIF (139839 bytes)

192 PERSONAS QUE NOS VISITAN

iconobusca.gif (415 bytes)

AUTOMATAS FINITOS NO DETERMINISTAS

Si existe mas de un estado de transición , el autómata se llama autómata finito no determinista (FNA, finite nondeterministic automaton) en especial, se permiten transiciones para la entrada vacía e . El ejemplo siguiente ilustrara esta situación. Considere el autómata A1. El estado inicial es X y el final es Y. Podemos ver que la estar en el estado X y leer una entrada 1 podemos cambiar al estado Yo permanecer en el estado X. El autómata A1 solo acepta frases que comienzan con 1; no hay transición de x al leer un 0. La frase 11 será aceptada porque hay una secuencia de transiciones hasta el estado final Y. Sin embargo, también hay una secuencia de transiciones donde podemos permanecer en el estado inicial X , que no es un elemento del conjunto de estados finales. Esto significa que en un autómata finito no determinista hay que revisar todas las transiciones posibles de una frase dada para estar seguros si esta aceptará o rechazará. Implantar autómatas finitos no deterministas como programas de computo no es una tarea trivial . Por ello, es importante saber que para cualquier autómata finito no determinista A podemos construir un autómata finito no determinista A¢ que acepte el mismo lenguaje que A ( es decir ,L(A)=L(A¢)).

REGRESAR

CONTINUAR