Saltar a contenido

Thompson Construction

El Algoritmo de Construcción de Thompson es un método fundamental en la teoría de la computación para convertir una expresión regular (ER) en un Autómata Finito No Determinista (NFA) equivalente. Las definiciones de estos conceptos se describen en el libro de Sipser\(^1\).

Este algoritmo fue descrito por primera vez por Ken Thompson en su artículo de 1968\(^2\). Thompson lo utilizó para implementar una de las primeras aplicaciones de expresiones regulares en forma de "programa", en concreto, para la búsqueda de expresiones regulares en el editor de texto orientado a líneas QED\(^3\). Anteriormente, en los editores solo se utilizaba la búsqueda de cadenas literales. Posteriormente, esto conllevó a su uso en importantes programas de Unix como ed, grep, lex, sed, AWK y expr, además de ser la base para implementaciones en editores como vi y Emacs.

La principal ventaja de este algoritmo es su naturaleza composicional y recursiva. Construye el NFA para una expresión regular compleja a partir de NFAs más pequeños correspondientes a sus subexpresiones. Por lo tanto, el NFA resultante tiene una estructura muy regular:

  • Tiene exactamente un estado inicial y un estado de aceptación.
  • Para una expresión regular de longitud \(m\) (contando operadores y símbolos), el NFA resultante   tendrá como máximo \(2m\) estados y \(4m\) transiciones. Esta complejidad espacial lineal es su característica más destacada.
  • El algoritmo de construcción en sí también opera en tiempo lineal, \(O(m)\), asumiendo que la expresión regular ya está analizada (por ejemplo, en notación postfija).

Complejidad de Búsqueda y Comparativa

Si bien la construcción del autómata es eficiente, el objetivo final es la búsqueda de patrones.

  • Rendimiento del NFA de Thompson: Una vez construido el NFA (con \(O(m)\) estados), puede usarse para buscar coincidencias en un texto \(T\) de longitud \(n\). La simulación directa del NFA (gestionando los conjuntos de estados alcanzables mediante clausura-\(\epsilon\)) toma tiempo \(O(m \times n)\) en el peor de los casos. Esta es una garantía de rendimiento excelente y predecible.

  • Comparativa (Enfoque DFA): Una alternativa es convertir el NFA de Thompson en un Autómata Finito Determinista (DFA) mediante la "construcción de subconjuntos".

    • Ventaja: Un DFA permite búsquedas en tiempo óptimo \(O(n)\) (solo se necesita un recorrido por el texto).
    • Desventaja: En el peor de los casos, la conversión de NFA a DFA puede ser exponencial, generando un DFA con hasta \(O(2^m)\) estadosi\(^4\). Herramientas clásicas como grep a menudo siguen esta ruta (ER \(\rightarrow\) NFA \(\rightarrow\) DFA) para lograr la máxima velocidad de búsqueda.

  • Comparativa (Enfoques de Backtracking): Es crucial distinguir el enfoque de Thompson de los motores de expresiones regulares usados en lenguajes como Perl, Python (el módulo re), o JavaScript\(^5\).

    • *Desventaja: Estos motores comúnmente usan backtracking (vuelta atrás). Aunque son potentes (permiten backreferences), su rendimiento en el peor de los casos puede ser exponencial sobre la longitud del texto (\(O(2^n)\)) para expresiones "malignas", dando lugar a vulnerabilidades de Denegación de Servicio (ReDoS).*
    • Ventaja: El NFA de Thompson (y su posterior conversión a DFA) evita este problema y garantiza un rendimiento acotado (polinómico en el peor caso, \(O(mn)\), o lineal, \(O(n)\), si se convierte a DFA).

Procedimiento

El algoritmo funciona definiendo "bloques de construcción" básicos de las subexpresiones atómicas, para luego combinarlas recursivamente de forma "bottom-up", hasta llegar a la NFA equivalente a la expresión original.

Sean \(I\) el estado inicial y \(F\) el estado final:

  1. Base (Símbolo): Para un símbolo a del alfabeto, el NFA es un estado inicial conectado a un estado de aceptación por una transición etiquetada con a.

nfa1

  1. Unión / Alternación: Para la ER P|Q, el algoritmo toma los NFAs \(N(P)\) y \(N(Q)\):
  2. Crea un nuevo estado inicial.
  3. Añade transiciones épsilon (\(\epsilon\)) desde el nuevo estado inicial a los estados iniciales de \(N(P)\) y \(N(Q)\).
  4. Crea un nuevo estado de aceptación.
  5. Añade transiciones épsilon (\(\epsilon\)) desde los estados de aceptación de \(N(P)\) y \(N(Q)\) al nuevo estado de aceptación.

nfa2

  1. Concatenación: Para la ER PQ, el algoritmo toma los NFAs \(N(P)\) y \(N(Q)\):
  2. El estado inicial de \(N(P)\) se convierte en el estado inicial del nuevo NFA.
  3. El estado de aceptación de \(N(Q)\) se convierte en el estado de aceptación del nuevo NFA.
  4. El estado de aceptación de \(N(P)\) se fusiona con el estado inicial de \(N(Q)\) (o se conectan con una transición \(\epsilon\)).

nfa3

  1. Cierre de Kleene (Estrella): Para la ER P*, el algoritmo toma el NFA \(N(P)\):
  2. Crea un nuevo estado inicial y un nuevo estado de aceptación.
  3. Añade una transición \(\epsilon\) desde el nuevo estado inicial al nuevo estado de aceptación (para manejar el caso de la cadena vacía).
  4. Añade una transición \(\epsilon\) desde el nuevo estado inicial al estado inicial de \(N(P)\).
  5. Añade una transición \(\epsilon\) desde el estado de aceptación de \(N(P)\) al estado inicial de \(N(P)\) (para el bucle).
  6. Añade una transición \(\epsilon\) desde el estado de aceptación de \(N(P)\) al nuevo estado de aceptación.

nfa3

Ejemplo de Procedimiento

Vamos a construir el NFA para la expresión regular (a|b)*a.

Para facilitar la construcción, primero convertimos la ER a notación postfija (RPN), en la cual los operadores binarios se describen después de sus dos operandos (a|b \(\rightarrow\) ab|). También, usaremos . para la concatenación explícita, lo que resulta en ab|*a.

Siguiendo la construcción paso a paso:

  1. a: Creamos el NFA para a.

step1

  1. b: Creamos el NFA para b.

step2

  1. ab| (Unión de a y b): Aplicamos la regla de unión a \(N(a)\) y \(N(b)\).

step3

  1. ab|* (Cierre de Kleene de a|b): Aplicamos la regla de cierre a \(N(a|b)\).

step4

  1. ab|*a (Concatenación con a): Primero, creamos un nuevo NFA para el símbolo a final.

step5

  1. ab|*a. (Concatenación final): Aplicamos la regla de concatenación a \(N((a|b)*)\) (cuyo estado inicial es q6 y de aceptación q7) y \(N(a)\) (con q8 y q9).

step6

El resultado es un NFA completo que reconoce el lenguaje (a|b)*a.

Implementación

Una implementación común utiliza un stack y procesa la expresión regular en notación postfija (RPN). Aquí hay un ejemplo con una expresión simple:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define EPSILON 0

// - Representación NFA

typedef struct Transition {
    int symbol;               // Símbolo (EPSILON o un char)
    struct State *next_state; // Estado al que apunta
    struct Transition *next;  // Siguiente transición desde el mismo estado
} Transition;

typedef struct State {
    int is_accept;           // 0 = no, 1 = sí
    Transition *transitions; // Linked list de transiciones
} State;

// Fragmento / subgrafo
typedef struct NFAFragment {
    State *start_state;
    State *accept_state;
} NFAFragment;


// - Representación de simulación

#define MAX_STATES_IN_SET 256

typedef struct {
    State *states[MAX_STATES_IN_SET];
    int count;
} StateSet;

void clearSet(StateSet *set) {
    set->count = 0;
}

int addStateToSet(StateSet *set, State *state) {
    if (state == NULL)
        return 0;
    for (int i = 0; i < set->count; i++) {
        if (set->states[i] == state) {
            return 0; // Ya está en el set
        }
    }
    if (set->count < MAX_STATES_IN_SET) {
        set->states[set->count++] = state;
        return 1; // Añadido
    } else {
        fprintf(stderr, "Error: Set de estados lleno\n");
        return 0;
    }
}

int containsState(StateSet *set, State *state) {
    for (int i = 0; i < set->count; i++) {
        if (set->states[i] == state) {
            return 1;
        }
    }
    return 0;
}


// - Construcción Thompson NFA

State *createState(int is_accept) {
    State *state = (State *)malloc(sizeof(State));
    if (state == NULL) {
        fprintf(stderr, "Error: malloc falló\n");
        exit(1);
    }
    state->is_accept = is_accept;
    state->transitions = NULL;
    return state;
}

void addTransition(State *from, int symbol, State *to) {
    Transition *t = (Transition *)malloc(sizeof(Transition));
    if (t == NULL) {
        fprintf(stderr, "Error: malloc falló\n");
        exit(1);
    }
    t->symbol = symbol;
    t->next_state = to;
    t->next = from->transitions;
    from->transitions = t;
}

NFAFragment *createFragment(State *start, State *accept) {
    NFAFragment *f = (NFAFragment *)malloc(sizeof(NFAFragment));
    if (f == NULL) {
        fprintf(stderr, "Error: malloc falló\n");
        exit(1);
    }
    f->start_state = start;
    f->accept_state = accept;
    return f;
}

NFAFragment *build_nfa_symbol(int symbol) {
    State *accept = createState(1);
    State *start = createState(0);
    addTransition(start, symbol, accept);
    return createFragment(start, accept);
}

NFAFragment *build_nfa_concat(NFAFragment *f1, NFAFragment *f2) {
    addTransition(f1->accept_state, EPSILON, f2->start_state);
    f1->accept_state->is_accept = 0;
    NFAFragment *f = createFragment(f1->start_state, f2->accept_state);
    free(f1);
    free(f2);
    return f;
}

NFAFragment *build_nfa_union(NFAFragment *f1, NFAFragment *f2) {
    State *start = createState(0);
    State *accept = createState(1);
    addTransition(start, EPSILON, f1->start_state);
    addTransition(start, EPSILON, f2->start_state);
    f1->accept_state->is_accept = 0;
    f2->accept_state->is_accept = 0;
    addTransition(f1->accept_state, EPSILON, accept);
    addTransition(f2->accept_state, EPSILON, accept);
    NFAFragment *f = createFragment(start, accept);
    free(f1);
    free(f2);
    return f;
}

NFAFragment *build_nfa_star(NFAFragment *f1) {
    State *start = createState(0);
    State *accept = createState(1);
    addTransition(start, EPSILON, accept); // 0 ocurrencias
    addTransition(start, EPSILON, f1->start_state);
    f1->accept_state->is_accept = 0;
    addTransition(f1->accept_state, EPSILON, f1->start_state); // Bucle
    addTransition(f1->accept_state, EPSILON, accept);
    NFAFragment *f = createFragment(start, accept);
    free(f1);
    return f;
}

// - Stack utilizado

#define MAX_STACK_SIZE 100

typedef struct {
    NFAFragment *fragments[MAX_STACK_SIZE];
    int top;
} NFAStack;

void push(NFAStack *stack, NFAFragment *f) {
    if (stack->top < MAX_STACK_SIZE) {
        stack->fragments[stack->top++] = f;
    } else {
        fprintf(stderr, "Error: Stack overflow\n");
        exit(1);
    }
}

NFAFragment *pop(NFAStack *stack) {
    if (stack->top > 0) {
        return stack->fragments[--stack->top];
    } else {
        fprintf(stderr, "Error: Stack underflow\n");
        exit(1);
    }
}

// - Función principal de construcción

NFAFragment *regex_to_nfa(const char *postfix_regex) {
    NFAStack stack;
    stack.top = 0;
    NFAFragment *f1, *f2;
    for (int i = 0; postfix_regex[i] != '\0'; i++) {
        char c = postfix_regex[i];
        switch (c) {
        case '|':
            f2 = pop(&stack);
            f1 = pop(&stack);
            push(&stack, build_nfa_union(f1, f2));
            break;
        case '.':
            f2 = pop(&stack);
            f1 = pop(&stack);
            push(&stack, build_nfa_concat(f1, f2));
            break;
        case '*':
            f1 = pop(&stack);
            push(&stack, build_nfa_star(f1));
            break;
        default: push(&stack, build_nfa_symbol(c)); break;
        }
    }
    return pop(&stack);
}


// Función recursiva para calcular la clausura épsilon
void _epsilon_closure_recursive(State *state, StateSet *closure) {
    if (addStateToSet(closure, state)) {
        for (Transition *t = state->transitions; t != NULL; t = t->next) {
            if (t->symbol == EPSILON) {
                _epsilon_closure_recursive(t->next_state, closure);
            }
        }
    }
}

// Calcula la clausura épsilon de un conjunto de estados
void epsilon_closure(StateSet *input, StateSet *output) {
    clearSet(output);
    for (int i = 0; i < input->count; i++) {
        _epsilon_closure_recursive(input->states[i], output);
    }
}

// Calcula el conjunto de estados alcanzables con un símbolo
void move(StateSet *input, int symbol, StateSet *output) {
    clearSet(output);
    for (int i = 0; i < input->count; i++) {
        State *s = input->states[i];
        for (Transition *t = s->transitions; t != NULL; t = t->next) {
            if (t->symbol == symbol) {
                addStateToSet(output, t->next_state);
            }
        }
    }
}

// Simula el NFA con una cadena de entrada
int simulate_nfa(NFAFragment *nfa, const char *input) {
    StateSet current_states, next_states, temp_set;

    // Estado inicial: clausura épsilon del estado inicial del NFA
    clearSet(&temp_set);
    addStateToSet(&temp_set, nfa->start_state);
    epsilon_closure(&temp_set, &current_states);

    // Procesar cada carácter de la cadena
    for (int i = 0; input[i] != '\0'; i++) {
        char c = input[i];
        move(&current_states, c, &next_states);
        epsilon_closure(&next_states, &current_states);

        if (current_states.count == 0) {
            return 0; // Camino muerto
        }
    }

    // Al final, comprobar si el estado de aceptación está en el conjunto final
    return containsState(&current_states, nfa->accept_state);
}

void _free_nfa_recursive(State *state, StateSet *visited) {
    if (state == NULL || !addStateToSet(visited, state)) {
        return; // Ya visitado o nulo
    }

    Transition *t = state->transitions;
    while (t != NULL) {
        _free_nfa_recursive(t->next_state, visited);
        Transition *old_t = t;
        t = t->next;
        free(old_t);
    }
    free(state);
}

void free_nfa(NFAFragment *nfa) {
    StateSet visited;
    clearSet(&visited);
    _free_nfa_recursive(nfa->start_state, &visited);
    free(nfa); // Liberar el contenedor del fragmento
}

int main() {
    // ER: (a|b)*a -> Postfix: ab|*a.
    const char *postfix_expr = "ab|*a.";
    NFAFragment *final_nfa = regex_to_nfa(postfix_expr);

    printf("NFA construido para la ER:\n\t(a|b)*a\n");

    printf("Pruebas de strings:\n");
    const char *test_strings[] = {"a", "aa", "ba", "b", "ab", "bab", "bbba", "bba", "aaaa", ""};
    int num_tests = sizeof(test_strings) / sizeof(test_strings[0]);
    for (int i = 0; i < num_tests; i++) { int result = simulate_nfa(final_nfa, test_strings[i]);
        printf("\tString: \"%-6s\" -> %s\n", test_strings[i], result ? "Aceptada" : "Rechazada");
    }

    free_nfa(final_nfa);

    return 0;
}

Referencias

  1. Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning.

  2. Thompson, K. (1968). Regular expression search algorithm. Communications of the ACM, 11(6), 419-422. Archivo

  3. Ritchie, Dennis M. (1999). An incomplete history of the QED Text Editor. Archivo

  4. Russ Cox (2007). Regular Expression Matching Can Be Simple And Fast. Enlace

  5. Navarro, G., & Raffinot, M. (2002). Flexible Pattern Matching in Strings. Cambridge University Press.