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 racional E son los siguientes:
- Transforme la expresión E en una nueva expresión E' donde cada letra aparece como máximo una vez en E'.
- Construye un autómata A' aceptando el conjunto de palabras descrito por E'
- Transformar A' en un autómata A aceptando el conjunto de palabras descrito por E reemplazando los símbolos únicos de E' por los de origen
Paso 1: letras separadas
El primer paso en el algoritmo de Gloushkov es hacer que todas las letras sean distintas en la expresión. 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:
Paso 2: construcción del autómata
Sea E' una expresión regular donde todas las letras son diferentes. Construimos un autómata A' de la siguiente manera.
- 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') al que le sumamos i si ε ∈ E'
- Las transiciones son (i,a,a) para a ∈ First(E') y (a,b,b) para (a,b) ∈ Next(E')
En nuestra expresión (x1 + x2) * (X3X4X5 + ε), construimos el estado inicial i con 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}. Esto finalmente da el siguiente autómata:
