El algoritmo de Gloushkov

Dificultad
Fácil 25%

El algoritmo de Gloushkov

El algoritmo de Glushkov construye un autómata no determinista aceptando el conjunto de palabras descritas por una expresión regular. El número de estados del autómata es proporcional al tamaño de la expresión.

Los pasos principales del algoritmo de Gloushkov a partir de una expresión regular E son los siguientes:

  1. Transforma la expresión E en una nueva expresión E 'donde cada letra aparece como máximo una vez en E'.
  2. Construye un autómata A 'aceptando el conjunto de palabras descrito por E'
  3. Transforma A 'en un autómata A aceptando el conjunto de palabras descrito por E reemplazando los símbolos únicos de E' por los originales

Paso 1: letras separadas

El primer paso en el algoritmo de Glushkov es hacer que todas las letras de la expresión sean distintas. Cada aparición de la misma letra está numerada. La expresión E = (ab + b)* se convierte, por ejemplo, en E '= (ab0 + b1)*.

Tomemos un ejemplo más largo: E = (a + b) * (abb + ε). Después de renombrar tenemos la siguiente expresión: (x1 + x2) * (X3X4X5 + ε).

Ahora debemos definir el primer grupo que contiene los símbolos que pueden comenzar una palabra. Por último, el grupo que contiene los símbolos que pueden terminar la palabra. Y una siguiente tabla que define los símbolos que pueden tener como sufijo otro símbolo.

En este ejemplo tenemos:

  • Prime = {x1, X2, X3}
  • Último = {x1, X2, X5}
  • Tabla de lo siguiente: Algoritmo de Glushkov

Paso 2: construcción del autómata

Sea E 'una expresión regular donde todas las letras son diferentes. Construimos un autómata A 'como sigue.

  • El conjunto de estados es Q = {i} ∪ {a: a aparece en E '}
  • El estado inicial es el estado i
  • Los estados finales son Último (E ') a los que agregamos i si ε ∈ E'
  • Las transiciones son (i, a, a) para a ∈ Prime (E ') y (a, b, b) para (a, b) ∈ Next (E')

En nuestra expresión (x1 + x2) * (X3X4X5 + ε), construimos el estado inicial i con la transición x1, X2, X3 a los respectivos estados x1, X2, X3.

Luego usamos la siguiente tabla para crear los enlaces de tipo (a, b, b). Por ejemplo si tomamos la primera línea tenemos los siguientes arcos: (x1, X1, X1), (X1, X2, X2), (X1, X3, X3).

Para terminar agregamos los estados terminales {x1, X2, X5}. Lo que finalmente da el siguiente autómata:

Algoritmo de Glushkov