Algoritmo de McNaughton y Yamada

Dificultad
Promedio 50%

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 Ij. Esta expresión se construye por inducción utilizando una condición en las rutas. Esta condición establece que las rutas solo pasan por ciertos estados autorizados.

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

La idea es avanzar paso a paso teniendo en cuenta un número creciente de estados intermedios entre s y s'. Se supone que los estados están numerados de 0 a no, comenzamos con no estado intermedio, entonces solo s0, después s0 y s1, después s0s1 y s2etc.

Apuntamos LOSs, s '(k) es la expresión para el conjunto de palabras que etiquetan las rutas de sa s 'y cuyos vértices intermedios son menores o iguales que k. Los vértices iniciales sy los finales s 'no son intermedios, por lo que no están limitados a ser menores o iguales que k.

Construimos el LOSs, 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 LOSs, s '(k)=LOSs, s '  si s ≠ s ', y ε +LOSs, s(no)=LOSs, 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:

Algoritmo de McNaughton y Yamada

Para la inducción, consideramos un camino de sa s 'cuyos vértices intermedios son más pequeños 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 LOSs, 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: Algoritmo de McNaughton y Yamada.

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

A continuación se muestra un ejemplo del algoritmo de McNaughton y Yamada.

Considere el siguiente autómata:

Algoritmo de McNaughton y Yamada

Con k = 0 tenemos:

Algoritmo de McNaughton y Yamada

Entonces k = 1:

Algoritmo de McNaughton y Yamada

Entonces k = 2:

Algoritmo de McNaughton y Yamada

Entonces k = 3:

Algoritmo de McNaughton y Yamada

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

Algoritmo de McNaughton y Yamada

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

Compartir, repartir
es_ESES