Introduccion a los automatas finitos y exp regulares

2.1. AUTÓMATAS FINITOS DETERMINÍSTICOS (DFA’S).

Las características de los autómatas finitos determinísticos son:

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 .
Para cada símbolo de entrada existe exactamente una transición a partir de cada estado (posiblemente de regreso al mismo estado).
Unestado, por lo general denotado como q0 es el estado inicial, en el que el autómata comienza.
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 deestados 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, elestado 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, hastaqué 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 esaceptada 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.

Ejemplo: El lenguaje que acepta el DFA esta formado por todas las cadenas sobre el alfabeto S = {a, b}, siempre y cuando terminen con a.

[pic]

Figura 2.1.

Q = {q0,q1}, S = {a, b}, q0 = q0 , F = {q1} y d se define mediante la tabla de la figura 2.1.

Se puede utilizar también la siguiente lista para definir la función d

(q0, a) = q1(q0, b) = q0

(q1, a) = q1(q1 ,b) = q0

El diagrama de transición se muestra en la figura 2.2.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Consideremos otro ejemplo. El DFA M= {Q, S , q0,F, d } acepta el lenguaje L(M)={w Î {a, b}* que no contiene tres b’s consecutivas} y esta representada por:

Q={q0, q1, q2, q3}

S ={a, b}

q0=q0

F={q0, q1, q2}

y d dada por la tabla de la figura 2.3.

[pic]

Figura 2.3.

El diagrama de transición correspondiente se muestra en la figura 2.4.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

2.2.AUTÓMATAS FINITOS NO DETERMINÍSTICOS (NFA’S).

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...