MEZA DE LOS PALOS ANA KAREN
***INSTITUTO TECNOLOGICO DE TIJUANA***
AUTÓMATAS FINITOS DETERMINÍSTICOS
.
Las características de los autómatas finitos determinísticos son:
1. Un conjunto finito de estados y un conjunto de transiciones de estado a estado, que se dan sobre símbolos de entrada tomados de un alfabeto S .
2. Para cada símbolo de entrada existe exactamente una transición a partir de cada estado (posiblemente de regreso al mismo estado).
3. Un estado, por lo general denotado como q0 es el estado inicial, en el que el autómata comienza.
4. Algunos estados (tal vez ninguno) están designados como final o de aceptación. Un autómata finito determinístico es una quinta tupla (Q, S , d , q0, F) donde:
Q es un conjunto finito de estados. S un alfabeto de entrada finito. q0 elemento de Q , el estado inicial. FÍ Q el conjunto de estados finales o de aceptación. d es la función d : Q x S ® Q que determina el único estado siguiente para el par (q1, s ) correspondiente al estado actual q1 y la entrada s . Generalmente el término autómata finito determinístico se abrevia como DFA de sus siglas en inglés Deterministic Finite Automaton. Usaremos M = (Q, S , q0, F, d ) para indicar el conjunto de estados, el alfabeto, el estado inicial, el conjunto de estados finales y la función asociadas con el DFA M.
Se puede construir un diagrama para que ayude a determinar los distintos miembros o cadenas del lenguaje. Tal diagrama tiene la forma de un grafo dirigido con información añadida, y se llama diagrama de transición. Los nodos del grafo corresponden a los estados del DFA y se usan para señalar, en ese momento, hasta qué lugar se analizó la cadena. Por lo general q0 es el estado inicial, marcando con una flecha (® ), el comienzo del autómata; algunos estados están designados como final o aceptación indicados por un doble círculo. Los símbolos del alfabeto son las etiquetas de los arcos del grafo. Si cuando ha sido tratada la cadena en su totalidad se termina en un estado de aceptación entonces la cadena es aceptada por el lenguaje. Si M es un AFD, entonces el lenguaje aceptado por M es L(M)={w Î S *½ w es aceptada por M}. Por tanto, L(M) es el conjunto de cadenas que hacen que M pase de su estado inicial a un estado de aceptación.
AUTÓMATAS FINITOS NO DETERMINÍSTICOS.
Un autómata finito no determinístico es una quinta tupla ( Q, S , q0, d , F) en donde Q, S , q0 y F (estados, entradas, estado inicial y estados finales) poseen el mismo significado que para un DFA, pero en este caso d es una transformación de Q x S a 2Q. (Recuérdese que 2Q es el conjunto de potencias de Q, el conjunto de todos los subconjuntos de Q). Obsérvese que puesto que d es una relación para todo par (q, s ) compuesto por el estado actual y el símbolo de la entrada, d (q, s ), es una colección de cero o más estados [es decir, d (q, s )Í Q]. Esto indica que, para todo estado q1 se pueden tener cero o más alternativas a elegir como estado siguiente, todas para el mismo símbolo de entrada.
Generalmente el término autómata finito no determinístico se abrevia como NFA de sus siglas en inglés Nondeterministic Finite Automaton. Si M es un NFA, definiremos el lenguaje acepatdo por M por medio de L(M)={w ½ w es una cadena aceptada por M} donde una cadena w es aceptada por M, si M pasa de su estado inicial a su estado de aceptación o final al recorrer w (w es consumida en su totalidad).
- AUTOMATA FINITO DETERMINISTA***
Un Autómata Finito Determinista consiste en un dispositivo que puede estar en cualquier estado entre un número finito, uno de los cuales es el estado inicial y por lo menos uno es un estado de aceptación.
A este dispositivo está unido un flujo de entrada por medio del cual llegan en secuencia los símbolos de un alfabeto determinado.
La máquina tiene capacidad para detectar los símbolos conforme llegan y, basándose en el estado actual y el símbolo recibido, ejecutar una transición consistente en cambiar a otro estado o la permanencia en el mismo.
El programa de un Autómata Finito Determinista no debe contener ambigüedades (para un estado un determinado símbolo sólo puede producir una determinada acción).
Se dice que un Autómata Finito Determinista acepta su cadena de entrada si, después de comenzar sus cálculos en el estado inicial la máquina cambia a un estado de aceptación después de leer el último símbolo de la cadena.
Si después de leer el último símbolo no queda en estado de aceptación, se dice que la cadena ha sido rechazada. Si la entrada es una cadena vacía (l) será aceptada si y sólo si el estado inicial es también un estado de aceptación.
Un Autómata Finito Determinista consiste en una quíntupla ( S, S, d, i, F) donde:
• S, es un conjunto finito de estados. • S, es el alfabeto de la máquina. • d, es una función (función de transición) de S× S a S. • i, (un elemento de S) es el estado inicial. • F (un subconjunto de S) es el conjunto de estados de aceptación.
La interpretación de la función de transición d de un autómata finito determinista es que d(p,x)=q sí y sólo sí la máquina puede pasar de un estado p a un estado q al leer el símbolo x.
El diagrama de transición determinista sólo debe tener un arco que sale de un estado para cada símbolo del alfabeto. Además, dicho diagrama está completamente definido, es decir, debe existir un arco para cada símbolo del alfabeto.
- AUTOMATA FINITO NO DETERMINISTA***
Esta maquina se parece mucho a un AFD, pues también analiza cadenas construidas a partir de un S y solo puede tener un numero finito de estados, algunos de los cuales son de aceptación y uno es el estado inicial.
A diferencia de los AFD, la transición que se ejecuta en una etapa dada de un AFN puede ser incierta, es posible aplicar cero, una o mas de una transición mediante el mismo símbolo de entrada, como sucede con una maquina que no esta completamente definida.
Un AFN acepta una cadena si es posible que su análisis deje a la maquina en un estado de aceptación.
De manera formal, un AFN se define como sigue, un AFN consiste en una quíntupla (S,∑ , p, i, F) donde:
• S es un conjunto finito de estados. • ∑ es el alfabeto de la maquina • p es un sub-conjunto de SXS XS llamada relación de transiciones. • i es le estado inicial (un elemento de S) • F es la colección de estados de aceptación (un sub-conjunto de S).