Algoritmo de McNaughton y Yamada

Algoritmo de McNaughton y Yamada

el algoritmo de McNaughton y Yamada sigue los siguientes pasos. Dado un autómata Para no estados, y cuyos estados están numerados del 1 al no, damos una expresión para los lenguajes compuestos por las palabras que etiquetan los caminos de I Para j, para cualquier pareja I, j. Esta expresión se construye por inducción utilizando una condición en los caminos. Esta condición establece que las rutas solo pasan por ciertos estados permitidos.

Nuestro autómata teniendo no estados, por lo que nos enfocamos en construir un expresión regular para cada uno de no×no idiomas LOS_{s, s'} = { w∈X * | s.w = s' } formado por todas las palabras que envían un estado s cualquiera en otro estado si. Si lo conseguimos, el lenguaje reconocido por el autómata será el valor de una unión finita de expresiones regulares, por tanto de una expresión regular.

La idea es proceder paso a paso teniendo en cuenta un número creciente de estados intermedios entre s y si. Se supone que los estados están numerados de 0 a no, comenzamos con no estado intermedio, entonces solo s₀, después s₀ y s₁, después s₀, s₁ y s₂etc.

Apuntamos LOS_{s, s'}^(k) es la expresión del conjunto de palabras que etiquetan los caminos de s a s' y todos cuyos vértices intermedios son menores o iguales que k. Los vértices iniciales s y los vértices finales s' no son intermedios, por lo que no están sujetos a la restricción de ser menor o igual que k.

Construimos el LOS_{s, s'}^(k) por inducción en k, comenzando con k = 0 y terminando con k = n. Cuando k = n, la restricción sobre k ya no es una restricción, y LOS_{s, s'}^(k)=LOS_{s, s'}  si s≠s', y ε+LOS_{s, s}^(no)=LOS_{s, s}.

Para k = 0, dado que los vértices se numeran a partir de 1, la restricción simplemente expresa que no hay vértice intermedio. Las únicas rutas son las transiciones de sa s '(ignoramos una ruta de longitud 0 en el estado s).

Por lo tanto tenemos con s=p y s'=q:

Para la recurrencia, consideramos un camino de s a s' cuyos vértices intermedios son menores que k. Entonces son posibles dos casos:

1. los vértices intermedios son más pequeños que k-1, entonces la etiqueta está en LOS_{s, s'}^(k-1)
2. el camino pasa por el estado k. Luego descomponemos el camino en partes cuyos vértices intermedios son más pequeños que k-1. Para ello, consideramos cada aparición del vértice k en este camino: entre dos ocurrencias consecutivas, los vértices intermedios son menores que k-1. Entonces tenemos la fórmula con s = p y s '= q: .

Por tanto, hay n + 1 pasos. Cada uno de los pasos requiere el cálculo de n² expresiones, y el tamaño de las propias expresiones aumenta con k.

Ejemplo

Considere el siguiente autómata:

Con k = 0 tenemos:

Entonces k = 1:

Entonces k = 2:

Entonces k = 3:

Para el último paso simplemente calculamos las dos expresiones que nos interesan (estados iniciales a estados finales):

Por tanto, la expresión deseada es ab (a + b) ∗ + (b + aa) a ∗.