Glushkov Construction
El algoritmo de construcción de Glushkov permite, al igual que el algoritmo de construcción de Thompson, convertir una expresión regular en un autómata finito no determinista (AFND) pero, a diferencia de este último, los autómatas generados no contienen transiciones épsilon.
Sea n el número total de apariciones de símbolos del alfabeto en una expresión regular dada, su autómata asociado, generado por el algoritmo de construcción de Glushkov, contiene n+1 estados y n2 transiciones. Sin embargo, la cantidad de estados puede ser reducida utilizando paralelismo de bits.
Descripción del algoritmo
Para transformar una expresión regular en un AFND utilizando el algoritmo de Glushkov, se siguen los siguientes pasos:
Linearización
Para cada símbolo de la expresión regular, se añaden índices de manera secuencial.Por ejemplo, al linearizar la expresión regular (ab|a*b*), se obtiene (a1b2|a3*b4*).
Creación de estados
Se genera un estado por cada símbolo de la expresión regular previamente linearizada, los cuales pueden ser designados con el mismo índice de su símbolo correspondiente, además de añadir el estado inicial S~0~. Siguiendo con el ejemplo anterior, obtendríamos los estados {S0, 1, 2, 3, 4}.
Creación de conjuntos
- Determinar conjunto de símbolos iniciales: se crea un conjunto de todos los símbolos que puedan aparecer al inicio de cualquier string generado por la expresión regular.
- Determinar conjunto de símbolos finales: se crea un conjunto de todos los símbolos que puedan aparecer al final de cualquier cadena generada por la expresión regular.
- Determinar conjunto de símbolos pares: el conjunto de símbolos pares (o conjunto de pares de símbolos) consiste en tuplas de símbolos que pueden aparecer de manera consecutiva en una cadena generada por la expresión regular.
Transiciones
Se añaden transiciones desde el estado inicial S0 a cada uno de los estados previamente creados para cada símbolo. La etiqueta de cada una de estas transiciones corresponde al símbolo al que se dirige. Luego, se añaden transiciones por cada uno de los elementos {p1, p2} del conjunto de símbolos pares, donde la transición se extiende desde el estado que corresponda al símbolo de p1 hasta el de p2.
Pasos finales
Para terminar, deben designarse como estados de aceptación aquellos cuyo símbolo pertenezca al conjunto de símbolos finales. Finalmente, se debe eliminar los índices creados previamente en la linearización.
Ejemplo
Sea la expresión regular:
a* | (ab)
Se lineariza la expresión asignando índices a cada símbolo.
a1* | (a2b3)
Se crean los estados del AFND, donde tendremos uno por cada símbolo de la expresión y un estado inicial extra S0, el cual debe ser de aceptación si la expresión regular acepta la palabra vacía.
Se construye conjunto de símbolos iniciales. Los símbolos que pueden aparecer al inicio de una palabra generada por la expresión regular linearizada son:
SI = {a1, a2}
Se construye conjunto de símbolos finales. Los símbolos que pueden aparecer en una palabra generada por la expresión regular linearizada son:
SF = {a1, b3}
Se construye conjunto de símbolos pares. Las tuplas de símbolos que pueden aparecer de manera consecutiva en una palabra generada por la expresión regular linearizada son:
SP = {[a2, b3]}
Utilizando los estados del AFND creados anteriormente, se añaden transiciones desde S0 a cada uno de los demás estados.
También añadimos transiciones para cada una de las tuplas en SP.
Se asignan como estados de aceptación estados que coincidan con los elementos de SF. Por último, eliminamos subíndices de las transiciones del AFND.
Implementación
A continuación se tiene la implementación en C++ del algoritmo de construcción de Glushkov. La función main contiene la misma expresión descrita en la sección de ejemplo.
#include <bits/stdc++.h>
using namespace std;
struct Node {
char op; // puede ser operador o símbolo
// hijos del operador o símbolo
Node *left = nullptr, *right = nullptr;
int position = -1;
bool nullable = false;
set<int> si_set, sf_set;
};
int posCounter = 1;
map<int, char> posToSymbol;
map<int, set<int>> sp_Pos;
// nodo hoja
Node* makeSymbol(char c) {
Node* n = new Node();
n->op = c;
n->position = posCounter++;
posToSymbol[n->position] = c;
//true si nodo puede desaparecer y la cadena seguir siendo valida
n->nullable = false;
n->si_set = {n->position};
n->sf_set = {n->position};
return n;
}
// nodo de concatenacion de dos nodos
Node* makeConcat(Node* l, Node* r) {
Node* n = new Node();
n->op = '.';
n->left = l;
n->right = r;
n->nullable = l->nullable && r->nullable;
n->si_set = l->si_set;
if (l->nullable)
n->si_set.insert(r->si_set.begin(), r->si_set.end());
n->sf_set = r->sf_set;
if (r->nullable)
n->sf_set.insert(l->sf_set.begin(), l->sf_set.end());
for (int i : l->sf_set)
for (int j : r->si_set)
sp_Pos[i].insert(j);
return n;
}
// nodo de unión
Node* makeUnion(Node* l, Node* r) {
Node* n = new Node();
n->op = '|';
n->left = l;
n->right = r;
n->nullable = l->nullable || r->nullable;
n->si_set = l->si_set;
n->si_set.insert(r->si_set.begin(), r->si_set.end());
n->sf_set = l->sf_set;
n->sf_set.insert(r->sf_set.begin(), r->sf_set.end());
return n;
}
// nodo estrella de Kleene
Node* makeStar(Node* child) {
Node* n = new Node();
n->op = '*';
n->left = child;
n->nullable = true;
n->si_set = child->si_set;
n->sf_set = child->sf_set;
for (int i : child->sf_set)
for (int j : child->si_set)
sp_Pos[i].insert(j);
return n;
}
// muestra el conjunto de pares de simbolos
void printSimbolosPares() {
for (auto &p : sp_Pos) {
cout << "SímbolosPares(" << p.first << "): { ";
for (int x : p.second) cout << x << " ";
cout << "}\n";
}
}
struct State {
set<int> positions;
bool isFinal = false;
map<char, set<int>> transitions;
};
void buildAutomaton(Node* root) {
vector<State> states;
queue<set<int>> pending;
map<set<int>, int> stateId; // para identificar conjuntos de posiciones
int nextId = 0;
auto addState = [&](set<int> s) {
if (stateId.count(s)) return stateId[s];
State st;
st.positions = s;
for (int p : s)
if (root->sf_set.count(p))
st.isFinal = true;
states.push_back(st);
stateId[s] = nextId++;
pending.push(s);
return stateId[s];
};
// estado inicial:
addState(root->si_set);
while (!pending.empty()) {
set<int> current = pending.front();
pending.pop();
int id = stateId[current];
// se agrupan elementos de simbolospares por símbolo
map<char, set<int>> moves;
for (int p : current) {
char c = posToSymbol[p];
for (int q : sp_Pos[p])
moves[c].insert(q);
}
// transiciones
for (auto &m : moves) {
char sym = m.first;
set<int> dest = m.second;
int destId = addState(dest);
states[id].transitions[sym] = dest;
}
}
// printear automata resultante
cout << "\nConstrucción autómata de Glushkov\n";
for (int i = 0; i < (int)states.size(); ++i) {
cout << "Estado q" << i << " = { ";
for (int p : states[i].positions) cout << p << " ";
cout << "}";
if (states[i].isFinal) cout << " (final)";
cout << "\n";
for (auto &t : states[i].transitions) {
cout << " --" << t.first << "--> { ";
for (int q : t.second) cout << q << " ";
cout << "}\n";
}
}
}
int main() {
// Ejemplo REGEX: a*|(ab)
Node* a1 = makeSymbol('a');
Node* a2 = makeSymbol('a');
Node* b3 = makeSymbol('b');
Node* ab = makeConcat(a2, b3);
Node* aStar = makeStar(a1);
Node* root = makeUnion(aStar, ab);
cout << "Conjunto símbolos inciales: ";
for (int i : root->si_set) cout << i << " ";
cout << "\nConjunto símbolos finales: ";
for (int i : root->sf_set) cout << i << " ";
cout << "\n";
printSimbolosPares();
buildAutomaton(root);
}
Referencias
- Navarro, G., Raffinot, M. (2001). Compact DFA Representation for Fast Regular Expression Search. In: Brodal, G.S., Frigioni, D., Marchetti-Spaccamela, A. (eds) Algorithm Engineering. WAE 2001. Lecture Notes in Computer Science, vol 2141. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44688-5_1
Recursos útiles
- Regular Expression Matching with Glushkov Automata: https://coursys.sfu.ca/2018fa-cmpt-384-d1/pages/GlushkovRE