AUTÓMATA FINITO DETERMINISTA

Un autómata finito determinista (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado en que se encuentre el autómata, y con cualquier símbolo del alfabeto leído, existe siempre a lo más una transición posible desde ese estado y con ese símbolo.

Un Autómata Finito Determinista consta de:1. Un conjunto finito de estados, menudo designado como Q.

2. Un conjunto finito de símbolos de entrada, menudo designado como (sigma).

3. Una función de transición que toma como argumentos un estado y un símbolo de entrada y devuelve un estado. La función de transición se designa habitualmente como ᵟ o Δ (delta).

4. Un estado inicial, uno de los estados de Q.

5. Un conjunto de estados finales o de aceptación F.El conjunto F es un subconjunto de Q.

Autómata finito determinista que reconoce el lenguaje regular conformado exclusivamente por las cadenas con un número par de ceros y un número par de unos.

Ejemplo de AFD con dos estados. En nodo de la izquierda es inicial y de aceptación

Formalmente, se define como una 5-tupla (Q, Σ, q0, δ, F) donde:

En un AFD no pueden darse ninguno de estos dos casos:

Que existan dos transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2; Que existan transiciones del tipo δ (q, ε), donde ε es la cadena vacía, salvo que q

sea un estado final, sin transiciones hacia otros estados.

Ejemplo de determinizar (AFnD con ǫ-transiciones)

En algunos lenguajes de programación, los comentarios aparecen entre los delimitadores “/*” y “*/” como marca inicial y final del comentario. Sea L el lenguaje de todas las cadenas de comentarios delimitados. Así pues todo elemento de L, empieza por /* y acaba por */, pero no debe tener ningún */ intermedio. Por simplicidad consideraremos que el alfabeto sería {a, b, /,*}. Indicar el Autómata Finito Determinista que reconoce L.Solución:Un posible autómata es AFD1=({/,*,a,b},{S,A,B,C,D,Z},f,S,{D}), siendo f:

En esta solución, la cadena de entrada debe contener la marca de inicio de comentario (“\*”) desde el principio, lo cual se reconoce en las transiciones entre los estados S, A y B. Si la cadena de entrada no comienza con “\*”, la palabra se rechaza, transitando desde S o A al estado sumidero, Z.Además, en esta solución sólo se reconoce un comentario, por lo que al llegar al final del comentario, es decir, cuando el autómata está situado en el estado final D, el resto de cadena no se analiza, dado que se transita al estado sumidero Z, del que no se sale.Cabe destacar que las transiciones de B, C y entre ellos leen el texto que se encuentra dentro del comentario, analizando si se ha llegado a la marca de fin de comentario (“*/”) o no, y hay que retroceder a B para seguir leyendo símbolos del interior del comentario.

AUTÓMATA FINITO NO DETERMINISTICOS

Un autómata finito no determinista (abreviado AFND) es un autómata finito que, a diferencia de los autómatas finitos deterministas (AFD), posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.

En un AFND puede darse cualquiera de estos dos casos:

Que existan transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2; Que existan transiciones del tipo δ(q, ε), siendo q un estado no-final, o bien un

estado final pero con transiciones hacia otros estados.

Cuando se cumple el segundo caso, se dice que el autómata es un autómata finito no determinista con transiciones vacías o transiciones ε (abreviado AFND-ε). Estas transiciones permiten al autómata cambiar de estado sin procesar ningún símbolo de entrada. Considérese una modificación al modelo del autómata finito para permitirle ninguna, una o más transiciones de un estado sobre el mismo símbolo de entrada.

Ejmplo Computacion de un automata no determinista

Dado un AFnD M = (Q,_, δ, q0, F)◮ Una computaci´on de M con entrada w = w1 . . . wn es(r0, r1, . . . , rm) que cumple:◮ w = y1 . . . ym con yi 2 _ [ ǫ◮ r0 es el estado inicial◮ ri+1 2 δ(ri , yi+1)◮ Una computacion aceptadora de M con entrada w es unacomputaci´on (r0, r1, . . . , rm) de M con entrada w que cumplerm 2 F.