3.1.- Autómatas Finitos Deterministicos (AFD)

Consideremos el lenguaje regular A representado por c*(a È bc*)*. Si dada una cadena w se nos pregunta si w pertenece a A, debemos analizar no sólo los caracteres que aparecen en w, si no también sus posiciones relativas. Por ejemplo, la cadena abc⁵c³ab  esta en A, sin embargo cabac³bc no lo ésta. Podemos construir un diagrama que nos ayude a determinar los distintos miembros del lenguaje. Tal diagrama tiene la forma de un grafo dirigido con una información adicional añadida, y se llama diagrama de transición. Los nodos del grafo se llaman estados y se usan para señalar, en ese momento, hasta que lugar se ha analizado la cadena. Las aristas del grafo se etiquetan con caracteres del alfabeto y se llaman transiciones. Si el siguiente carácter a reconocer concuerda con la etiqueta de algua transición que parta del estado actual, nos desplazamos al estado al que nos lleve la arista correspondiente. Naturalmente, nosotros debemos comenzar por un estado inicial, y cuando se hayan tratado todos los caracteres de la cadena correspondiente, necesitamos saber si la cadena es “legal”. Para ello se marcan ciertos estados como estados de aceptación  o estados finales. Si cuando ha sido tratada la cadena en su totalidad terminamos en un estado de aceptación, entonces la cadena es “legal”. Marcaremos el estado inicial con una flecha (à) y alrededor de los estados de aceptación trazaremos un circulo.

Formalmente un autómata finito determinista M es una colección de 5 elementos.

1.- Un alfabeto de entrada S

2.- Una colección finita de estados Q

3.- Un estado inicial S

4.- Una colección F de estados finales o de aceptación

5.- Una función d: Q x S à Q que determina el único estado siguiente para el par (q_i,s) correspondiente al estado actual y la entrada.

Generalmente el termino autómata finito determinista se abrevia como AFD. Usaremos M=(Q,S,S,F,d) para indicar el conjunto de estados, el alfabeto, el estado inicial, el conjunto de estados finales y la función asociada con el AFD M.

La característica principal de un AFD es que d es una función. Por tanto d se debe definir para todos los pares (q_i,s) de Q x S. Esto significa que sea cual seas el estado actual y el carácter de la entrada, siempre hay un estado siguiente y este es único. Por tanto, para un par (q_i,s). En otras palabras, el estado siguiente está totalmente determinado por la información que proporciona el par (q_i,s).

Se puede crear un diagrama de transición a partir de la definición de un AFD. Primero, creamos y etiquetamos un nodo para cada estado. Entonces, para cada celda q_j de la fila correspondiente a estado q_i trazamos una arista desde q_i a q_j etiquetada tonel carácter de entrada asociado a q_j. Finalmente, se marca el nodo S con una flecha, y se trazan unos círculos en todos los nodos de F para indicar cuales son los estados de aceptación. Por tanto, el diagrama de transición para el AFD M=(Q,S,S,F,d), donde

Q = {q₀,q₁}

S = {a,b}

S = q₀

F = { q₀ }

y d representada mediante la tabla:

d	a	B
q0	q0	q1
q1	q1	q0

3.2.- Autómatas Finitos No Deterministicos (AFND)

Si se permite que desde un estado se realicen cero, una o mas transiciones mediante el mismo símbolo de entrada, se dice que el autómata es no deterministico. A veces es mas conveniente diseñas autómatas finitos no deterministicos (AFND) en lugar de los autómatas Finitos Deterministicos (AFD). Consideremos un lenguaje a*b È ab*. Las cadenas pertenecientes a este lenguaje están formadas por algunas aes seguidas de una b o por una a seguida de varias bes.

Aunque diseñar un diagrama es relativamente sencillo, debemos detenernos en poder determinar si este diagrama de transición corresponde al AFD de A. primero se debe comprobar que reconoce solo las cadenas pertenecientes a A, y después, si representa un AFD. Para ello, debemos comprobar que las reglas de transición constituyen una función, es decir, que de cada estado parte una y solo una transición para cada símbolo del alfabeto.

Consideremos ahora el diagrama de transición del AFD, este diagrama acepta solo cadenas pertenecientes a A. Fíjese también que las reglas de transición no son una función de QxS en Q porque no asigna un estado siguiente a los pares estado-entrada (q₄,a), (q₃,a), (q₃,b), (q₂,a) y (q₂,b). es mas, existe mas de un estado siguiente correspondiente al par (q₀,a).

Si tratamos de definir el término autómata finito no determinista, veremos que la mayor parte de la definición se puede obtener a partir de la de AFD. Es decir, tendremos un conjunto finito de estados Q, un alfabeto de entradaS, un estado inicial o de partida S, un conjunto de estados de aceptación F, y una regla de transición. La única diferencia que existe se encuentra en las reglas de transición. En un AFND, las reglas se asocian pares (q,s) con cero o más estados. Se puede decir que las reglas relacionan pares (q,s) con colecciones o conjuntos de estados. Esto significa que la regla es una relacion entre QxS y Q, o sobre (QxS)xQ. Por tanto, definiremos un autómata finito no determinista mediante una colección de 5 objetos (Q,S,S,F,D) donde:

1.- Q es un conjunto finito de estados

2.- S es el alfabeto de entrada

3.- S es uno de los estados de Q, designado como punto de partida

4.- F es una colección de estados de aceptación o finales.

5.- D es una relación sobre (QxS)xQ y se llama relación de transición.

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 entrada, D(q,s) e una colección de cero o mas estados [es decir, D(q,s) Í Q]. Esto indica que, para todo estado q, se pueden tener cero o mas alternativas a elegir como estado siguiente, todas para el mismo símbolo de entrada.

Como con los AFND, si M es un AFND, definimos el lenguaje aceptado por M or 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 un estado de aceptación o final al recorrer w (w es consumida en su totalidad).

Para determinar si una cadena pertenece a L(M), se debe recorrer el diagrama de transición correspondiente a M. Debemos encontrar un camino que termine en un estado de aceptación cuando haya sido consumida toda la cadena. Durante el recorrido, debemos elegir de forma no deterministica la transición de un estado a otro cuando existe más de una para el mismo símbolo. Para afirmar que la cadena no esta en L(M), debemos agotar  todas las formas posibles de recorrer el diagrama de transición para dicha cadena. Para diagramas de transición sencillos, esto puede ocasionar un problema de gasto de tiempo. El siguiente ejemplo proporciona una forma de abordar este problema de una manera distinta, evitando la búsqueda exhaustiva por el diagrama.

La  naturaleza recursiva del análisis de cadenas que vimos para los AFD se mantiene en los AFND si la notación se define con cuidado. Si XÍQ, vamos a interpretar D(X,s) como el conjunto de estados {p | q Î X y pÎD (q,s)}. Por tanto, D(X,s) es el conjunto de todos los estados siguientes a los que se puede llegar desde X con la entradas. Obsérvese que D(X,s)= È_qÎX D (q,s) [recuerdese que D(q,s) es un conjunto para cualquier estado q].

3.3.- Equivalencia entre AFD y AFND.

Hemos definido la equivalencia para los AFD. Extenderemos esta definición para la clase de todos los autómatas finitos (AFD y AFND)de forma que un autómata M es equivalente a un autómata M’ si L(M) = L(M’).

Ya que una función es un caso especial de relación (es decir, las funciones son relaciones que poseen requerimientos adicionales), las funciones de los AFD se consideran como relaciones en los AFND. En consecuencia, todo AFD es un AFND. La colección d lenguajes aceptados por los AFND incluye a todos los lenguajes aceptados por los AFD. De esto resulta que los AFND solo aceptan lenguajes aceptados por los AFD. Por lo tanto, los AFND no son más potentes que los AFD con respecto a los lenguajes que aceptan. Para probar esto, necesitamos demostrar que todo lenguaje aceptado por un AFND también es aceptado por algún AFD.

Sean M=(Q,S,S,F,D) un AFND. En el tema anterior presentamos una forma de recorrer M, de la cual se obtenía la colección de todos los estados accesibles desde el estado inicial en cada una de las etapas de análisis de una cadena. Estas técnicas proporcionan la base para construir un AFD M’=(Q’,S’,S’,F’,d’) que acepte el mismo lenguaje que M. Esencialmente, lo que se pretende es hacer que cada estado Q’ se corresponda con un conjunto de estados Q. Cuando se analiza una cadena con M, esta se acepta cuando la colección finadle estados contiene al menos un estado de aceptación perteneciente a F. por tanto, haremos que F’ sea el conjunto de estados de Q’ que se correspondan con los conjuntos de estados (de Q) que contienen un estado de F. haremos corresponder a S’ con el conjunto {S}.S’=S y definiremos d de forma que nos desplacemos de un conjunto de estados de M a otro, como se hace D.

Ahora demostraremos formalmente que todo lenguaje aceptado por un AFND es también aceptado por un AFD, con lo que probaremos que los lenguajes AFND y los lenguajes AFD están formados por la misma colección de lenguajes.

Teorema 1.- Sea M=(Q,S,S,F,D) un AFND. Entonces existe un AFD M’= (Q’,S’,S’,F’,d’) que es equivalente a M.

Demostración: Definamos M’=(Q’,S’,S’,F’,d’) como sigue: sea S’={S}, S’=S, Q’=2^Q (que es la colección de todos los subconjuntos de Q) y F’ la colección de todos los conjuntos  de Q’ que contienen estados de F. Para cada conjunto (q_i1,q_i2,q_in) de Q’ y cada  símbolo de entrada s de S, definiremos a  como:

d({q_i1, q_i2, …,q_1n},s) ={p₁,p₂,…p_k)

D({q_i1,q_i2,…,q_in},s) = {p₁,p₂,…,p_k}

Obsérvese que d, definida de esta forma, es una función Q’xS’ en Q’, puesto que esta bien definida para todos los elementos de Q’xS’.

Para probar que L(M) = L(M’), debemos demostrar que para toda la cadena w, d(S’,w)={p₁,p₂,…,p_j} si y solo si D (S,w)={p₁,p₂,…,p_j} con lo cual M’ acepta w si y solo si M acepta w. Probaremos esto por inducción sobre la longitud de w. Si la longitud de w es 0 (es decir w=e), entonces:

D(S,w)=D (S,e) = {S} = d (S’,w)

Ahora supongamos que para toda cadena w de longitud menor o igual que m se tiene que D(S,w)=d(S’,w). Supongamos que u es una cadena de longitud m+1. Entonces, existirá algún  sÎS, de forma que se obtiene que u=ws, donde w es una cadena de longitud m. En este caso,  d(S’ws) = d(d(S’,w),s). Ahora, por la hipótesis de inducción, dado que w tiene longitud m, d(S’,w)= {p₁,p₂,…,p_j} si y solo si D(s,w)={p1,p2,…,pj}.Pero por la forma en la que hemos definido d, tendremos que:

d({p1,p2,…,pj},s) = {r1,r2,…,rk}

si y solo si

D({p1,p2,…,pj},s)= {r1,r2,…,rk}

Por lo que d(S’,ws) = {r1,r2,…,rk} si y solo si D (S,ws) = {r1,r2,…,rk}. Es decir, la igualdad se cumple para cadenas de longitud m+1 si se cumple para cadenas de longitud m. Entonces por lo anterior tenemos que d(S’,w) es un estado de F’ si y solo si D(S,w) contiene algún estado de F. Por tanto M’ acepta w si y solo si M acepta w.

3.3.- Equivalencia entre AFD y AFND.

Hemos definido la equivalencia para los AFD. Extenderemos esta definición para la clase de todos los autómatas finitos (AFD y AFND)de forma que un autómata M es equivalente a un autómata M’ si L(M) = L(M’).

Ya que una función es un caso especial de relación (es decir, las funciones son relaciones que poseen requerimientos adicionales), las funciones de los AFD se consideran como relaciones en los AFND. En consecuencia, todo AFD es un AFND. La colección d lenguajes aceptados por los AFND incluye a todos los lenguajes aceptados por los AFD. De esto resulta que los AFND solo aceptan lenguajes aceptados por los AFD. Por lo tanto, los AFND no son más potentes que los AFD con respecto a los lenguajes que aceptan. Para probar esto, necesitamos demostrar que todo lenguaje aceptado por un AFND también es aceptado por algún AFD.

Sean M=(Q,S,S,F,D) un AFND. En el tema anterior presentamos una forma de recorrer M, de la cual se obtenía la colección de todos los estados accesibles desde el estado inicial en cada una de las etapas de análisis de una cadena. Estas técnicas proporcionan la base para construir un AFD M’=(Q’,S’,S’,F’,d’) que acepte el mismo lenguaje que M. Esencialmente, lo que se pretende es hacer que cada estado Q’ se corresponda con un conjunto de estados Q. Cuando se analiza una cadena con M, esta se acepta cuando la colección finadle estados contiene al menos un estado de aceptación perteneciente a F. por tanto, haremos que F’ sea el conjunto de estados de Q’ que se correspondan con los conjuntos de estados (de Q) que contienen un estado de F. haremos corresponder a S’ con el conjunto {S}.S’=S y definiremos d de forma que nos desplacemos de un conjunto de estados de M a otro, como se hace D.

Ahora demostraremos formalmente que todo lenguaje aceptado por un AFND es también aceptado por un AFD, con lo que probaremos que los lenguajes AFND y los lenguajes AFD están formados por la misma colección de lenguajes.

Teorema 1.- Sea M=(Q,S,S,F,D) un AFND. Entonces existe un AFD M’= (Q’,S’,S’,F’,d’) que es equivalente a M.

Demostración: Definamos M’=(Q’,S’,S’,F’,d’) como sigue: sea S’={S}, S’=S, Q’=2^Q (que es la colección de todos los subconjuntos de Q) y F’ la colección de todos los conjuntos  de Q’ que contienen estados de F. Para cada conjunto (q_i1,q_i2,q_in) de Q’ y cada  símbolo de entrada s de S, definiremos a  como:

d({q_i1, q_i2, …,q_1n},s) ={p₁,p₂,…p_k)

D({q_i1,q_i2,…,q_in},s) = {p₁,p₂,…,p_k}

Obsérvese que d, definida de esta forma, es una función Q’xS’ en Q’, puesto que esta bien definida para todos los elementos de Q’xS’.

Para probar que L(M) = L(M’), debemos demostrar que para toda la cadena w, d(S’,w)={p₁,p₂,…,p_j} si y solo si D (S,w)={p₁,p₂,…,p_j} con lo cual M’ acepta w si y solo si M acepta w. Probaremos esto por inducción sobre la longitud de w. Si la longitud de w es 0 (es decir w=e), entonces:

D(S,w)=D (S,e) = {S} = d (S’,w)

Ahora supongamos que para toda cadena w de longitud menor o igual que m se tiene que D(S,w)=d(S’,w). Supongamos que u es una cadena de longitud m+1. Entonces, existirá algún  sÎS, de forma que se obtiene que u=ws, donde w es una cadena de longitud m. En este caso,  d(S’ws) = d(d(S’,w),s). Ahora, por la hipótesis de inducción, dado que w tiene longitud m, d(S’,w)= {p₁,p₂,…,p_j} si y solo si D(s,w)={p1,p2,…,pj}.Pero por la forma en la que hemos definido d, tendremos que:

d({p1,p2,…,pj},s) = {r1,r2,…,rk}

si y solo si

D({p1,p2,…,pj},s)= {r1,r2,…,rk}

Por lo que d(S’,ws) = {r1,r2,…,rk} si y solo si D (S,ws) = {r1,r2,…,rk}. Es decir, la igualdad se cumple para cadenas de longitud m+1 si se cumple para cadenas de longitud m. Entonces por lo anterior tenemos que d(S’,w) es un estado de F’ si y solo si D(S,w) contiene algún estado de F. Por tanto M’ acepta w si y solo si M acepta w.

3.3.- Equivalencia entre AFD y AFND.

Hemos definido la equivalencia para los AFD. Extenderemos esta definición para la clase de todos los autómatas finitos (AFD y AFND)de forma que un autómata M es equivalente a un autómata M’ si L(M) = L(M’).

Ya que una función es un caso especial de relación (es decir, las funciones son relaciones que poseen requerimientos adicionales), las funciones de los AFD se consideran como relaciones en los AFND. En consecuencia, todo AFD es un AFND. La colección d lenguajes aceptados por los AFND incluye a todos los lenguajes aceptados por los AFD. De esto resulta que los AFND solo aceptan lenguajes aceptados por los AFD. Por lo tanto, los AFND no son más potentes que los AFD con respecto a los lenguajes que aceptan. Para probar esto, necesitamos demostrar que todo lenguaje aceptado por un AFND también es aceptado por algún AFD.

Sean M=(Q,S,S,F,D) un AFND. En el tema anterior presentamos una forma de recorrer M, de la cual se obtenía la colección de todos los estados accesibles desde el estado inicial en cada una de las etapas de análisis de una cadena. Estas técnicas proporcionan la base para construir un AFD M’=(Q’,S’,S’,F’,d’) que acepte el mismo lenguaje que M. Esencialmente, lo que se pretende es hacer que cada estado Q’ se corresponda con un conjunto de estados Q. Cuando se analiza una cadena con M, esta se acepta cuando la colección finadle estados contiene al menos un estado de aceptación perteneciente a F. por tanto, haremos que F’ sea el conjunto de estados de Q’ que se correspondan con los conjuntos de estados (de Q) que contienen un estado de F. haremos corresponder a S’ con el conjunto {S}.S’=S y definiremos d de forma que nos desplacemos de un conjunto de estados de M a otro, como se hace D.

Ahora demostraremos formalmente que todo lenguaje aceptado por un AFND es también aceptado por un AFD, con lo que probaremos que los lenguajes AFND y los lenguajes AFD están formados por la misma colección de lenguajes.

Teorema 1.- Sea M=(Q,S,S,F,D) un AFND. Entonces existe un AFD M’= (Q’,S’,S’,F’,d’) que es equivalente a M.

Demostración: Definamos M’=(Q’,S’,S’,F’,d’) como sigue: sea S’={S}, S’=S, Q’=2^Q (que es la colección de todos los subconjuntos de Q) y F’ la colección de todos los conjuntos  de Q’ que contienen estados de F. Para cada conjunto (q_i1,q_i2,q_in) de Q’ y cada  símbolo de entrada s de S, definiremos a  como:

d({q_i1, q_i2, …,q_1n},s) ={p₁,p₂,…p_k)

D({q_i1,q_i2,…,q_in},s) = {p₁,p₂,…,p_k}

Obsérvese que d, definida de esta forma, es una función Q’xS’ en Q’, puesto que esta bien definida para todos los elementos de Q’xS’.

Para probar que L(M) = L(M’), debemos demostrar que para toda la cadena w, d(S’,w)={p₁,p₂,…,p_j} si y solo si D (S,w)={p₁,p₂,…,p_j} con lo cual M’ acepta w si y solo si M acepta w. Probaremos esto por inducción sobre la longitud de w. Si la longitud de w es 0 (es decir w=e), entonces:

D(S,w)=D (S,e) = {S} = d (S’,w)

Ahora supongamos que para toda cadena w de longitud menor o igual que m se tiene que D(S,w)=d(S’,w). Supongamos que u es una cadena de longitud m+1. Entonces, existirá algún  sÎS, de forma que se obtiene que u=ws, donde w es una cadena de longitud m. En este caso,  d(S’ws) = d(d(S’,w),s). Ahora, por la hipótesis de inducción, dado que w tiene longitud m, d(S’,w)= {p₁,p₂,…,p_j} si y solo si D(s,w)={p1,p2,…,pj}.Pero por la forma en la que hemos definido d, tendremos que:

d({p1,p2,…,pj},s) = {r1,r2,…,rk}

si y solo si

D({p1,p2,…,pj},s)= {r1,r2,…,rk}

Por lo que d(S’,ws) = {r1,r2,…,rk} si y solo si D (S,ws) = {r1,r2,…,rk}. Es decir, la igualdad se cumple para cadenas de longitud m+1 si se cumple para cadenas de longitud m. Entonces por lo anterior tenemos que d(S’,w) es un estado de F’ si y solo si D(S,w) contiene algún estado de F. Por tanto M’ acepta w si y solo si M acepta w.