Demostraciones Lenguajes Regulares (Teoría de Lenguajes)

Autómatas

Función de transición extendida

La función de transición extendida o generalizada se define recursivamente sobre la cadena a la que se aplica. En el caso base (cadena vacía) devuelve el mismo estado (o su clausura lambda en un AFND-λ); en el inductivo, toma la cadena w + a y devuelve el conjunto resultante de aplicar la transición por a al conjunto de estados generado por la transicion sobre w.

• Caso Base: ${\hat {\delta }}(q,\lambda )=q$
• Caso Recursivo: ${\hat {\delta }}(q,wa)=\delta ({\hat {\delta }}(q,w),a)$

Esta naturaleza recursiva permite demostrar propiedades sobre la función de transición generalizada a partir de propiedades de la función de transición común utilizando inducción sobre la longitud de la cadena. Supongamos se tiene una función $\delta$ igual a una $\delta \prime$, se quiere probar que la igualdad vale tambien para la generalizada:

${\hat {\delta }}\prime (q_{0},wa)=\delta \prime ({\hat {\delta }}\prime (q_{0},w),a)$ por definición de generalizada,
$=\delta \prime ({\hat {\delta }}(q_{0},w),a)$ por HI,
$=\delta ({\hat {\delta }}(q_{0},w),a)$ por igualdad entre delta,
$={\hat {\delta }}(q_{0},wa)$ por definicion de generalizada.

Este esquema puede usarse para probar equivalencias o propiedades sobre funciones generalizadas dadas las de las funciones no generalizadas, y eventualmente predicar sobre el lenguaje en lugar de solamente caracteres.

Lenguaje aceptado por un automata

El lenguaje aceptado por un autómata generalmente se define como el conjunto de cadenas que derivan en un estado final al consumirse partiendo del estado inicial. Es decir, se define en función de la funcion de transicion extendida.

$w\in L(M)\Leftrightarrow \exists q_{f}\in {\hat {\delta }}(q_{0},w)$

Esto hace que demostrar una propiedad sobre la función de transición extendida permita demostrar propiedades sobre el lenguaje aceptado por un autómata. Al demostrar equivalencia entre autómatas, conviene demostrar equivalencias entre funciones de transición extendidas.

Equivalencias

AFND en AFD

Para probar que todo AFND puede representarse con un AFD, se construye uno equivalente tomando como estados todos los posibles conjuntos de estados del AFND original (partes de $Q$). Las transiciones entre los estados de este nuevo AFD se definen como las transiciones entre los conjuntos de estados del AFND. Los estados finales del AFD son aquellos conjuntos de estados del AFND que contenían algún estado final. O sea, por ejemplo, si $\delta '$ es la función de transición del AFD, $\delta '([q_{1},...,q_{j}],a)=[p_{1},...,p_{i}]\Leftrightarrow \delta (\{q_{1},...,q_{j}\},a)=\{p_{1},...,p_{i}\}$ .

Una manera de demostrar que ambos aceptan el mismo lenguaje, es demostrar primero que la función de transición extendida mantiene la misma relación que la ya definida partiendo de $q_{0}$ (el estado inicial), y luego chequear las condiciones de aceptación de una cadena de ambos autómatas.

Para probar que el conjunto de estados al que se llega en el AFND a partir de una cadena x es el estado definido por ese mismo conjunto en el AFD, se hace inducción en la longitud de x para probar $\delta '([q_{0}],x)=[p_{1},...,p_{i}]\Leftrightarrow \delta (q_{0},x)=\{p_{1},...,p_{i}\}$. El caso base (longitud cero) es trivial. El paso inductivo parte la cadena x en y + a, siendo a un caracter, y aplica hipótesis inductiva y la definición de delta del AFD.

Al saber que cualquier cadena lleva a estados análogos en el AFND y en el AFD, basta verificar la aceptación de la cadena. En el AFND es aceptada sii en el conjunto de estados al que se llega hay alguno final, mientras que en el AFD cada estado se marca como final si en el conjunto que representa había alguno final. Por lo tanto, el AFND acepta una cadena sii el AFD la acepta, con lo que representan el mismo lenguaje.

AFND-L en AFND

Antes de la demostración, es necesario notar que en el caso de los AFND-L la función de transición extendida para un caracter no es equivalente a la función de transición común (pues la primera efectúa la clausura lambda sobre el conjunto de llegada), con lo cual ya no pueden usarse indistintamente.

La demostración nuevamente es constructiva, a partir de un AFND-L se crea un AFND que admite el mismo lenguaje. Para esto se toma el mismo conjunto de estados, alfabeto y los mismo estados finales aunque se les agrega el inicial sii tiene algún final en su clausura lambda. La función de transición en el AFND se define como la función de transición extendida (para un caracter) del AFND-L, es decir, se le agrega la clausura lambda a cada paso.

Intuitivamente, el AFND generado es igual al AFND-L, pero se quitan las transiciones lambda al agregar transiciones a toda la clausura de la transición original. Por ejemplo, si se tenia $A\rightarrow aB$ y $B\rightarrow \lambda C$, se reemplaza por $A\rightarrow aB$ y $A\rightarrow aC$. El único detalle es que para el estado inicial se pierden las transiciones lambda, por eso hay que agregarlo (a veces) a los finales.

El lema intermedio a demostrar en este caso es análogo al anterior: $\delta '(q_{0},x)=\delta {\hat {(}}q_{0},x)$ para $|x|\geq 1$. Se busca probar por inducción que vale la equivalencia (definida entre las funciones de transición de los autómatas) en la función de transición extendida a partir del estado inicial. Nuevamente se demuestra a partir de separar el primer caracter del resto de la cadena, aplicar la definición original y luego hipótesis inductiva.

Sabiendo que partiendo de los estados iniciales y consumiendo las mismas cadenas en ambos autómatas se llegan a los mismos estados, resta probar que los lenguajes son iguales. Recordar que la condición de aceptación del AFND y del AFND-L es que la función de transición extendida aplicada a la cadena desde el estado inicial devuelva un conjunto que contenga algún estado final; la diferencia entre AFND y AFND-L es que la función de este ultimo incluye la clausura lambda a cada paso.

Si la cadena a aceptar es vacía, entonces en el AFNDL la condición de aceptación es que la clausura lambda del estado inicial contenga un final. Como los finales en el AFND equivalente se definieron incluyendo al estado inicial si esto sucedía, entonces lambda es aceptada en uno sii lo es en el otro.

Si la cadena a aceptar es no vacía, entonces ambas funciones de transición llevan al mismo conjunto de estados (por el lema intermedio). Como los estados finales son equivalentes o difieren en $q_{0}$, entonces la cadena es aceptada en un autómata sii (hay que separar el análisis según si se agregó a los estados finales $q_{0}$ o no).

Por lo tanto, el AFND así construido reconoce el mismo lenguaje que el AFNDL original.

Expresiones Regulares en AFND-L

Dada cualquier expresion regular, se puede construir un AFND-L con un unico estado final y sin transiciones a partir de este, haciendo induccion sobre la estructura de la expresion regular.

AFD en Expresiones Regulares

La demostración de la existencia de una expresión regular que captura el mismo lenguaje que un AFD es constructiva. Se basa en la definición de un sublenguaje (o conjunto de cadenas) $R_{i,j}^{k}$, previo numerar los estados del autómata de 1 a n.

La expresión $R_{i,j}^{k}$ representa a todas las cadenas que se obtienen en el automata yendo desde el estado i al estado j pasando por estados de índice a lo sumo k. Notar que i y j pueden ser mayores a k, pero solamente si aparecen como principio y final del camino. Análogamente, se define $r_{i,j}^{k}$ como la expresión regular cuyo lenguaje es dicho conjunto de cadenas.

La construcción de los R se hace mediante inducción sobre k´y lo que debemos demostrar constructivamente por inducción es que podemos dar una expresión regular cuyo lenguaje es R. El caso base es cuando se tiene $R_{i,j}^{0}$, esto es, todos los caminos que van de i a j sin pasar por ningún estado intermedio (pues están numerados a partir de 1). Esto es el conjunto de terminales que se encuentran en todos los arcos que van de i a j, más lambda si i y j son el mismo estado (el conjunto también puede ser vacío). La expresión regular que lo denota es simplemente la disyunción de todos los terminales así obtenidos, con o sin $\lambda$ según corresponda, la expresión regular $\emptyset$.

Para el paso inductivo, $R_{i,j}^{k}$ con $k\geq 1$, para cada camino se pueden dar dos posibilidades. Una es que el camino no pase por ningun estado de índice k, con lo que $r_{i,j}^{k}=r_{i,j}^{k-1}$.

El caso más elaborado es cuando pasa al menos una vez por el nodo k. Cada camino puede partirse entonces en tres partes: desde i a la primera aparición de k, desde la primera aparición de k hasta la ultima (que a su vez se puede dividir como cero o más caminos que empezaron y terminaron en k), y desde la última aparición de k hasta j.

Caminos de i a j pasando una o mas veces por k

Esto puede escribirse como $R_{i,k}^{k-1}(R_{k,k}^{k-1})^{*}R_{k,j}^{k-1}$. Sumado al caso en que no se pasa por el nodo k, y reemplazando cada conjunto de cadena por la ER que la representa, se tiene que la expresión regular final que denota las cadenas de $R_{i,j}^{k}$ es $r_{i,j}^{k-1}|r_{i,k}^{k-1}(r_{k,k}^{k-1})^{*}r_{k,j}^{k-1}$ (se aplicó la hipótesis inductiva en cada $R^{k-1}$).

En castellano, esto significa que para ir del nodo i al j pasando por nodos de a lo sumo índice k, se puede o bien ir directamente de i a j pasando por nodos de a lo sumo k-1, o bien ir hasta k, hacer cero o varios loops, y luego hacer el ultimo tramo de k a j.

Por lo tanto, se pueden generar expresiones regulares para todos los conjuntos de cadenas $R_{i,j}^{n}$, esto es, todas las cadenas que resultan de recorrer los caminos de i a j, sin restricción sobre los nodos intermedios.

Notar que el autómata acepta una cadena si existe un camino que la genera que comience en el estado inicial y termine en un estado final. Por lo tanto, las cadenas aceptadas serán aquellas de la forma $R_{i,j}^{n}$, con i estado inicial y j algún estado final.

Entonces, la expresión regular que genera el mismo lenguaje que el autómata es $r_{1,f_{1}}^{n}|r_{1,f_{2}}^{n}|\ldots |r_{1,f_{m}}^{n}$, siendo $f_{1}\ldots f_{m}$ los estados finales del autómata, y 1 el estado inicial.

Gramaticas Regulares en AFND

Dada una gramática regular $G=\langle V_{n},V_{T},P,S\rangle$ existe un $AFND$ $M=\langle Q,\Sigma ,\delta ,q_{0},F\rangle$

Se puede definir $M$ como:

1. $Q=V_{N}\cup \{q_{f}\}$
2. $\Sigma =V_{T}$
3. $q_{0}=q_{s}$
4. $q_{B}\in \delta (q_{A},a)\leftrightarrow A\rightarrow aB\in P$
5. $q_{f}\in \delta (q_{A},a)\leftrightarrow A\rightarrow a\in P$
6. $q_{A}\in F\leftrightarrow A\rightarrow \lambda \in P$
7. $q_{f}\in F$

La idea es que $M$ va a ser un AFND donde cada no terminal sea un estado, los terminales son las etiquetas de las transiciones entre estados y $q_{A}$ se conecta con $q_{B}$ por $a$ si en $G$ está la producción $A\rightarrow aB$. El estado inicial va a ser el del no terminal distinguido ($q_{S}$) y se agrega otro estado final ($q_{f}$) para conectar con $q_{A}$ si está $A\rightarrow a$.

Idea de la demostración:

Se demuestra primero el lema $A\Rightarrow ^{*}wB\Leftrightarrow q_{B}\in \delta (q_{A},w)$ por inducción en $w$:

• El caso base $w=\lambda$ es aútomático, porque si $w$ es vacia, $B$ tiene que ser $A$ (por las producciones que puede tener la gramática) y por definición de $\delta$ también se cumple lo otro.
• Luego se prueba para $w=\alpha a$. Se ve que si $A\Rightarrow ^{*}\alpha C$ y $C\rightarrow aB$, de $q_{A}$ se puede llegar a $q_{C}$ por $\alpha$ por hip. inductiva, y que de $q_{C}$ se puede llegar a $q_{B}$ por $a$ por la regla 4 de la definición de $M$. Entonces de $q_{A}$ se puede llegar a $q_{B}$ por $\alpha a$. Para probarlo para el otro lado, se ve que si se puede llegar a $q_{B}$ por $\alpha a$, entonces se puede llegar a un estado $q_{C}$ por $\alpha$ que llega a $q_{B}$ por $a$. Como sólo agregamos una transición a un estado $q_{B}$ no final si existe $C\rightarrow aB$, esta producción existe en G. Por hipótesis inductiva, $A\Rightarrow ^{*}\alpha C$. Por lo tanto, $A\Rightarrow ^{*}\alpha C\Rightarrow \alpha aB$, o sea, $A\Rightarrow ^{*}\alpha aB$.

Después se debe probar que el lenguaje generado por $G$ y $M$ es el mismo:

• Se parte de: $wa\in L(G)\Leftrightarrow S\Rightarrow ^{*}wa$ .
  • Hay dos formas en que de $S$ se puede llegar a la forma sentencial de sólo terminales $wa$:
    1. Se llega al $a$ final usando como último paso $A\rightarrow a$. Entonces, (por el lema aplicado a $w$), de $q_{S}$ se llegó a $q_{A}$, y (por def. 5) $q_{A}$ se conecta a $q_{f}$ por $a$.
    2. La otra opción es que como último paso nos deshacemos de un no terminal $B$ que le seguía al terminal $a$, y que desapareció usando $B\rightarrow \lambda$. Entonces, por el lema (aplicado a $waB$), de $q_{S}$ se llega a $q_{B}$ por $wa$, y (por def. 6) $q_{B}$ es final.
  • Llegamos entonces a que de $q_{S}$ se llega por $wa$ a $q_{f}$ o a un estado final $q_{B}$, lo cual es equivalente a $wa\in L(M)$.
• Se ve aparte: $\lambda \in L(G)\;\Leftrightarrow \;S\rightarrow \lambda \;\Leftrightarrow \;q_{S}\in F\;\Leftrightarrow \;\lambda \in L(M)$.

AFD en Gramáticas Regulares

Dado un AFD $M=<Q,\Sigma ,\delta ,q_{0},F>$ existe un gramática regular $G=<V_{n},V_{T},P,S>$ equivalente. Se demuestra definiendo $G$ así y probando luego que $M$ y $G$ generan el mismo lenguaje.

1. $V_{N}=Q$
2. $V_{T}=\Sigma$
3. $S=A_{q_{0}}$
4. $A_{p}\rightarrow aA_{q}\in P\leftrightarrow q=\delta (p,a)$
5. $A_{p}\rightarrow a\in P\leftrightarrow \delta (p,a)\in F$
6. $S\rightarrow \lambda \in P\leftrightarrow q_{0}\in F$

La idea es casi es la inversa que para pasar de gramática regular a AFND.

Idea de la demostración:

Se demuestra primero el lema $\delta (p,w)=q\Leftrightarrow A_{p}\Rightarrow ^{*}wA_{q}$ por inducción en $w$:

• El caso base $w=\lambda$ es verdadero por definición en los dos lados del ssi.
• Se prueba para $w=\alpha a$ separando el último paso de $\delta$ y aplicando la hip. inductiva a $\alpha$ para llegar a que $A_{p}\Rightarrow ^{*}wA_{x}$ (donde $x$ es el estado anterior para llegar a $q$) y usando que como de $x$ se llega a $q$, por la regla 4 $A_{x}\rightarrow aA_{q}$.

Después se debe probar que el lenguaje generado por $G$ y $M$ es el mismo:

• Analizamos cadenas no vacias partiendo de $wa\in L(M)\Leftrightarrow \delta (q_{0},wa)\in F$ . Separamos $\delta$ en el estado $p$ al que se llega consumiendo $w$ y la última transición por $a$ al estado final. Por el lema, al anteúltimo estado $p$ se llega con $w$ ssi $A_{q_{0}}\Rightarrow ^{*}wA_{p}$, y por la def. 5 $A_{p}\rightarrow a$. Esas dos cosas son equivalentes a $A_{q_{0}}\Rightarrow ^{*}wa$.
• Por def. 6 $q_{0}$ M es final (acepta la cadena vacía) ssi $S\rightarrow \lambda$.

Propiedades

Unión

El conjunto de lenguajes regulares incluido en $\Sigma ^{*}$ es cerrado respecto de la unión. Dados $L_{1}$ = $L(M_{1})$ y $L_{2}=L(M_{2})$, $L_{1}\cup L2$ es un lenguaje regular.

• Esto es inmediato con expresiones regulares, ya que el lenguaje generado por $ER(L_{1})+ER(L_{2})$ es regular y el más es por definición la unión de los lenguajes $L_{1}$ y $L_{2}$.

• Si lo queremos probar con autómatas, basta con: pegar $M_{1}$ al lado de $M_{2}$, agregar un estado inicial $q_{0}$ que tiene transiciones a los mismos estados (y por los mismos símbolos) que los iniciales de $M_{1}$ y $M_{2}$, marcarlo como final si alguno de los lenguajes acepta la cadena vacía y listo (transiciones y finales queda igual).

Complemento

El complmento de un lenguaje regular es regular

• Una forma constructiva de probar esto es tomando el AFD del lenguaje y complementando el conjunto de estados finales (poniendo los finales como no finales y vicevera). Es inmediato que esto genera el complemento. Si $\Delta$ es el alfabeto del autómata y queremos tomar el complemento respecto a un superconjunto $\Sigma$ de $\Delta$, basta con encontrar el autómata del complemento $M'$ y calcular: $L(M')\cup \Sigma ^{*}(\Sigma -\Delta )\Sigma ^{*}$ (notar que es una unión de lenguajes regulares). Recordar que el AFD debe estar completo (tener el estado "trampa").

Intersección

La intersección de un lenguaje regular es regular

Es inmediata usando la ley de DeMorgan, ya que $L_{1}\cap L_{2}={\overline {{\overline {L_{1}}}\cup {\overline {L_{2}}}}}$.

También se puede realizar de forma constructiva a partir de los autómatas. Se arma un gran autómata que tiene como estados el producto cartesiano de los estados de los otros dos de forma tal que un estado $(a,b)$ es final si $a$ y $b$ son finales en sus respectivos autómatas.

Unión e Intersección finita

La unión finita y la intersección finita de lenguajes regulares dan por resultado un leguaje regular. Es trivial de probar con una inducción.

Esto NO VALE para INFINITO. (pensar en la unión infinita de $a^{k}b^{k}$)

Pertenencia

Saber si una cadena pertenece a un lenguaje regular es decidible (Dado el lenguaje regular, se construye su AFD y se pone a prueba la cadena).

Finitud

Todo lenguaje finito es regular. Ya que se puede ver como la unión finita de los elementos uno a uno.

Determinar si un lenguaje regular es finito es decidible

Un lenguaje regular es finito si en su AFD ningún estado desde el cual se pueda alcanzar un estado final puede dar lugar a un "ciclo".

Alternativamente, un lenguaje regular es infinito sii su AFD acepta al menos una cadena de longitud $k$ tal que $2n>k\geq n$, donde $n$ es la cantidad de estados del AFD.

Vacuidad

Determinar si un lenguaje regular es vacío es decidible. Se construye el AFD y se mira si alguno de los estados alcanzables es final.

Equivalencia

Determinar si dos lenguajes regulares son equivalentes es decidible. Se construyen sus respectivos autómatas. Luego se construye el autómata de $(L_{1}\cap {\overline {L_{2}}})\cup ({\overline {L_{1}}}\cap L_{2})$. Si es vacío, son equivalentes, sino no lo son.

Lema de Pumping

Transición para Config Instantánea

La función de transición entre dos configuraciones instantáneas se define como $(q,a\alpha )\vdash (p,\alpha )$ sii existe una transición de q a p por a. Asimismo se define la función de transición generalizada.

Vale que si $(q,\alpha \beta )\vdash ^{*}(q,\beta )$, entonces $(q,\alpha ^{i}\beta )\vdash ^{*}(q,\beta )$ para cualquier $i\geq 0$. Es decir, si es posible hacer un loop sobre el estado q consumiendo la cadena alfa, entonces es posible realizar ese loop tantas veces como se desee. Se demuestra fácilmente por inducción en la cantidad de repeticiones de alfa.

Pumping

El lema de pumping expresa que dada una longitud mínima n (que depende del lenguaje), todas las cadenas z de longitud mayor o igual a n pueden escribirse como z = uvw, donde uv no supera a n, v es no vacía y es posible repetir tantas veces v como se desee sin que la cadena deje de pertenecer al lenguaje. Es decir, $uv^{*}w$ pertenece al lenguaje.

Intuitivamente, significa que existe una longitud n (para la cual puede tomarse la cantidad de estados del AFD mínimo que captura el lenguaje) tal que toda cadena mayor o igual resulta de haber realizado al menos un ciclo sobre uno de los estados del autómata. Esto es, si se tiene w = xyz, se obtiene un recorrido de la siguiente forma.

Lema de pumping

Notar que la cadena y debe ser no vacía para que el ciclo efectivamente exista, xy es menor que la cantidad de estados del autómata, y la cadena total debe superar la cantidad de estados (o podría ser capturada por el autómata sin efectuar ningún ciclo). Expresado en transiciones de configuraciones instantáneas:

$(q_{0},xyz)\vdash ^{*}(q_{i_{j}},yz)\vdash ^{*}(q_{i_{k}},z)\vdash ^{*}(q_{m},\lambda )$

Como $q_{i_{j}}=q_{i_{k}}$ y por la propiedad ya demostrada, es posible repetir y tantas veces como se desee y volver siempre al mismo estado, que tras consumir la cadena z se sabe que lleva a un estado final con lo que la cadena resulta aceptada.

El lema de pumping es una manera útil de demostrar que un lenguaje no es regular, viendo que no verifica este lema. Notar que la implicación no vale a la inversa, esto es, un lenguaje no regular puede cumplir pumping de regulares. En estos casos generalmente se recurre a demostrar que el complemento, inverso, unión o alguna combinación a partir de dicho lenguaje no lo verifica.

Minimizacion

Minimizacion se aplica solamente a AFD, no existe equivalente sobre AFND. Tambien es necesario que el AFD no tenga estados inalcanzables (debe haber un camino orientado desde el estado inicial hacia cualquier otro).

Se basa en el concepto de estados indistinguibles. Dos estados son indistinguibles sii para cualquier cadena, partiendo de esos estados se llega siempre o a finales o a no finales. Vale que los estados a los que se llegan son tambien indistinguibles. Indistinguibilidad es una relacion de equivalencia.

Indistinguibilidad de orden K

Es analogo a indistinguibilidad pero sujeto a cadenas de longitud a lo sumo K. Es el que se usa en la practica.

Relacion de equivalencia

Al igual que indistinguibilidad, es una relacion de equivalencia (reflexiva, simetrica y transitiva). La demostracion es trivial.

K+1 implica K

La relacion de orden K+1 esta contenida no estrictamente en la de orden K. Si dos estados son indistinguibles respecto de cadenas de longitud a lo sumo K+1, entonces, en particular, lo son para cadenas de longitud a lo sumo K.

Cociente por orden 0

El conjunto de estados de un automata, cocientado por la relacion de indistinguibildad de orden 0, lo separa en dos clases de equivalencia: los finales y los no finales.

K+1 sii K por todo terminal

Dos estados p y r son indistinguibles de orden K+1 sii para todo terminal a vale que los estados que se alcanzan a partir de consumir a por p y r son indistinguibles de orden K. Esto permite dar una definicion inductiva de indistinguibilidad.

La ida se prueba por absurdo. Si existe un terminal a tal que al consumirlo se llega a dos estados p' y r' distinguibles por alguna cadena alfa de longitud a lo sumo K, entonces la cadena a + alfa distingue K+1 a p y r, lo que contradice la hipotesis.

La vuelta tambien se puede probar por absurdo. Si p y r son distinguibles por alfa de longitud K+1, entonces p' y r' , alcanzados tras consumir el primer caracter de alfa, son distinguibles por el resto de alfa, que tiene longitud a lo sumo K, lo que contradice la hipotesis.

K+1 = K implica K+n = K

Si para cualquier par de estados q y p vale que la relacion de indistinguibilidad de orden K+1 es igual a la de orden K, entonces cualquier indistinguibilidad de orden superior seguira siendo igual. Esto da un criterio de corte para la definicion inductiva de indistinguibilidad de orden K, y permite generalizar de orden K a indistinguibilidad en general.

Puede demostrarse por induccion en n. El caso base es trivial. Para el paso inductivo, simplemente se usa que si dos estados son indistinguibles orden k+n+1, entonces los estados a los que se llega por cualquier terminal lo son orden k+n, y luego se aplica la hipotesis inductiva.

Intuitivamente, esto sucede pues indistinguibilidad de orden K permite distinguir a todos los estados que estan a "distancia" K de algun estado final. Al pasar a K+1, se agregan todos los estados que están a un paso más. Si no hay cambios, es porque ya se cubrieron todos los estados del automata, y no es necesario tener cadenas mas largas para distinguirlos.

Automata Minimo

Un automata minimo se logra tomando como estados las clases de equivalencia generadas por la relacion de indistinguibilidad en el automata original. Las transiciones en el nuevo automata se definen como $\delta \prime ([q],a)=[\delta (q,a)]$, es decir, el estado alcanzable en el AFDM a partir de la clase [q] por el terminal a, es la clase que se alcanza por a a partir de todos los estados que conforman q en el AFD original.

Transiciones entre clases indistinguibles

Dada la definicion de funcion de transicion anterior, vale la equivalencia tambien para la funcion de transicion extendida. Esto es, si en el AFD original se llegaba al estado r desde q por la cadena alfa, entonces en el minimo se llega a la clase de equivalencia de r desde q via alfa.

${\hat {\delta }}(q,a)=r\Longrightarrow {\hat {\delta }}\prime ([q],a)=[r]$

Se demuestra por induccion en la longitud de la cadena. El caso base (longitud cero) es trivial. Para el paso inductivo, se parte la cadena en a + alfa, y se aplica la definicion de la funcion no extendida (sobre a) junto con la hipotesis inductiva (sobre alfa), mas propiedades de la funcion de transicion extendida.

Cantidad de estados

Dados dos AFDs M y M', si para todo par de cadenas que conducen a estados diferentes en M desde q0 tambien conducen a estados diferentes en M' desde q0', entonces M' debe tener tantos o más estados que M.

Para demostrarlo, se puede obtener una funcion inyectiva de Q en Q', esto es, alguna funcion que para todo estado de Q vaya a un estado de Q' y no repita imagenes. Esto garantiza que $|Q|\leq |Q'|$.

Dicha funcion f(q) se puede definir como el estado que se alcanza en M' a desde q0' consumiendo la cadena g(q). La funcion g puede definirse como la menor cadena en M tal que al consumirla desde q0 se llegue al estado q; o sea, qué camino hay que seguir en M para llegar a q.

Como todas las cadenas generadas por g llevan a estados diferentes, entonces al consumirlas en M' tambien se llegan a estados diferentes (por hipotesis). Por lo tanto, se tiene la funcion inyectiva buscada.

Minimo

Se desea probar que el automata minimo construido a partir de las clases de equivalencia de la funcion de indistinguibilidad es efectivamente minimo. Esto es, que no existe ningun automata M' que reconozca el mismo lenguaje que MR (siendo MR el automata reducido) y que tenga menos estados.

Por la demostracion anterior, esto implica que deberia existir un par de cadenas alfa y beta tales que lleven a estados distintos p y r en MR y a estados iguales en M'.

Al ser p y r estados distintos en MR, significa que son distinguibles, esto es, que hay una cadena que lleva a uno a un estado final y a otro a uno no final. Esto significa que al concatenar esta cadena a las dos alfa y beta que habian dado origen a p y r, se obtienen dos cadenas, las cuales una pertenece al lenguaje y la otra no.

Ahora bien, como p y r coinciden en M', cualquier cadena los lleva al mismo estado, sea final o no. Entonces, al realizar la misma concatenacion que antes, se llega a ambas cadenas pertenecen o no. Por lo tanto, M' no reconoce el mismo lenguaje que MR, absurdo que proviene de suponer que MR no era minimo en cantidad de estados.