Semana 3 — Expresiones regulares

Objetivos

  • Leer y escribir expresiones regulares con unión, concatenación y estrella, y decir qué lenguaje describen.
  • Convertir una expresión regular en un NFA con la construcción de Thompson.
  • Convertir un DFA en una expresión regular eliminando estados.
  • Enunciar el teorema de Kleene y explicar por qué las expresiones de las herramientas reales no siempre son regulares.

Sesión A — Expresiones regulares · De expresión regular a NFA

Lectura: Apuntes, semana 3.

Apoyo: Sipser, sec. 1.3 (Regular Expressions). Erickson, Models of Computation, nota 2 (Regular languages).

Temas:

  • Describir un lenguaje en vez de dar una máquina que lo reconoce. grep, los validadores de formularios y los lexers de los compiladores.
  • Definición inductiva: ∅\emptyset, ε\varepsilon, un símbolo, unión, concatenación y estrella. Precedencia: estrella, concatenación, unión.
  • Leer expresiones: (0∪1)∗1(\mathtt{0} \cup \mathtt{1})^*\mathtt{1}, (ΣΣ)∗(\Sigma\Sigma)^*, 0∗10∗10∗\mathtt{0}^*\mathtt{1}\mathtt{0}^*\mathtt{1}\mathtt{0}^*. Escribirlas: cadenas con un número par de ceros, cadenas sin 11.
  • Identidades útiles y trampas: R∪∅=RR \cup \emptyset = R, R∅=∅R\emptyset = \emptyset, ∅∗={ε}\emptyset^* = \{\varepsilon\}.
  • De expresión regular a NFA: una construcción por cada caso de la definición, que son las de cierre de la semana 2. Construcción de Thompson.
  • El NFA resultante tiene un número de estados lineal en el tamaño de la expresión.
  • Abreviaturas de las herramientas (+, ?, [a-z], {n,m}) y por qué no agregan poder.
  • Error común: escribir una expresión que acepta lo pedido y también cadenas que no debía. Se prueba con cadenas de los dos lados.

Sesión B — De DFA a expresión regular: el teorema de Kleene

Lectura: Apuntes, semana 3.

Apoyo: Sipser, sec. 1.3, la segunda mitad: los autómatas generalizados (GNFA). Erickson, Models of Computation, nota 4.

Temas:

  • La dirección difícil: de una máquina a una descripción.
  • Autómatas con expresiones regulares en las flechas. Normalizar: un estado inicial nuevo y uno solo de aceptación.
  • Eliminar un estado: la flecha de ii a jj pasa a ser Rij∪Rik(Rkk)∗RkjR_{ij} \cup R_{ik} (R_{kk})^* R_{kj}. Ejemplo completo con un DFA de tres estados.
  • El orden de eliminación cambia la expresión que sale, no el lenguaje. Las expresiones crecen rápido.
  • Teorema de Kleene: DFA, NFA y expresiones regulares describen los mismos lenguajes. El triángulo de conversiones del curso.
  • Cómo busca un motor real: simular el NFA con el conjunto de estados activos, en tiempo O(nm)O(nm), frente al backtracking, que puede tardar un tiempo exponencial.
  • Las referencias hacia atrás (\1) no son regulares: se demuestra en la semana 4.
  • Error común: al eliminar un estado, olvidar el ciclo sobre sí mismo o alguna de las parejas (i,j)(i, j).

Laboratorio — Un grep pequeño

  1. Leer una expresión regular con |, concatenación, * y paréntesis, y una lista de líneas; responder por cada una si la expresión la acepta completa.
  2. Construir el árbol de la expresión respetando la precedencia.
  3. Convertirlo en un NFA con la construcción de Thompson.
  4. Decidir cada línea simulando el NFA con el conjunto de estados activos, sin backtracking.
  5. Pasar el caso grande: la expresión (a|a)*b contra una cadena larga de a, que hace exponencial a una búsqueda con backtracking.

Preguntas de repaso

  1. ¿Qué lenguajes describen (0∪ε)1∗(\mathtt{0} \cup \varepsilon)\mathtt{1}^* y (01)∗∪(10)∗(\mathtt{01})^* \cup (\mathtt{10})^*? Den dos cadenas dentro y dos fuera de cada uno.
  2. Escriban una expresión regular para las cadenas binarias con un número de ceros múltiplo de 3.
  3. Conviertan (ab∪a)∗(\mathtt{ab} \cup \mathtt{a})^* en un NFA con la construcción de la clase.
  4. Eliminen los estados de un DFA de dos estados en los dos órdenes posibles y comprueben que las expresiones son equivalentes.
  5. ¿Por qué simular el NFA cuesta O(nm)O(nm) y el backtracking puede costar un tiempo exponencial con la misma expresión?

Código de la semana

Compilar y probar dentro del contenedor del curso con make y make test.

Ejemplos (23)Errores (1)Pruebas (4)Laboratorio (3)Compilación (1)

Ejemplos

Los programas que usan los apuntes y la clase.

backtrack.cppDescargar backtrack.cpp
// Busca con backtracking: backtrack EXPRESIÓN CADENA...
// Dice si la expresión describe cada cadena completa y cuántas llamadas hizo la búsqueda.
#include <iostream>
#include <stdexcept>
#include <string>

#include "backtrack.h"
#include "regex.h"
#include "words.h"

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cerr << "uso: backtrack EXPRESIÓN CADENA...\n";
        return 2;
    }
    try {
        RegexPtr r = parse_regex(argv[1]);
        for (int i = 2; i < argc; i++) {
            std::string w = argv[i];
            long long calls = 0;
            bool found = backtrack_accepts(r, w, &calls);
            std::cout << show(w) << ": " << (found ? "acepta" : "rechaza") << ", " << calls << " llamadas\n";
        }
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
backtrack.hDescargar backtrack.h
// Un buscador con backtracking: recorre el árbol de la expresión y prueba las alternativas
// una por una. Cuando una falla, vuelve atrás y prueba la siguiente.
// Es correcto, y con algunas expresiones tarda un tiempo exponencial en la longitud de la
// cadena: está aquí para compararlo con la simulación del NFA.
#ifndef BACKTRACK_H
#define BACKTRACK_H

#include <cstddef>
#include <functional>
#include <string>

#include "regex.h"

struct Backtracker {
    std::string w;
    long long calls = 0;  // cuántas veces se llamó a match

    // ¿Se puede leer con r un tramo de w que empieza en pos, de modo que lo que sigue (rest)
    // acepte desde donde r terminó?
    bool match(const RegexPtr& r, std::size_t pos, const std::function<bool(std::size_t)>& rest) {
        calls++;
        switch (r->kind) {
            case Kind::Empty:
                return false;
            case Kind::Epsilon:
                return rest(pos);
            case Kind::Symbol:
                return pos < w.size() && w[pos] == r->symbol && rest(pos + 1);
            case Kind::Union:
                // Primero la alternativa izquierda; si falla, la derecha.
                return match(r->left, pos, rest) || match(r->right, pos, rest);
            case Kind::Concat:
                return match(r->left, pos, [&](std::size_t middle) { return match(r->right, middle, rest); });
            case Kind::Star:
                // Primero intenta una vuelta más y, si falla, sale de la estrella. Una vuelta
                // que no avanza no se cuenta: sin esa condición, (a*)* no terminaría.
                return match(r->left, pos,
                             [&](std::size_t middle) { return middle > pos && match(r, middle, rest); }) ||
                       rest(pos);
        }
        return false;
    }
};

// ¿Describe r la cadena w completa? Devuelve además cuántas llamadas hizo.
inline bool backtrack_accepts(const RegexPtr& r, const std::string& w, long long* calls = nullptr) {
    Backtracker search{w};
    bool found = search.match(r, 0, [&](std::size_t end) { return end == w.size(); });
    if (calls != nullptr) {
        *calls = search.calls;
    }
    return found;
}

#endif
dfa.hDescargar dfa.h
// Autómata finito determinista. El struct tiene los cinco componentes de la definición
// M = (Q, Σ, δ, q0, F), con los nombres del formato .dfa de code/formats.md.
// Es una copia de code/week-01/dfa.h, sin cambios, para que esta carpeta no dependa de otra.
// Además: leer y escribir ese formato, la función de transición extendida, la construcción
// del producto y el complemento.
#ifndef DFA_H
#define DFA_H

#include <cstddef>
#include <fstream>
#include <istream>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

struct Dfa {
    std::vector<std::string> states;                            // Q, en el orden del archivo
    std::vector<char> alphabet;                                 // Σ
    std::map<std::pair<std::string, char>, std::string> delta;  // δ : Q × Σ → Q
    std::string start;                                          // q0
    std::set<std::string> accept;                               // F ⊆ Q
};

// ------------------------------------------------------------
// Comprobar que la quíntupla es un DFA
// ------------------------------------------------------------

// Lanza std::runtime_error si m no cumple la definición. Lo más importante: δ es total.
inline void check_dfa(const Dfa& m) {
    std::set<std::string> q(m.states.begin(), m.states.end());
    std::set<char> sigma(m.alphabet.begin(), m.alphabet.end());
    if (m.states.empty()) {
        throw std::runtime_error("Q no puede ser vacío");
    }
    if (q.size() != m.states.size()) {
        throw std::runtime_error("hay un estado repetido en states");
    }
    if (m.alphabet.empty()) {
        throw std::runtime_error("el alfabeto no puede ser vacío");
    }
    if (sigma.size() != m.alphabet.size()) {
        throw std::runtime_error("hay un símbolo repetido en alphabet");
    }
    if (q.count(m.start) == 0) {
        throw std::runtime_error("el estado inicial " + m.start + " no está en states");
    }
    for (const std::string& f : m.accept) {
        if (q.count(f) == 0) {
            throw std::runtime_error("el estado de aceptación " + f + " no está en states");
        }
    }
    for (const auto& [key, target] : m.delta) {
        if (q.count(key.first) == 0) {
            throw std::runtime_error("transición desde " + key.first + ", que no está en states");
        }
        if (sigma.count(key.second) == 0) {
            throw std::runtime_error(std::string("transición con ") + key.second + ", que no está en alphabet");
        }
        if (q.count(target) == 0) {
            throw std::runtime_error("transición hacia " + target + ", que no está en states");
        }
    }
    for (const std::string& state : m.states) {
        for (char a : m.alphabet) {
            if (m.delta.count({state, a}) == 0) {
                throw std::runtime_error("falta la transición δ(" + state + ", " + a + "): en un DFA, δ es total");
            }
        }
    }
}

// ------------------------------------------------------------
// Leer y escribir el formato .dfa
// ------------------------------------------------------------

inline std::vector<std::string> split_words(const std::string& text) {
    std::istringstream in(text);
    std::vector<std::string> words;
    std::string word;
    while (in >> word) {
        words.push_back(word);
    }
    return words;
}

// Lee una descripción completa, hasta el final de la entrada.
inline Dfa read_dfa(std::istream& in) {
    int number = 0;
    auto fail = [&number](const std::string& message) {
        throw std::runtime_error("línea " + std::to_string(number) + ": " + message);
    };
    // Siguiente línea que no es comentario ni está vacía. Devuelve false al final.
    auto next_line = [&in, &number](std::vector<std::string>& words) {
        std::string line;
        while (std::getline(in, line)) {
            number++;
            if (!line.empty() && line[0] == '#') {
                continue;
            }
            words = split_words(line);
            if (!words.empty()) {
                return true;
            }
        }
        return false;
    };
    // Un campo: "nombre: valor valor ...". Devuelve los valores.
    auto field = [&next_line, &fail](const std::string& name) {
        std::vector<std::string> words;
        if (!next_line(words) || words[0] != name + ":") {
            fail("se esperaba el campo " + name + ":");
        }
        words.erase(words.begin());
        return words;
    };

    Dfa m;
    m.states = field("states");
    for (const std::string& symbol : field("alphabet")) {
        if (symbol.size() != 1 || symbol[0] == '#') {
            fail("un símbolo es un solo carácter distinto de #: " + symbol);
        }
        m.alphabet.push_back(symbol[0]);
    }
    std::vector<std::string> start = field("start");
    if (start.size() != 1) {
        fail("start: lleva exactamente un estado");
    }
    m.start = start[0];
    for (const std::string& state : field("accept")) {
        m.accept.insert(state);
    }
    if (!field("delta").empty()) {
        fail("después de delta: las transiciones van una por línea");
    }
    std::vector<std::string> words;
    while (next_line(words)) {
        if (words.size() != 3 || words[1].size() != 1) {
            fail("una transición se escribe: estado símbolo destino");
        }
        std::pair<std::string, char> key = {words[0], words[1][0]};
        if (m.delta.count(key) > 0) {
            fail("transición repetida para δ(" + words[0] + ", " + words[1] + "): en un DFA hay una sola");
        }
        m.delta[key] = words[2];
    }
    check_dfa(m);
    return m;
}

inline Dfa load_dfa(const std::string& path) {
    std::ifstream file(path);
    if (!file) {
        throw std::runtime_error("no se pudo abrir " + path);
    }
    try {
        return read_dfa(file);
    } catch (const std::runtime_error& error) {
        throw std::runtime_error(path + ": " + error.what());
    }
}

// Escribe m en el formato .dfa: lo que escribe se puede volver a leer con read_dfa.
inline void write_dfa(std::ostream& out, const Dfa& m) {
    out << "states:";
    for (const std::string& state : m.states) {
        out << ' ' << state;
    }
    out << "\nalphabet:";
    for (char a : m.alphabet) {
        out << ' ' << a;
    }
    out << "\nstart: " << m.start << "\naccept:";
    for (const std::string& state : m.states) {
        if (m.accept.count(state) > 0) {
            out << ' ' << state;
        }
    }
    out << "\ndelta:\n";
    for (const std::string& state : m.states) {
        for (char a : m.alphabet) {
            out << state << ' ' << a << ' ' << m.delta.at({state, a}) << '\n';
        }
    }
}

// ------------------------------------------------------------
// Ejecutar
// ------------------------------------------------------------

// Un paso: δ(q, a).
inline const std::string& step(const Dfa& m, const std::string& q, char a) {
    auto it = m.delta.find({q, a});
    if (it == m.delta.end()) {
        throw std::runtime_error("δ(" + q + ", " + a + ") no está definida");
    }
    return it->second;
}

// La función de transición extendida: δ*(q, ε) = q y δ*(q, wa) = δ(δ*(q, w), a).
// El ciclo aplica la segunda línea de la definición una vez por símbolo, de izquierda a derecha.
inline std::string delta_star(const Dfa& m, std::string q, const std::string& w) {
    for (char a : w) {
        q = step(m, q, a);
    }
    return q;
}

// M acepta w si δ*(q0, w) ∈ F.
inline bool accepts(const Dfa& m, const std::string& w) {
    return m.accept.count(delta_star(m, m.start, w)) > 0;
}

// La ejecución de M con w: los estados r0, r1, …, rn, con r0 = q0 y r(i+1) = δ(r(i), w(i+1)).
inline std::vector<std::string> run(const Dfa& m, const std::string& w) {
    std::vector<std::string> sequence = {m.start};
    for (char a : w) {
        sequence.push_back(step(m, sequence.back(), a));
    }
    return sequence;
}

// Los estados a los que se llega desde q0 con alguna cadena.
inline std::set<std::string> reachable(const Dfa& m) {
    std::set<std::string> seen = {m.start};
    std::queue<std::string> pending;
    pending.push(m.start);
    while (!pending.empty()) {
        std::string q = pending.front();
        pending.pop();
        for (char a : m.alphabet) {
            const std::string& next = step(m, q, a);
            if (seen.insert(next).second) {
                pending.push(next);
            }
        }
    }
    return seen;
}

// ------------------------------------------------------------
// Construcciones
// ------------------------------------------------------------

enum class Combine { Intersection, Union };

// El nombre del estado (p, q) del producto. Los nombres del formato no llevan espacios.
inline std::string pair_name(const std::string& p, const std::string& q) {
    return "(" + p + "," + q + ")";
}

// Construcción del producto: Q = Q1 × Q2, δ((p, q), a) = (δ1(p, a), δ2(q, a)), q0 = (q1, q2).
// Para la intersección, F = F1 × F2. Para la unión, F = (F1 × Q2) ∪ (Q1 × F2).
inline Dfa product(const Dfa& m1, const Dfa& m2, Combine mode) {
    std::set<char> sigma1(m1.alphabet.begin(), m1.alphabet.end());
    std::set<char> sigma2(m2.alphabet.begin(), m2.alphabet.end());
    if (sigma1 != sigma2) {
        throw std::runtime_error("el producto necesita dos DFA con el mismo alfabeto");
    }
    Dfa m;
    m.alphabet = m1.alphabet;
    m.start = pair_name(m1.start, m2.start);
    for (const std::string& p : m1.states) {
        for (const std::string& q : m2.states) {
            std::string name = pair_name(p, q);
            m.states.push_back(name);
            bool in1 = m1.accept.count(p) > 0;
            bool in2 = m2.accept.count(q) > 0;
            bool accepting = (mode == Combine::Intersection) ? (in1 && in2) : (in1 || in2);
            if (accepting) {
                m.accept.insert(name);
            }
            for (char a : m.alphabet) {
                m.delta[{name, a}] = pair_name(step(m1, p, a), step(m2, q, a));
            }
        }
    }
    check_dfa(m);  // también detecta dos pares con el mismo nombre, si los nombres traían comas
    return m;
}

// Complemento: la misma máquina con F cambiado por Q − F.
inline Dfa complement(const Dfa& m) {
    Dfa result = m;
    result.accept.clear();
    for (const std::string& state : m.states) {
        if (m.accept.count(state) == 0) {
            result.accept.insert(state);
        }
    }
    return result;
}

// La misma máquina sin los estados inalcanzables. Reconoce el mismo lenguaje.
inline Dfa remove_unreachable(const Dfa& m) {
    std::set<std::string> keep = reachable(m);
    Dfa result;
    result.alphabet = m.alphabet;
    result.start = m.start;
    for (const std::string& state : m.states) {
        if (keep.count(state) == 0) {
            continue;
        }
        result.states.push_back(state);
        if (m.accept.count(state) > 0) {
            result.accept.insert(state);
        }
        for (char a : m.alphabet) {
            result.delta[{state, a}] = step(m, state, a);
        }
    }
    return result;
}

#endif
eliminate.cppDescargar eliminate.cpp
// De DFA a expresión regular eliminando estados: eliminate ARCHIVO.dfa [ESTADO...]
// Los estados se eliminan en el orden en que se nombran; sin nombres, en el orden del archivo.
// Muestra las flechas del autómata generalizado al empezar y después de cada eliminación.
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

#include "dfa.h"
#include "gnfa.h"
#include "regex.h"

static void show_gnfa(const Gnfa& g) {
    std::cout << "  estados:";
    for (const std::string& q : g.states) {
        std::cout << ' ' << q;
    }
    std::cout << '\n';
    for (const std::string& i : g.states) {
        for (const std::string& j : g.states) {
            auto it = g.arrow.find({i, j});
            if (it != g.arrow.end()) {
                std::cout << "  " << i << " -> " << j << " :  " << to_string(it->second) << '\n';
            }
        }
    }
}

int main(int argc, char** argv) {
    if (argc < 2) {
        std::cerr << "uso: eliminate ARCHIVO.dfa [ESTADO...]\n";
        return 2;
    }
    try {
        Dfa m = load_dfa(argv[1]);
        std::vector<std::string> order(argv + 2, argv + argc);
        if (order.empty()) {
            order = m.states;
        }
        RegexPtr result = to_regex(m, order);  // también revisa que el orden esté completo
        Gnfa g = to_gnfa(m);
        std::cout << "Autómata generalizado de " << argv[1] << '\n';
        show_gnfa(g);
        for (const std::string& k : order) {
            g = eliminate(g, k);
            std::cout << "\nSe elimina " << k << '\n';
            show_gnfa(g);
        }
        std::cout << "\nExpresión: " << to_string(result) << '\n';
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
gnfa.hDescargar gnfa.h
// Autómata finito no determinista generalizado (GNFA): las flechas llevan expresiones
// regulares en lugar de símbolos. Sirve para convertir un DFA en una expresión regular
// eliminando sus estados de uno en uno.
#ifndef GNFA_H
#define GNFA_H

#include <map>
#include <set>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

#include "dfa.h"
#include "regex.h"

struct Gnfa {
    std::vector<std::string> states;                                 // Q, con start y accept
    std::string start;                                               // no le entra ninguna flecha
    std::string accept;                                              // no le sale ninguna flecha
    std::map<std::pair<std::string, std::string>, RegexPtr> arrow;   // la expresión de i a j
};

// La expresión de la flecha de i a j. Una flecha que no está dibujada lleva ∅.
inline RegexPtr label(const Gnfa& g, const std::string& i, const std::string& j) {
    auto it = g.arrow.find({i, j});
    return it == g.arrow.end() ? empty_set() : it->second;
}

// Un nombre que no esté usado: base, o base con apóstrofos.
inline std::string fresh_name(const std::set<std::string>& used, std::string base) {
    while (used.count(base) > 0) {
        base += "'";
    }
    return base;
}

// Normalizar: un estado inicial nuevo con una flecha ε al inicial del DFA, y un único estado
// de aceptación nuevo al que llega una flecha ε desde cada estado de aceptación del DFA.
// Las flechas del DFA entre dos mismos estados se juntan en una sola, con la unión de sus
// símbolos.
inline Gnfa to_gnfa(const Dfa& m) {
    std::set<std::string> used(m.states.begin(), m.states.end());
    Gnfa g;
    g.start = fresh_name(used, "ini");
    used.insert(g.start);
    g.accept = fresh_name(used, "fin");
    g.states.push_back(g.start);
    g.states.insert(g.states.end(), m.states.begin(), m.states.end());
    g.states.push_back(g.accept);
    g.arrow[{g.start, m.start}] = epsilon();
    for (const std::string& q : m.states) {
        if (m.accept.count(q) > 0) {
            g.arrow[{q, g.accept}] = epsilon();
        }
        for (char a : m.alphabet) {
            const std::string& target = step(m, q, a);
            g.arrow[{q, target}] = simple_union(label(g, q, target), symbol(a));
        }
    }
    return g;
}

// Eliminar el estado k. Para cada pareja (i, j) de los estados que quedan, la flecha nueva es
//     R(i, j) ∪ R(i, k) R(k, k)* R(k, j)
// Las operaciones aplican las identidades de ∅ y de ε, para no arrastrar términos vacíos.
inline Gnfa eliminate(const Gnfa& g, const std::string& k) {
    if (k == g.start || k == g.accept) {
        throw std::runtime_error("no se elimina el estado inicial ni el de aceptación");
    }
    Gnfa result;
    result.start = g.start;
    result.accept = g.accept;
    for (const std::string& q : g.states) {
        if (q != k) {
            result.states.push_back(q);
        }
    }
    if (result.states.size() == g.states.size()) {
        throw std::runtime_error("el estado " + k + " no está en el autómata");
    }
    RegexPtr loop = simple_star(label(g, k, k));
    for (const std::string& i : result.states) {
        if (i == g.accept) {
            continue;  // del estado de aceptación no sale nada
        }
        for (const std::string& j : result.states) {
            if (j == g.start) {
                continue;  // al estado inicial no entra nada
            }
            RegexPtr through = simple_concat(simple_concat(label(g, i, k), loop), label(g, k, j));
            RegexPtr merged = simple_union(label(g, i, j), through);
            if (merged->kind != Kind::Empty) {
                result.arrow[{i, j}] = merged;
            }
        }
    }
    return result;
}

// De DFA a expresión regular, eliminando los estados en el orden dado.
// El orden debe nombrar cada estado del DFA exactamente una vez.
inline RegexPtr to_regex(const Dfa& m, const std::vector<std::string>& order) {
    std::set<std::string> named(order.begin(), order.end());
    std::set<std::string> all(m.states.begin(), m.states.end());
    if (order.size() != m.states.size() || named != all) {
        throw std::runtime_error("el orden debe nombrar cada estado una vez");
    }
    Gnfa g = to_gnfa(m);
    for (const std::string& k : order) {
        g = eliminate(g, k);
    }
    return label(g, g.start, g.accept);
}

#endif
growth.cppDescargar growth.cpp
// Cuánto crece la expresión al eliminar estados: growth [K_MÁXIMO]
// Para cada k construye el DFA de k estados de los múltiplos de k en binario (el de la
// semana 1 con k = 3), elimina sus estados en el orden r0, r1, … y en el orden inverso, y
// cuenta los nodos de la expresión que sale.
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>

#include "dfa.h"
#include "gnfa.h"
#include "regex.h"

// El estado rI dice que el valor de lo leído deja resto I al dividir entre k.
// Leer el bit b cambia el valor v por 2v + b.
static Dfa multiples_of(int k) {
    Dfa m;
    m.alphabet = {'0', '1'};
    for (int i = 0; i < k; i++) {
        m.states.push_back("r" + std::to_string(i));
    }
    m.start = "r0";
    m.accept = {"r0"};
    for (int i = 0; i < k; i++) {
        m.delta[{m.states[i], '0'}] = m.states[(2 * i) % k];
        m.delta[{m.states[i], '1'}] = m.states[(2 * i + 1) % k];
    }
    check_dfa(m);
    return m;
}

int main(int argc, char** argv) {
    int max_k = (argc == 2) ? std::stoi(argv[1]) : 8;
    std::cout << " k   estados   nodos (r0 primero)   nodos (r0 al final)\n";
    for (int k = 2; k <= max_k; k++) {
        Dfa m = multiples_of(k);
        std::vector<std::string> forward = m.states;
        std::vector<std::string> backward(m.states.rbegin(), m.states.rend());
        std::size_t a = size(to_regex(m, forward));
        std::size_t b = size(to_regex(m, backward));
        std::cout.width(2);
        std::cout << k;
        std::cout.width(10);
        std::cout << k;
        std::cout.width(21);
        std::cout << a;
        std::cout.width(22);
        std::cout << b << '\n';
    }
}
matchers_bench.cppDescargar matchers_bench.cpp
// Backtracking frente a simulación del NFA, con el caso malo: (a|a)*b contra a^n.
// La cadena no tiene ninguna b, así que la respuesta siempre es "rechaza".
// Cuenta las llamadas del backtracking y mide el tiempo de las dos búsquedas.
// Se compila con -O2 y sin sanitizers: make bench.
#include <chrono>
#include <cstddef>
#include <cstdio>
#include <string>
#include <vector>

#include "backtrack.h"
#include "nfa.h"
#include "regex.h"
#include "thompson.h"

static double seconds_since(std::chrono::steady_clock::time_point start) {
    return std::chrono::duration<double>(std::chrono::steady_clock::now() - start).count();
}

int main() {
    RegexPtr r = parse_regex("(a|a)*b");
    Nfa n = thompson(r);
    std::printf("expresión: (a|a)*b    cadena: a^n    NFA de Thompson: %zu estados\n\n", n.states.size());
    std::printf("      n   backtracking: llamadas   backtracking: tiempo   NFA: tiempo\n");
    std::vector<std::size_t> lengths = {5, 10, 15, 20, 25};
    for (std::size_t length : lengths) {
        std::string w(length, 'a');
        long long calls = 0;
        auto t0 = std::chrono::steady_clock::now();
        bool by_backtracking = backtrack_accepts(r, w, &calls);
        double backtracking_time = seconds_since(t0);
        auto t1 = std::chrono::steady_clock::now();
        bool by_nfa = accepts(n, w);
        double nfa_time = seconds_since(t1);
        if (by_backtracking || by_nfa) {
            std::printf("error: alguna de las dos búsquedas aceptó\n");
            return 1;
        }
        std::printf("%7zu   %22lld   %18.4f s   %9.4f s\n", length, calls, backtracking_time, nfa_time);
    }
    // Solo el NFA: con estas longitudes el backtracking no termina.
    for (std::size_t length : {1000, 100000}) {
        std::string w(length, 'a');
        auto t1 = std::chrono::steady_clock::now();
        bool by_nfa = accepts(n, w);
        double nfa_time = seconds_since(t1);
        if (by_nfa) {
            std::printf("error: el NFA aceptó\n");
            return 1;
        }
        std::printf("%7zu   %22s   %20s   %9.4f s\n", length, "-", "-", nfa_time);
    }
}
nfa.hDescargar nfa.h
// Autómata finito no determinista, con transiciones ε. El struct tiene los cinco componentes
// de la definición N = (Q, Σ, δ, q0, F), con los nombres del formato .nfa de code/formats.md.
// Además: leer y escribir ese formato, la clausura ε y la simulación con el conjunto de
// estados activos.
#ifndef NFA_H
#define NFA_H

#include <cstddef>
#include <fstream>
#include <istream>
#include <map>
#include <ostream>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

// En δ, una transición ε se guarda con este carácter en el lugar del símbolo.
const char EPS = '\0';

using StateSet = std::set<std::string>;

struct Nfa {
    std::vector<std::string> states;                         // Q, en el orden del archivo
    std::vector<char> alphabet;                              // Σ
    std::map<std::pair<std::string, char>, StateSet> delta;  // δ : Q × (Σ ∪ {ε}) → P(Q)
    std::string start;                                       // q0
    StateSet accept;                                         // F ⊆ Q
};

// ------------------------------------------------------------
// Comprobar que la quíntupla es un NFA
// ------------------------------------------------------------

inline void check_nfa(const Nfa& n) {
    StateSet q(n.states.begin(), n.states.end());
    std::set<char> sigma(n.alphabet.begin(), n.alphabet.end());
    if (n.states.empty()) {
        throw std::runtime_error("Q no puede ser vacío");
    }
    if (q.size() != n.states.size()) {
        throw std::runtime_error("hay un estado repetido en states");
    }
    if (n.alphabet.empty()) {
        throw std::runtime_error("el alfabeto no puede ser vacío");
    }
    if (sigma.size() != n.alphabet.size()) {
        throw std::runtime_error("hay un símbolo repetido en alphabet");
    }
    if (q.count(n.start) == 0) {
        throw std::runtime_error("el estado inicial " + n.start + " no está en states");
    }
    for (const std::string& f : n.accept) {
        if (q.count(f) == 0) {
            throw std::runtime_error("el estado de aceptación " + f + " no está en states");
        }
    }
    for (const auto& [key, targets] : n.delta) {
        if (q.count(key.first) == 0) {
            throw std::runtime_error("transición desde " + key.first + ", que no está en states");
        }
        if (key.second != EPS && sigma.count(key.second) == 0) {
            throw std::runtime_error(std::string("transición con ") + key.second + ", que no está en alphabet");
        }
        for (const std::string& target : targets) {
            if (q.count(target) == 0) {
                throw std::runtime_error("transición hacia " + target + ", que no está en states");
            }
        }
    }
}

// ------------------------------------------------------------
// Leer y escribir el formato .nfa
// ------------------------------------------------------------

inline std::vector<std::string> split_nfa_words(const std::string& text) {
    std::istringstream in(text);
    std::vector<std::string> words;
    std::string word;
    while (in >> word) {
        words.push_back(word);
    }
    return words;
}

// Lee una descripción completa, hasta el final de la entrada.
inline Nfa read_nfa(std::istream& in) {
    int number = 0;
    auto fail = [&number](const std::string& message) {
        throw std::runtime_error("línea " + std::to_string(number) + ": " + message);
    };
    // Siguiente línea que no es comentario ni está vacía. Devuelve false al final.
    auto next_line = [&in, &number](std::vector<std::string>& words) {
        std::string line;
        while (std::getline(in, line)) {
            number++;
            if (!line.empty() && line[0] == '#') {
                continue;
            }
            words = split_nfa_words(line);
            if (!words.empty()) {
                return true;
            }
        }
        return false;
    };
    auto field = [&next_line, &fail](const std::string& name) {
        std::vector<std::string> words;
        if (!next_line(words) || words[0] != name + ":") {
            fail("se esperaba el campo " + name + ":");
        }
        words.erase(words.begin());
        return words;
    };

    Nfa n;
    n.states = field("states");
    for (const std::string& symbol : field("alphabet")) {
        if (symbol.size() != 1 || symbol[0] == '#') {
            fail("un símbolo es un solo carácter distinto de #: " + symbol);
        }
        n.alphabet.push_back(symbol[0]);
    }
    std::vector<std::string> start = field("start");
    if (start.size() != 1) {
        fail("start: lleva exactamente un estado");
    }
    n.start = start[0];
    for (const std::string& state : field("accept")) {
        n.accept.insert(state);
    }
    if (!field("delta").empty()) {
        fail("después de delta: las transiciones van una por línea");
    }
    std::vector<std::string> words;
    while (next_line(words)) {
        // estado símbolo destino…  con eps en el lugar del símbolo para una transición ε
        if (words.size() < 3 || (words[1] != "eps" && words[1].size() != 1)) {
            fail("una transición se escribe: estado símbolo destino…");
        }
        char a = (words[1] == "eps") ? EPS : words[1][0];
        for (std::size_t i = 2; i < words.size(); i++) {
            n.delta[{words[0], a}].insert(words[i]);
        }
    }
    check_nfa(n);
    return n;
}

inline Nfa load_nfa(const std::string& path) {
    std::ifstream file(path);
    if (!file) {
        throw std::runtime_error("no se pudo abrir " + path);
    }
    try {
        return read_nfa(file);
    } catch (const std::runtime_error& error) {
        throw std::runtime_error(path + ": " + error.what());
    }
}

// Escribe n en el formato .nfa. Un par de estado y símbolo sin transiciones no lleva línea.
inline void write_nfa(std::ostream& out, const Nfa& n) {
    out << "states:";
    for (const std::string& state : n.states) {
        out << ' ' << state;
    }
    out << "\nalphabet:";
    for (char a : n.alphabet) {
        out << ' ' << a;
    }
    out << "\nstart: " << n.start << "\naccept:";
    for (const std::string& state : n.states) {
        if (n.accept.count(state) > 0) {
            out << ' ' << state;
        }
    }
    out << "\ndelta:\n";
    std::vector<char> labels = n.alphabet;
    labels.push_back(EPS);
    for (const std::string& state : n.states) {
        for (char a : labels) {
            auto it = n.delta.find({state, a});
            if (it == n.delta.end() || it->second.empty()) {
                continue;
            }
            out << state << ' ' << (a == EPS ? std::string("eps") : std::string(1, a));
            // Los destinos, en el orden de states.
            for (const std::string& target : n.states) {
                if (it->second.count(target) > 0) {
                    out << ' ' << target;
                }
            }
            out << '\n';
        }
    }
}

// ------------------------------------------------------------
// Ejecutar: el conjunto de estados activos
// ------------------------------------------------------------

// Clausura ε: los estados de s y todos los que se alcanzan desde ellos con transiciones ε.
// Es una búsqueda en el grafo de las transiciones ε.
inline StateSet eps_closure(const Nfa& n, const StateSet& s) {
    StateSet closure = s;
    std::vector<std::string> pending(s.begin(), s.end());
    while (!pending.empty()) {
        std::string q = pending.back();
        pending.pop_back();
        auto it = n.delta.find({q, EPS});
        if (it == n.delta.end()) {
            continue;
        }
        for (const std::string& target : it->second) {
            if (closure.insert(target).second) {
                pending.push_back(target);
            }
        }
    }
    return closure;
}

// Un paso: desde los estados de s, leer el símbolo a y después seguir las transiciones ε.
inline StateSet step(const Nfa& n, const StateSet& s, char a) {
    StateSet next;
    for (const std::string& q : s) {
        auto it = n.delta.find({q, a});
        if (it != n.delta.end()) {
            next.insert(it->second.begin(), it->second.end());
        }
    }
    return eps_closure(n, next);
}

// Los conjuntos de estados activos S0, S1, …, Sn: S0 es la clausura ε de {q0}, y S(i) es el
// conjunto de estados en los que el NFA puede estar después de leer los primeros i símbolos.
inline std::vector<StateSet> run(const Nfa& n, const std::string& w) {
    std::vector<StateSet> sets = {eps_closure(n, {n.start})};
    for (char a : w) {
        sets.push_back(step(n, sets.back(), a));
    }
    return sets;
}

// N acepta w si, después de leerla, algún estado activo es de aceptación.
inline bool accepts(const Nfa& n, const std::string& w) {
    StateSet active = eps_closure(n, {n.start});
    for (char a : w) {
        active = step(n, active, a);
    }
    for (const std::string& q : active) {
        if (n.accept.count(q) > 0) {
            return true;
        }
    }
    return false;
}

// Para imprimir un conjunto de estados en el orden de states: {q0, q3}.
inline std::string show_set(const Nfa& n, const StateSet& s) {
    std::string text = "{";
    for (const std::string& state : n.states) {
        if (s.count(state) > 0) {
            text += (text.size() > 1 ? ", " : "") + state;
        }
    }
    return text + "}";
}

#endif
orders.cppDescargar orders.cpp
// Elimina los estados de un DFA en todos los órdenes posibles: orders ARCHIVO.dfa
// Imprime la expresión que sale con cada orden y cuántos nodos tiene su árbol.
#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

#include "dfa.h"
#include "gnfa.h"
#include "regex.h"

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: orders ARCHIVO.dfa\n";
        return 2;
    }
    try {
        Dfa m = load_dfa(argv[1]);
        if (m.states.size() > 6) {
            throw std::runtime_error("con más de 6 estados son demasiados órdenes");
        }
        std::vector<std::string> order = m.states;
        std::sort(order.begin(), order.end());
        do {
            RegexPtr r = to_regex(m, order);
            for (const std::string& k : order) {
                std::cout << k << ' ';
            }
            std::cout << " (" << size(r) << " nodos)\n    " << to_string(r) << '\n';
        } while (std::next_permutation(order.begin(), order.end()));
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
regex_diff.cppDescargar regex_diff.cpp
// Compara dos expresiones con todas las cadenas cortas: regex_diff EXPRESIÓN1 EXPRESIÓN2 [LONGITUD]
// Lista las cadenas que una describe y la otra no. La longitud máxima por defecto es 8.
// Que no haya diferencias hasta esa longitud no demuestra que sean equivalentes.
#include <cstddef>
#include <iostream>
#include <set>
#include <stdexcept>
#include <string>
#include <vector>

#include "nfa.h"
#include "regex.h"
#include "thompson.h"
#include "words.h"

int main(int argc, char** argv) {
    if (argc < 3 || argc > 4) {
        std::cerr << "uso: regex_diff EXPRESIÓN1 EXPRESIÓN2 [LONGITUD]\n";
        return 2;
    }
    try {
        RegexPtr r1 = parse_regex(argv[1]);
        RegexPtr r2 = parse_regex(argv[2]);
        std::size_t max_len = (argc == 4) ? std::stoul(argv[3]) : 8;
        std::set<char> both;
        collect_symbols(r1, both);
        collect_symbols(r2, both);
        std::vector<char> alphabet(both.begin(), both.end());
        if (alphabet.empty()) {
            throw std::runtime_error("las expresiones no tienen símbolos");
        }
        Nfa n1 = thompson(r1, alphabet);
        Nfa n2 = thompson(r2, alphabet);
        std::vector<std::string> only1;
        std::vector<std::string> only2;
        std::vector<std::string> words = all_strings(alphabet, max_len);
        for (const std::string& w : words) {
            bool in1 = accepts(n1, w);
            bool in2 = accepts(n2, w);
            if (in1 && !in2) {
                only1.push_back(w);
            }
            if (in2 && !in1) {
                only2.push_back(w);
            }
        }
        auto report = [](const std::string& name, const std::vector<std::string>& list) {
            std::cout << "solo en " << name << ": " << list.size();
            if (!list.empty()) {
                std::cout << ". Las más cortas:";
                for (std::size_t i = 0; i < list.size() && i < 6; i++) {
                    std::cout << ' ' << show(list[i]);
                }
            }
            std::cout << '\n';
        };
        std::cout << "R1 = " << to_string(r1) << "\nR2 = " << to_string(r2) << '\n'
                  << words.size() << " cadenas de longitud a lo sumo " << max_len << '\n';
        report("R1", only1);
        report("R2", only2);
        if (only1.empty() && only2.empty()) {
            std::cout << "sin diferencias hasta esa longitud\n";
        }
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
regex_lang.cppDescargar regex_lang.cpp
// Lista las cadenas más cortas del lenguaje de una expresión: regex_lang EXPRESIÓN [LONGITUD] [ALFABETO]
// Sin alfabeto, usa los símbolos que aparecen en la expresión. La longitud máxima por defecto es 4.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

#include "nfa.h"
#include "regex.h"
#include "thompson.h"
#include "words.h"

int main(int argc, char** argv) {
    if (argc < 2 || argc > 4) {
        std::cerr << "uso: regex_lang EXPRESIÓN [LONGITUD] [ALFABETO]\n";
        return 2;
    }
    try {
        RegexPtr r = parse_regex(argv[1]);
        std::size_t max_len = (argc >= 3) ? std::stoul(argv[2]) : 4;
        std::vector<char> alphabet = symbols_of(r);
        if (argc == 4) {
            std::string given = argv[3];
            alphabet.assign(given.begin(), given.end());
        }
        if (alphabet.empty()) {
            throw std::runtime_error("la expresión no tiene símbolos: indiquen el alfabeto");
        }
        Nfa n = thompson(r, alphabet);
        std::vector<std::string> words = all_strings(alphabet, max_len);
        std::size_t inside = 0;
        std::cout << "L(" << to_string(r) << "), hasta longitud " << max_len << ":\n ";
        for (const std::string& w : words) {
            if (accepts(n, w)) {
                std::cout << ' ' << show(w);
                inside++;
            }
        }
        std::cout << (inside == 0 ? " (ninguna)" : "") << '\n'
                  << inside << " de " << words.size() << " cadenas\n";
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
regex_tree.cppDescargar regex_tree.cpp
// Muestra cómo se lee una expresión regular: regex_tree EXPRESIÓN...
// Imprime la expresión con los paréntesis justos, con todos los paréntesis, y su árbol.
#include <iostream>
#include <stdexcept>

#include "regex.h"

int main(int argc, char** argv) {
    if (argc < 2) {
        std::cerr << "uso: regex_tree EXPRESIÓN...\n";
        return 2;
    }
    for (int i = 1; i < argc; i++) {
        try {
            RegexPtr r = parse_regex(argv[i]);
            std::cout << "expresión:           " << to_string(r) << '\n'
                      << "con sus paréntesis:  " << to_string_full(r) << '\n'
                      << "nodos del árbol:     " << size(r) << '\n'
                      << tree(r);
        } catch (const std::runtime_error& error) {
            std::cout << argv[i] << "\n  error: " << error.what() << '\n';
        }
        if (i + 1 < argc) {
            std::cout << '\n';
        }
    }
}
regex.hDescargar regex.h
// Expresiones regulares. Una expresión es un árbol con un nodo por cada caso de la definición
// inductiva: ∅, ε, un símbolo, unión, concatenación y estrella.
// Además: el parser que lee una expresión escrita en una línea, y la escritura con los
// paréntesis justos.
//
// Cómo se escribe una expresión para estos programas:
//   - un símbolo es una letra o un dígito: a, b, 0, 1
//   - la unión es |, la concatenación no se escribe y la estrella es *
//   - ε se escribe % (o la propia letra ε) y ∅ se escribe @ (o el propio signo ∅)
//   - precedencia: primero la estrella, después la concatenación, al final la unión
//   - los paréntesis agrupan y los espacios se ignoran
#ifndef REGEX_H
#define REGEX_H

#include <cctype>
#include <cstddef>
#include <memory>
#include <set>
#include <stdexcept>
#include <string>
#include <vector>

enum class Kind { Empty, Epsilon, Symbol, Union, Concat, Star };

struct Regex;
// Un árbol no cambia después de construido, así que dos expresiones pueden compartir un subárbol.
using RegexPtr = std::shared_ptr<const Regex>;

struct Regex {
    Kind kind;
    char symbol;    // solo si kind == Symbol
    RegexPtr left;  // el único hijo de Star; el hijo izquierdo de Union y de Concat
    RegexPtr right;
};

// ------------------------------------------------------------
// Los seis casos de la definición
// ------------------------------------------------------------

inline RegexPtr empty_set() {
    return std::make_shared<const Regex>(Regex{Kind::Empty, '\0', nullptr, nullptr});
}

inline RegexPtr epsilon() {
    return std::make_shared<const Regex>(Regex{Kind::Epsilon, '\0', nullptr, nullptr});
}

inline RegexPtr symbol(char a) {
    return std::make_shared<const Regex>(Regex{Kind::Symbol, a, nullptr, nullptr});
}

inline RegexPtr make_union(const RegexPtr& r1, const RegexPtr& r2) {
    return std::make_shared<const Regex>(Regex{Kind::Union, '\0', r1, r2});
}

inline RegexPtr make_concat(const RegexPtr& r1, const RegexPtr& r2) {
    return std::make_shared<const Regex>(Regex{Kind::Concat, '\0', r1, r2});
}

inline RegexPtr make_star(const RegexPtr& r) {
    return std::make_shared<const Regex>(Regex{Kind::Star, '\0', r, nullptr});
}

// ------------------------------------------------------------
// Las mismas operaciones, aplicando las identidades de ∅ y de ε
// ------------------------------------------------------------

// R ∪ ∅ = ∅ ∪ R = R.
inline RegexPtr simple_union(const RegexPtr& r1, const RegexPtr& r2) {
    if (r1->kind == Kind::Empty) {
        return r2;
    }
    if (r2->kind == Kind::Empty) {
        return r1;
    }
    return make_union(r1, r2);
}

// R∅ = ∅R = ∅ y Rε = εR = R.
inline RegexPtr simple_concat(const RegexPtr& r1, const RegexPtr& r2) {
    if (r1->kind == Kind::Empty || r2->kind == Kind::Empty) {
        return empty_set();
    }
    if (r1->kind == Kind::Epsilon) {
        return r2;
    }
    if (r2->kind == Kind::Epsilon) {
        return r1;
    }
    return make_concat(r1, r2);
}

// ∅* = ε y ε* = ε.
inline RegexPtr simple_star(const RegexPtr& r) {
    if (r->kind == Kind::Empty || r->kind == Kind::Epsilon) {
        return epsilon();
    }
    return make_star(r);
}

// ------------------------------------------------------------
// Medidas
// ------------------------------------------------------------

// El tamaño de una expresión: cuántos nodos tiene su árbol.
inline std::size_t size(const RegexPtr& r) {
    switch (r->kind) {
        case Kind::Union:
        case Kind::Concat:
            return 1 + size(r->left) + size(r->right);
        case Kind::Star:
            return 1 + size(r->left);
        default:
            return 1;
    }
}

// Cuántas hojas, uniones y estrellas tiene: de eso depende el tamaño del NFA de Thompson.
inline std::size_t count_without_concat(const RegexPtr& r) {
    switch (r->kind) {
        case Kind::Union:
            return 1 + count_without_concat(r->left) + count_without_concat(r->right);
        case Kind::Concat:
            return count_without_concat(r->left) + count_without_concat(r->right);
        case Kind::Star:
            return 1 + count_without_concat(r->left);
        default:
            return 1;
    }
}

inline void collect_symbols(const RegexPtr& r, std::set<char>& symbols) {
    if (r->kind == Kind::Symbol) {
        symbols.insert(r->symbol);
    }
    if (r->left) {
        collect_symbols(r->left, symbols);
    }
    if (r->right) {
        collect_symbols(r->right, symbols);
    }
}

// Los símbolos que aparecen en la expresión, en orden.
inline std::vector<char> symbols_of(const RegexPtr& r) {
    std::set<char> symbols;
    collect_symbols(r, symbols);
    return std::vector<char>(symbols.begin(), symbols.end());
}

// ------------------------------------------------------------
// Escribir
// ------------------------------------------------------------

// Qué tan fuerte liga cada operación: la unión 1, la concatenación 2, la estrella 3.
// Las hojas no necesitan paréntesis nunca.
inline int precedence(Kind kind) {
    switch (kind) {
        case Kind::Union:
            return 1;
        case Kind::Concat:
            return 2;
        case Kind::Star:
            return 3;
        default:
            return 4;
    }
}

inline std::string to_string(const RegexPtr& r);

// Escribe r como operando de una operación de precedencia level: con paréntesis solo si r
// liga más débil que ella.
inline std::string operand(const RegexPtr& r, int level) {
    std::string text = to_string(r);
    return precedence(r->kind) < level ? "(" + text + ")" : text;
}

// La expresión con los paréntesis justos. La unión y la concatenación son asociativas, así
// que (R1|R2)|R3 y R1|(R2|R3) se escriben igual: R1|R2|R3.
inline std::string to_string(const RegexPtr& r) {
    switch (r->kind) {
        case Kind::Empty:
            return "∅";
        case Kind::Epsilon:
            return "ε";
        case Kind::Symbol:
            return std::string(1, r->symbol);
        case Kind::Union:
            return operand(r->left, 1) + "|" + operand(r->right, 1);
        case Kind::Concat:
            return operand(r->left, 2) + operand(r->right, 2);
        case Kind::Star:
            // Una estrella sobre otra estrella lleva paréntesis para que se lea: (a*)*.
            return (r->left->kind == Kind::Star ? "(" + to_string(r->left) + ")" : operand(r->left, 3)) + "*";
    }
    return "";
}

// La expresión con todos los paréntesis, un par por cada operación: muestra el árbol sin
// depender de la precedencia.
inline std::string to_string_full(const RegexPtr& r) {
    switch (r->kind) {
        case Kind::Union:
            return "(" + to_string_full(r->left) + "|" + to_string_full(r->right) + ")";
        case Kind::Concat:
            return "(" + to_string_full(r->left) + to_string_full(r->right) + ")";
        case Kind::Star:
            return "(" + to_string_full(r->left) + "*)";
        default:
            return to_string(r);
    }
}

inline void tree_lines(const RegexPtr& r, const std::string& indent, std::string& out) {
    switch (r->kind) {
        case Kind::Union:
            out += indent + "unión\n";
            break;
        case Kind::Concat:
            out += indent + "concatenación\n";
            break;
        case Kind::Star:
            out += indent + "estrella\n";
            break;
        default:
            out += indent + to_string(r) + "\n";
            break;
    }
    if (r->left) {
        tree_lines(r->left, indent + "    ", out);
    }
    if (r->right) {
        tree_lines(r->right, indent + "    ", out);
    }
}

// El árbol, un nodo por línea, con los hijos debajo y más adentro.
inline std::string tree(const RegexPtr& r) {
    std::string out;
    tree_lines(r, "", out);
    return out;
}

// ------------------------------------------------------------
// Leer: un parser recursivo, con una función por nivel de precedencia
// ------------------------------------------------------------
//
//   unión         →  concatenación ( '|' concatenación )*
//   concatenación →  estrella estrella*
//   estrella      →  átomo '*'*
//   átomo         →  símbolo  |  ε  |  ∅  |  '(' unión ')'

struct RegexParser {
    std::string text;
    std::size_t pos = 0;

    [[noreturn]] void fail(const std::string& message) const {
        throw std::runtime_error("posición " + std::to_string(pos + 1) + ": " + message);
    }

    void skip_spaces() {
        while (pos < text.size() && text[pos] == ' ') {
            pos++;
        }
    }

    // ¿Sigue el texto s en la posición actual? Si sigue, lo consume.
    bool take(const std::string& s) {
        skip_spaces();
        if (text.compare(pos, s.size(), s) == 0) {
            pos += s.size();
            return true;
        }
        return false;
    }

    // ¿Empieza un átomo en la posición actual? Sirve para saber si la concatenación sigue.
    bool atom_ahead() {
        skip_spaces();
        if (pos >= text.size()) {
            return false;
        }
        unsigned char c = static_cast<unsigned char>(text[pos]);
        return std::isalnum(c) != 0 || c == '(' || c == '%' || c == '@' || text.compare(pos, 2, "ε") == 0 ||
               text.compare(pos, 3, "∅") == 0;
    }

    RegexPtr parse_atom() {
        if (take("(")) {
            RegexPtr inside = parse_union();
            if (!take(")")) {
                fail("falta cerrar un paréntesis");
            }
            return inside;
        }
        if (take("%") || take("ε")) {
            return epsilon();
        }
        if (take("@") || take("∅")) {
            return empty_set();
        }
        skip_spaces();
        if (pos < text.size() && std::isalnum(static_cast<unsigned char>(text[pos])) != 0) {
            return symbol(text[pos++]);
        }
        if (pos >= text.size()) {
            fail("la expresión termina donde se esperaba un símbolo o un paréntesis");
        }
        fail(std::string("se esperaba un símbolo o un paréntesis, y hay ") + text[pos]);
    }

    RegexPtr parse_star() {
        RegexPtr r = parse_atom();
        while (take("*")) {
            r = make_star(r);
        }
        return r;
    }

    RegexPtr parse_concat() {
        RegexPtr r = parse_star();
        while (atom_ahead()) {
            RegexPtr next = parse_star();
            r = make_concat(r, next);
        }
        return r;
    }

    RegexPtr parse_union() {
        RegexPtr r = parse_concat();
        while (take("|")) {
            RegexPtr next = parse_concat();
            r = make_union(r, next);
        }
        return r;
    }
};

// Lee una expresión completa. Lanza std::runtime_error si no está bien formada.
inline RegexPtr parse_regex(const std::string& text) {
    RegexParser parser{text};
    RegexPtr r = parser.parse_union();
    parser.skip_spaces();
    if (parser.pos != text.size()) {
        parser.fail(std::string("sobra ") + text[parser.pos]);
    }
    return r;
}

#endif
run_nfa.cppDescargar run_nfa.cpp
// Sigue un NFA con una o más cadenas: run_nfa ARCHIVO.nfa CADENA...
// Con - en lugar del archivo, lee la descripción de la entrada estándar.
// Muestra el conjunto de estados activos antes de leer nada y después de cada símbolo.
// La cadena vacía se pasa como '' en la terminal.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

#include "nfa.h"
#include "words.h"

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cerr << "uso: run_nfa ARCHIVO.nfa CADENA...\n";
        return 2;
    }
    try {
        std::string path = argv[1];
        Nfa n = (path == "-") ? read_nfa(std::cin) : load_nfa(path);
        for (int i = 2; i < argc; i++) {
            std::string w = argv[i];
            std::vector<StateSet> sets = run(n, w);
            std::cout << "w = " << show(w) << '\n';
            std::cout << "  inicio  " << show_set(n, sets[0]) << '\n';
            for (std::size_t k = 0; k < w.size(); k++) {
                std::cout << "  lee " << w[k] << "   " << show_set(n, sets[k + 1]) << '\n';
            }
            bool ok = false;
            for (const std::string& q : sets.back()) {
                ok = ok || n.accept.count(q) > 0;
            }
            std::cout << (ok ? "  hay un estado de F entre los activos: acepta\n"
                             : "  ningún estado activo está en F: rechaza\n");
        }
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
thompson.cppDescargar thompson.cpp
// De expresión regular a NFA con la construcción de Thompson: thompson EXPRESIÓN [ALFABETO]
// Escribe el NFA en el formato .nfa. Sin alfabeto, usa los símbolos de la expresión.
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

#include "nfa.h"
#include "regex.h"
#include "thompson.h"

int main(int argc, char** argv) {
    if (argc < 2 || argc > 3) {
        std::cerr << "uso: thompson EXPRESIÓN [ALFABETO]\n";
        return 2;
    }
    try {
        RegexPtr r = parse_regex(argv[1]);
        std::vector<char> alphabet = symbols_of(r);
        if (argc == 3) {
            std::string given = argv[2];
            alphabet.assign(given.begin(), given.end());
        }
        Nfa n = thompson(r, alphabet);
        std::cout << "# NFA de Thompson de " << to_string(r) << '\n';
        write_nfa(std::cout, n);
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
thompson.hDescargar thompson.h
// Construcción de Thompson: de una expresión regular a un NFA con transiciones ε.
// Hay una pieza por cada caso de la definición de expresión regular. Cada pieza tiene un solo
// estado inicial y un solo estado de aceptación, y por eso se pueden conectar sin mirar adentro.
#ifndef THOMPSON_H
#define THOMPSON_H

#include <stdexcept>
#include <string>
#include <vector>

#include "nfa.h"
#include "regex.h"

// Una pieza ya construida dentro del NFA: por dónde se entra y por dónde se sale.
struct Fragment {
    std::string start;
    std::string accept;
};

// Agrega un estado nuevo, con el siguiente nombre libre: q0, q1, q2…
inline std::string new_state(Nfa& n) {
    std::string name = "q" + std::to_string(n.states.size());
    n.states.push_back(name);
    return name;
}

// Construye dentro de n la pieza de r y dice cuáles son su entrada y su salida.
inline Fragment build_fragment(Nfa& n, const RegexPtr& r) {
    switch (r->kind) {
        case Kind::Empty: {
            // Dos estados sin ninguna flecha: no hay camino de la entrada a la salida.
            std::string s = new_state(n);
            std::string f = new_state(n);
            return {s, f};
        }
        case Kind::Epsilon: {
            std::string s = new_state(n);
            std::string f = new_state(n);
            n.delta[{s, EPS}].insert(f);
            return {s, f};
        }
        case Kind::Symbol: {
            std::string s = new_state(n);
            std::string f = new_state(n);
            n.delta[{s, r->symbol}].insert(f);
            return {s, f};
        }
        case Kind::Union: {
            // Una entrada nueva que elige una de las dos piezas, y una salida nueva para las dos.
            std::string s = new_state(n);
            Fragment a = build_fragment(n, r->left);
            Fragment b = build_fragment(n, r->right);
            std::string f = new_state(n);
            n.delta[{s, EPS}].insert(a.start);
            n.delta[{s, EPS}].insert(b.start);
            n.delta[{a.accept, EPS}].insert(f);
            n.delta[{b.accept, EPS}].insert(f);
            return {s, f};
        }
        case Kind::Concat: {
            // La salida de la primera pieza se une con la entrada de la segunda.
            Fragment a = build_fragment(n, r->left);
            Fragment b = build_fragment(n, r->right);
            n.delta[{a.accept, EPS}].insert(b.start);
            return {a.start, b.accept};
        }
        case Kind::Star: {
            // Entrada y salida nuevas: se puede saltar la pieza, o recorrerla y repetir.
            std::string s = new_state(n);
            Fragment a = build_fragment(n, r->left);
            std::string f = new_state(n);
            n.delta[{s, EPS}].insert(a.start);
            n.delta[{s, EPS}].insert(f);
            n.delta[{a.accept, EPS}].insert(a.start);
            n.delta[{a.accept, EPS}].insert(f);
            return {s, f};
        }
    }
    throw std::runtime_error("expresión mal formada");
}

// El NFA de Thompson de r sobre el alfabeto dado, que debe contener los símbolos de r.
inline Nfa thompson(const RegexPtr& r, const std::vector<char>& alphabet) {
    Nfa n;
    n.alphabet = alphabet;
    Fragment whole = build_fragment(n, r);
    n.start = whole.start;
    n.accept = {whole.accept};
    check_nfa(n);
    return n;
}

// Lo mismo, con el alfabeto formado por los símbolos que aparecen en r.
inline Nfa thompson(const RegexPtr& r) {
    return thompson(r, symbols_of(r));
}

#endif
words.hDescargar words.h
// Listar cadenas, para comprobar un lenguaje con todas las cadenas cortas.
#ifndef WORDS_H
#define WORDS_H

#include <cstddef>
#include <string>
#include <vector>

// Todas las cadenas sobre el alfabeto con longitud a lo sumo max_len, primero las más cortas
// y, entre las de igual longitud, en el orden del alfabeto. Es la función de la semana 1.
inline std::vector<std::string> all_strings(const std::vector<char>& alphabet, std::size_t max_len) {
    std::vector<std::string> result = {""};
    std::size_t first = 0;  // dónde empiezan las cadenas de la longitud anterior
    for (std::size_t len = 1; len <= max_len; len++) {
        std::size_t last = result.size();
        for (std::size_t i = first; i < last; i++) {
            for (char a : alphabet) {
                result.push_back(result[i] + a);
            }
        }
        first = last;
    }
    return result;
}

// Para imprimir: la cadena vacía se muestra como ε.
inline std::string show(const std::string& w) {
    return w.empty() ? "ε" : w;
}

#endif
machines/ab_or_a_star.nfaDescargar machines/ab_or_a_star.nfa
# NFA de Thompson de (ab|a)*
states: q0 q1 q2 q3 q4 q5 q6 q7 q8 q9
alphabet: a b
start: q0
accept: q9
delta:
q0 eps q1 q9
q1 eps q2 q6
q2 a q3
q3 eps q4
q4 b q5
q5 eps q8
q6 a q7
q7 eps q8
q8 eps q1 q9
machines/ends_01.dfaDescargar machines/ends_01.dfa
# Cadenas binarias que terminan en 01.
# q0: lo leído no termina en 0 ni en 01. q1: termina en 0. q2: termina en 01.
states: q0 q1 q2
alphabet: 0 1
start: q0
accept: q2
delta:
q0 0 q1
q0 1 q0
q1 0 q1
q1 1 q2
q2 0 q1
q2 1 q0
machines/ends_in_1.nfaDescargar machines/ends_in_1.nfa
# NFA de Thompson de (0|1)*1
states: q0 q1 q2 q3 q4 q5 q6 q7 q8 q9
alphabet: 0 1
start: q0
accept: q9
delta:
q0 eps q1 q7
q1 eps q2 q4
q2 0 q3
q3 eps q6
q4 1 q5
q5 eps q6
q6 eps q1 q7
q7 eps q8
q8 1 q9
machines/even_ones.dfaDescargar machines/even_ones.dfa
# Cadenas binarias con una cantidad par de unos.
states: par impar
alphabet: 0 1
start: par
accept: par
delta:
par 0 par
par 1 impar
impar 0 impar
impar 1 par
machines/multiple_of_3.dfaDescargar machines/multiple_of_3.dfa
# Cadenas binarias que, leídas como un número en base 2, dan un múltiplo de 3.
# La cadena vacía vale 0. El estado rK dice que el valor de lo leído deja resto K al dividir entre 3.
states: r0 r1 r2
alphabet: 0 1
start: r0
accept: r0
delta:
r0 0 r0
r0 1 r1
r1 0 r2
r1 1 r0
r2 0 r1
r2 1 r2
machines/no_11.dfaDescargar machines/no_11.dfa
# Cadenas binarias que no contienen 11.
# q0: sin 11 y no termina en 1. q1: sin 11 y termina en 1. q2: ya apareció 11 (estado trampa).
states: q0 q1 q2
alphabet: 0 1
start: q0
accept: q0 q1
delta:
q0 0 q0
q0 1 q1
q1 0 q0
q1 1 q2
q2 0 q2
q2 1 q2

Errores

Ejemplos con errores a propósito: no compilan, fallan o dan un resultado incorrecto. Los apuntes explican cada uno.

errors/malformed.txtDescargar errors/malformed.txt
# Expresiones mal formadas: el parser debe rechazar cada una. Una por línea.
# Una unión a la que le falta el lado derecho.
0|
# Una unión a la que le falta el lado izquierdo.
|1
# Dos barras seguidas: entre ellas no hay nada. La expresión vacía no existe; ε se escribe %.
0||1
# Una estrella sin nada a su izquierda.
*0
# Una estrella justo después de abrir un paréntesis.
(*0)
# Un paréntesis sin cerrar.
(0|1
# Un paréntesis que nadie abrió.
0|1)
# Paréntesis sin nada adentro.
()
# Un carácter que no es símbolo ni operador: el + de las herramientas no está en la definición.
0+1

Pruebas

Comprueban lo que afirman los apuntes; se ejecutan con make test.

test_backtrack.cppDescargar test_backtrack.cpp
// Pruebas del buscador con backtracking (sesión B): responde lo mismo que la simulación del
// NFA, termina con estrellas anidadas, y con (a|a)*b contra a^n hace 10·2^n − 4 llamadas.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <string>
#include <vector>

#include "backtrack.h"
#include "nfa.h"
#include "regex.h"
#include "thompson.h"
#include "words.h"

static std::size_t test_agrees_with_nfa() {
    std::vector<std::string> expressions = {
        "(0|1)*1", "((0|1)(0|1))*", "0*10*10*", "(1|01*0)*", "(0|10)*(%|1)", "(01)*|(10)*",
        "(0*)*1",  "(0|%)*1",       "(0*1*)*",  "@",         "%",            "(0|@)1",
        "(%|0)*",  "((0|1)*)*",
    };
    std::vector<std::string> words = all_strings({'0', '1'}, 8);
    for (const std::string& text : expressions) {
        RegexPtr r = parse_regex(text);
        Nfa n = thompson(r, {'0', '1'});
        for (const std::string& w : words) {
            assert(backtrack_accepts(r, w) == accepts(n, w));
        }
    }
    return expressions.size();
}

static void test_bad_case() {
    RegexPtr r = parse_regex("(a|a)*b");
    long long calls = 0;
    assert(backtrack_accepts(r, "aab", &calls) && calls == 12);
    assert(!backtrack_accepts(r, "aaa", &calls) && calls == 76);
    long long power = 1;
    for (std::size_t n = 0; n <= 14; n++) {
        assert(!backtrack_accepts(r, std::string(n, 'a'), &calls));
        assert(calls == 10 * power - 4);
        power *= 2;
    }
    // Con la b al final, la primera rama que prueba ya acierta: las llamadas son lineales.
    for (std::size_t n = 0; n <= 14; n++) {
        assert(backtrack_accepts(r, std::string(n, 'a') + "b", &calls));
        assert(calls == static_cast<long long>(3 * n + 6));
    }
}

int main() {
    std::size_t expressions = test_agrees_with_nfa();
    test_bad_case();
    std::printf("test_backtrack: ok (%zu expresiones, 511 cadenas cada una)\n", expressions);
}
test_elimination.cppDescargar test_elimination.cpp
// Pruebas de la eliminación de estados (sesión B).
// La expresión que sale de un DFA se vuelve a leer, se convierte en un NFA con la construcción
// de Thompson y se compara con el DFA original sobre todas las cadenas cortas. Así se cierra
// el triángulo: DFA → expresión → NFA, y los dos extremos deben aceptar lo mismo.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <string>
#include <vector>

#include "dfa.h"
#include "gnfa.h"
#include "nfa.h"
#include "regex.h"
#include "thompson.h"
#include "words.h"

// La expresión, pasando por su texto: comprueba de paso que lo escrito se puede volver a leer.
static Nfa nfa_of(const RegexPtr& r, const std::vector<char>& alphabet) {
    return thompson(parse_regex(to_string(r)), alphabet);
}

static void check_equivalent(const Dfa& m, const RegexPtr& r, std::size_t max_len) {
    Nfa n = nfa_of(r, m.alphabet);
    for (const std::string& w : all_strings(m.alphabet, max_len)) {
        assert(accepts(m, w) == accepts(n, w));
    }
}

// Todos los órdenes de eliminación de m. Devuelve cuántos son.
static std::size_t check_all_orders(const std::string& path, std::size_t max_len) {
    Dfa m = load_dfa(path);
    std::vector<std::string> order = m.states;
    std::sort(order.begin(), order.end());
    std::size_t count = 0;
    do {
        check_equivalent(m, to_regex(m, order), max_len);
        count++;
    } while (std::next_permutation(order.begin(), order.end()));
    return count;
}

static Dfa multiples_of(int k) {
    Dfa m;
    m.alphabet = {'0', '1'};
    for (int i = 0; i < k; i++) {
        m.states.push_back("r" + std::to_string(i));
    }
    m.start = "r0";
    m.accept = {"r0"};
    for (int i = 0; i < k; i++) {
        m.delta[{m.states[i], '0'}] = m.states[(2 * i) % k];
        m.delta[{m.states[i], '1'}] = m.states[(2 * i + 1) % k];
    }
    check_dfa(m);
    return m;
}

static void test_gnfa_of_dfa() {
    Dfa m = load_dfa("machines/multiple_of_3.dfa");
    Gnfa g = to_gnfa(m);
    assert(g.states == (std::vector<std::string>{"ini", "r0", "r1", "r2", "fin"}));
    assert(g.arrow.size() == 8);
    assert(to_string(label(g, "ini", "r0")) == "ε");
    assert(to_string(label(g, "r0", "fin")) == "ε");
    assert(to_string(label(g, "r0", "r1")) == "1");
    assert(to_string(label(g, "r2", "r2")) == "1");
    assert(label(g, "r0", "r2")->kind == Kind::Empty);  // la flecha que no está lleva ∅
    // Al inicial no le entra nada y del de aceptación no sale nada.
    for (const auto& [key, r] : g.arrow) {
        assert(key.second != g.start && key.first != g.accept);
    }
    // Dos símbolos entre los mismos estados se juntan en una unión.
    Dfa all;
    all.states = {"q"};
    all.alphabet = {'0', '1'};
    all.start = "q";
    all.accept = {"q"};
    all.delta[{"q", '0'}] = "q";
    all.delta[{"q", '1'}] = "q";
    assert(to_string(label(to_gnfa(all), "q", "q")) == "0|1");
    assert(to_string(to_regex(all, {"q"})) == "(0|1)*");
    // Sin estados de aceptación no hay camino hasta fin: sale ∅.
    all.accept.clear();
    assert(to_regex(all, {"q"})->kind == Kind::Empty);
}

static void test_steps_of_the_notes() {
    // El ejemplo de dos estados, en los dos órdenes.
    Dfa parity = load_dfa("machines/even_ones.dfa");
    Gnfa g = eliminate(to_gnfa(parity), "impar");
    assert(g.arrow.size() == 3);
    assert(to_string(label(g, "par", "par")) == "0|10*1");
    assert(to_string(to_regex(parity, {"impar", "par"})) == "(0|10*1)*");
    Gnfa h = eliminate(to_gnfa(parity), "par");
    assert(to_string(label(h, "ini", "impar")) == "0*1");
    assert(to_string(label(h, "ini", "fin")) == "0*");
    assert(to_string(label(h, "impar", "impar")) == "0|10*1");
    assert(to_string(label(h, "impar", "fin")) == "10*");
    assert(to_string(to_regex(parity, {"par", "impar"})) == "0*|0*1(0|10*1)*10*");

    // El ejemplo completo de tres estados: r2, r1, r0.
    Dfa three = load_dfa("machines/multiple_of_3.dfa");
    Gnfa a = eliminate(to_gnfa(three), "r2");
    assert(a.arrow.size() == 6);
    assert(to_string(label(a, "r1", "r1")) == "01*0");
    assert(to_string(label(a, "r0", "r1")) == "1" && to_string(label(a, "r1", "r0")) == "1");
    Gnfa b = eliminate(a, "r1");
    assert(b.arrow.size() == 3);
    assert(to_string(label(b, "r0", "r0")) == "0|1(01*0)*1");
    assert(to_string(to_regex(three, {"r2", "r1", "r0"})) == "(0|1(01*0)*1)*");
    assert(size(to_regex(three, {"r2", "r1", "r0"})) == 14);
    assert(to_string(to_regex(three, {"r1", "r2", "r0"})) == "(0|11|10(1|00)*01)*");
    assert(size(to_regex(three, {"r0", "r1", "r2"})) == 65);
    // La de 14 nodos y la de 65 describen el mismo lenguaje: los múltiplos de 3.
    Nfa small = nfa_of(to_regex(three, {"r2", "r1", "r0"}), three.alphabet);
    Nfa large = nfa_of(to_regex(three, {"r0", "r1", "r2"}), three.alphabet);
    for (const std::string& w : all_strings(three.alphabet, 9)) {
        bool multiple = w.empty() || std::stoul(w, nullptr, 2) % 3 == 0;
        assert(accepts(small, w) == multiple && accepts(large, w) == multiple);
    }
    // Termina en 01.
    Dfa ends = load_dfa("machines/ends_01.dfa");
    assert(to_string(to_regex(ends, {"q2", "q0", "q1"})) == "1*0(0|10|111*0)*1");
    // No es la más corta: (0|1)*01 describe lo mismo que el autómata.
    check_equivalent(ends, parse_regex("(0|1)*01"), 9);
    // Sin 11: la eliminación devuelve la expresión que la sesión A escribió a mano.
    Dfa no_11 = load_dfa("machines/no_11.dfa");
    assert(to_string(to_regex(no_11, {"q2", "q1", "q0"})) == "(0|10)*(ε|1)");
    assert(to_string(to_regex(no_11, {"q0", "q1", "q2"})) == "0*|0*1(00*1)*(ε|00*)");
}

static void test_growth_table() {
    // La tabla de growth: nodos de la expresión con r0 primero y con r0 al final.
    std::vector<std::vector<std::size_t>> expected = {{2, 22, 9}, {3, 65, 14}, {4, 110, 27}, {5, 314, 52}};
    for (const std::vector<std::size_t>& row : expected) {
        Dfa m = multiples_of(static_cast<int>(row[0]));
        std::vector<std::string> backward(m.states.rbegin(), m.states.rend());
        RegexPtr first = to_regex(m, m.states);
        RegexPtr last = to_regex(m, backward);
        assert(size(first) == row[1] && size(last) == row[2]);
        check_equivalent(m, first, 6);
        check_equivalent(m, last, 6);
    }
}

int main() {
    test_gnfa_of_dfa();
    test_steps_of_the_notes();
    std::size_t orders = 0;
    orders += check_all_orders("machines/even_ones.dfa", 8);
    orders += check_all_orders("machines/multiple_of_3.dfa", 8);
    orders += check_all_orders("machines/ends_01.dfa", 8);
    orders += check_all_orders("machines/no_11.dfa", 8);
    test_growth_table();
    std::printf("test_elimination: ok (4 autómatas, %zu órdenes de eliminación, 511 cadenas cada uno)\n", orders);
}
test_regex.cppDescargar test_regex.cpp
// Pruebas del parser y de la escritura de expresiones regulares (sesión A).
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <fstream>
#include <stdexcept>
#include <string>
#include <vector>

#include "regex.h"

static bool is_malformed(const std::string& text) {
    try {
        parse_regex(text);
    } catch (const std::runtime_error&) {
        return true;
    }
    return false;
}

static void test_precedence() {
    // La estrella liga más que la concatenación, y la concatenación más que la unión.
    assert(to_string_full(parse_regex("ab|c*")) == "((ab)|(c*))");
    assert(to_string_full(parse_regex("ab*")) == "(a(b*))");
    assert(to_string_full(parse_regex("(ab)*")) == "((ab)*)");
    assert(to_string_full(parse_regex("a|bc")) == "(a|(bc))");
    assert(to_string_full(parse_regex("(a|b)c")) == "((a|b)c)");
    assert(to_string_full(parse_regex("(0|1)*1")) == "(((0|1)*)1)");
    assert(to_string_full(parse_regex("0|1*")) == "(0|(1*))");
    // La unión y la concatenación se agrupan hacia la izquierda.
    assert(to_string_full(parse_regex("abc")) == "((ab)c)");
    assert(to_string_full(parse_regex("a|b|c")) == "((a|b)|c)");
    // El árbol de (0|1)*1: la raíz es la concatenación.
    RegexPtr r = parse_regex("(0|1)*1");
    assert(r->kind == Kind::Concat);
    assert(r->left->kind == Kind::Star && r->left->left->kind == Kind::Union);
    assert(r->right->kind == Kind::Symbol && r->right->symbol == '1');
    assert(size(r) == 6);
    assert(tree(parse_regex("ab|c*")) ==
           "unión\n    concatenación\n        a\n        b\n    estrella\n        c\n");
}

static void test_epsilon_and_empty() {
    assert(parse_regex("%")->kind == Kind::Epsilon);
    assert(parse_regex("ε")->kind == Kind::Epsilon);
    assert(parse_regex("@")->kind == Kind::Empty);
    assert(parse_regex("∅")->kind == Kind::Empty);
    assert(to_string(parse_regex("(0|%)1*")) == "(0|ε)1*");
    assert(to_string(parse_regex("(0|ε)1*")) == "(0|ε)1*");
    assert(to_string(parse_regex("@*")) == "∅*");
    assert(to_string(parse_regex(" 0* 1 0* ")) == "0*10*");
}

static void test_round_trip() {
    // Lo que se escribe se vuelve a leer y se escribe igual, con los paréntesis justos.
    std::vector<std::string> expressions = {
        "(0|1)*1",     "((0|1)(0|1))*", "0*10*10*",      "1*(01*01*)*", "(1|01*0)*", "(0|10)*(ε|1)",
        "(0|ε)1*",     "(01)*|(10)*",   "(1|01*01*0)*",  "(ab|a)*",     "(a*)*",     "(a|a)*b",
        "∅*",          "a|b|c",         "(a|b)(c|d)",    "a(b|c)*d",    "0|1*",      "(0|1*)*",
    };
    for (const std::string& text : expressions) {
        RegexPtr r = parse_regex(text);
        assert(to_string(r) == text);
        assert(to_string(parse_regex(to_string(r))) == text);
        assert(to_string(parse_regex(to_string_full(r))) == text);
    }
    // Paréntesis de más: se leen y no se vuelven a escribir.
    assert(to_string(parse_regex("((0)|(1))*")) == "(0|1)*");
    assert(to_string(parse_regex("(a(b))c")) == "abc");
    assert(to_string(parse_regex("a**")) == "(a*)*");
}

static void test_simplified_operations() {
    RegexPtr r = parse_regex("0|1");
    assert(to_string(simple_union(r, empty_set())) == "0|1");
    assert(to_string(simple_union(empty_set(), r)) == "0|1");
    assert(simple_concat(r, empty_set())->kind == Kind::Empty);
    assert(simple_concat(empty_set(), r)->kind == Kind::Empty);
    assert(to_string(simple_concat(r, epsilon())) == "0|1");
    assert(to_string(simple_concat(epsilon(), r)) == "0|1");
    assert(simple_star(empty_set())->kind == Kind::Epsilon);
    assert(simple_star(epsilon())->kind == Kind::Epsilon);
    assert(to_string(simple_star(r)) == "(0|1)*");
}

static std::size_t test_malformed() {
    std::ifstream file("errors/malformed.txt");
    assert(file);
    std::string line;
    std::size_t count = 0;
    while (std::getline(file, line)) {
        if (line.empty() || line[0] == '#') {
            continue;
        }
        assert(is_malformed(line));
        count++;
    }
    assert(count == 9);
    assert(is_malformed(""));
    assert(is_malformed("   "));
    // El mensaje dice dónde está el problema.
    try {
        parse_regex("0|*");
        assert(false);
    } catch (const std::runtime_error& error) {
        assert(std::string(error.what()) == "posición 3: se esperaba un símbolo o un paréntesis, y hay *");
    }
    return count;
}

int main() {
    test_precedence();
    test_epsilon_and_empty();
    test_round_trip();
    test_simplified_operations();
    std::size_t malformed = test_malformed();
    std::printf("test_regex: ok (%zu expresiones mal formadas rechazadas)\n", malformed);
}
test_thompson.cppDescargar test_thompson.cpp
// Pruebas de la construcción de Thompson (sesión A).
// Cada expresión de los apuntes se convierte en un NFA y se compara con una función de C++
// que decide el mismo lenguaje mirando la cadena completa, sobre todas las cadenas cortas.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <functional>
#include <map>
#include <sstream>
#include <string>
#include <vector>

#include "nfa.h"
#include "regex.h"
#include "thompson.h"
#include "words.h"

using Predicate = std::function<bool(const std::string&)>;

static int count_of(const std::string& w, char c) {
    int total = 0;
    for (char x : w) {
        total += (x == c);
    }
    return total;
}

static bool contains(const std::string& w, const std::string& piece) {
    return w.find(piece) != std::string::npos;
}

// w es una repetición de la pieza: ε, pieza, pieza pieza, …
static bool is_power_of(const std::string& w, const std::string& piece) {
    if (w.size() % piece.size() != 0) {
        return false;
    }
    for (std::size_t i = 0; i < w.size(); i++) {
        if (w[i] != piece[i % piece.size()]) {
            return false;
        }
    }
    return true;
}

// La forma del NFA de Thompson: un solo estado de aceptación, del que no sale nada; al
// inicial no entra nada; de cada estado salen a lo sumo dos flechas; y el número de estados
// es exactamente el doble del número de hojas, uniones y estrellas.
static void check_shape(const RegexPtr& r, const Nfa& n) {
    assert(n.accept.size() == 1);
    assert(n.states.size() == 2 * count_without_concat(r));
    assert(n.states.size() <= 2 * size(r));
    std::map<std::string, std::size_t> out;
    for (const auto& [key, targets] : n.delta) {
        out[key.first] += targets.size();
        assert(targets.count(n.start) == 0);
    }
    for (const std::string& q : n.states) {
        assert(out[q] <= 2);
    }
    assert(out[*n.accept.begin()] == 0);
}

// Compara L(r) con el predicado sobre todas las cadenas de longitud a lo sumo max_len.
static std::size_t check_language(const std::string& text, const std::vector<char>& alphabet, std::size_t max_len,
                                  const Predicate& in_language) {
    RegexPtr r = parse_regex(text);
    Nfa n = thompson(r, alphabet);
    check_shape(r, n);
    std::vector<std::string> words = all_strings(alphabet, max_len);
    for (const std::string& w : words) {
        assert(accepts(n, w) == in_language(w));
    }
    return words.size();
}

// Dos expresiones describen el mismo lenguaje, hasta longitud max_len.
static void check_same(const std::string& text1, const std::string& text2, const std::vector<char>& alphabet,
                       std::size_t max_len) {
    Nfa n1 = thompson(parse_regex(text1), alphabet);
    Nfa n2 = thompson(parse_regex(text2), alphabet);
    for (const std::string& w : all_strings(alphabet, max_len)) {
        assert(accepts(n1, w) == accepts(n2, w));
    }
}

static std::size_t test_examples() {
    std::vector<char> binary = {'0', '1'};
    std::size_t count = 0;
    auto check = [&](const std::string& text, const Predicate& in_language) {
        check_language(text, binary, 9, in_language);
        count++;
    };
    // Las tres expresiones que se leen en la sesión A.
    check("(0|1)*1", [](const std::string& w) { return !w.empty() && w.back() == '1'; });
    check("((0|1)(0|1))*", [](const std::string& w) { return w.size() % 2 == 0; });
    check("0*10*10*", [](const std::string& w) { return count_of(w, '1') == 2; });
    // Las que se escriben: número par de ceros, sin 11.
    check("1*(01*01*)*", [](const std::string& w) { return count_of(w, '0') % 2 == 0; });
    check("(1|01*0)*", [](const std::string& w) { return count_of(w, '0') % 2 == 0; });
    check("(0|10)*(%|1)", [](const std::string& w) { return !contains(w, "11"); });
    // Los dos intentos fallidos de "sin 11": uno describe de menos y el otro de más.
    check("(0|10)*", [](const std::string& w) { return !contains(w, "11") && (w.empty() || w.back() == '0'); });
    check("(0|10)*1*", [](const std::string& w) {
        // Sin 11 antes de la cola final de unos: quitando esa cola, queda vacío o termina en 0 sin 11.
        std::size_t end = w.size();
        while (end > 0 && w[end - 1] == '1') {
            end--;
        }
        return !contains(w.substr(0, end), "11");
    });
    // Las de las preguntas de repaso de la guía.
    check("(0|%)1*", [](const std::string& w) { return !contains(w.substr(w.empty() ? 0 : 1), "0"); });
    check("(01)*|(10)*", [](const std::string& w) { return is_power_of(w, "01") || is_power_of(w, "10"); });
    check("(1|01*01*0)*", [](const std::string& w) { return count_of(w, '0') % 3 == 0; });
    // Σ*, y las cadenas que contienen 101.
    check("(0|1)*", [](const std::string&) { return true; });
    check("(0|1)*101(0|1)*", [](const std::string& w) { return contains(w, "101"); });
    // (ab ∪ a)*: no empieza con b y no tiene bb.
    check_language("(ab|a)*", {'a', 'b'}, 9,
                   [](const std::string& w) { return (w.empty() || w[0] == 'a') && !contains(w, "bb"); });
    count++;
    // Los enteros sin ceros a la izquierda, sobre los diez dígitos.
    check_language("0|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*",
                   {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}, 3,
                   [](const std::string& w) { return w == "0" || (!w.empty() && w[0] != '0'); });
    count++;
    return count;
}

static void test_cases_of_the_definition() {
    std::vector<char> binary = {'0', '1'};
    check_language("@", binary, 6, [](const std::string&) { return false; });
    check_language("%", binary, 6, [](const std::string& w) { return w.empty(); });
    check_language("0", binary, 6, [](const std::string& w) { return w == "0"; });
    check_language("0|1", binary, 6, [](const std::string& w) { return w == "0" || w == "1"; });
    check_language("01", binary, 6, [](const std::string& w) { return w == "01"; });
    check_language("0*", binary, 6, [](const std::string& w) { return count_of(w, '1') == 0; });
}

static void test_identities() {
    std::vector<char> binary = {'0', '1'};
    std::vector<std::string> some = {"0", "(0|1)*1", "0*10*10*", "(01)*|(10)*", "%", "@"};
    for (const std::string& r : some) {
        std::string p = "(" + r + ")";
        check_same(p + "|@", r, binary, 6);   // R ∪ ∅ = R
        check_same(p + "@", "@", binary, 6);  // R∅ = ∅
        check_same("@" + p, "@", binary, 6);  // ∅R = ∅
        check_same(p + "%", r, binary, 6);    // Rε = R
        check_same("%" + p, r, binary, 6);    // εR = R
        check_same(p + "|" + p, r, binary, 6);       // R ∪ R = R
        check_same(p + "**", p + "*", binary, 6);    // (R*)* = R*
    }
    // ∅* = {ε}: la estrella de ∅ no es ∅.
    check_same("@*", "%", binary, 6);
    check_same("%*", "%", binary, 6);
    // Las dos trampas: R ∪ ε no es R, y Rε no es ∅.
    Nfa with_eps = thompson(parse_regex("0|%"), binary);
    assert(accepts(with_eps, "") && accepts(with_eps, "0"));
    assert(!accepts(thompson(parse_regex("0"), binary), ""));
    // Otras igualdades que se usan en los apuntes.
    check_same("(0|1)*", "(0*1*)*", binary, 9);
    check_same("1*(01*01*)*", "(1|01*0)*", binary, 9);
    check_same("(0|10)*(%|1)", "(%|1)(0|01)*", binary, 9);
    // Las abreviaturas de las herramientas, escritas con las tres operaciones.
    check_language("00*", binary, 7, [](const std::string& w) { return !w.empty() && count_of(w, '1') == 0; });
    check_language("(01)(01)((01)|%)", binary, 7, [](const std::string& w) { return w == "0101" || w == "010101"; });
}

static void test_run() {
    // La ejecución que copian los apuntes: (0|1)*1 con 011.
    RegexPtr r = parse_regex("(0|1)*1");
    Nfa n = thompson(r);
    assert(n.states.size() == 10);
    assert(n.start == "q0" && n.accept == StateSet{"q9"});
    std::vector<StateSet> sets = run(n, "011");
    assert(sets.size() == 4);
    assert(show_set(n, sets[0]) == "{q0, q1, q2, q4, q7, q8}");
    assert(show_set(n, sets[1]) == "{q1, q2, q3, q4, q6, q7, q8}");
    assert(show_set(n, sets[2]) == "{q1, q2, q4, q5, q6, q7, q8, q9}");
    assert(show_set(n, sets[3]) == "{q1, q2, q4, q5, q6, q7, q8, q9}");
    assert(accepts(n, "011") && !accepts(n, "010") && !accepts(n, ""));
    // El archivo de machines/ es lo que escribe la construcción, y se vuelve a leer igual.
    Nfa from_file = load_nfa("machines/ends_in_1.nfa");
    std::ostringstream written;
    std::ostringstream built;
    write_nfa(written, from_file);
    write_nfa(built, n);
    assert(written.str() == built.str());
    // (ab ∪ a)*, el de las preguntas de repaso.
    Nfa second = load_nfa("machines/ab_or_a_star.nfa");
    std::ostringstream written2;
    std::ostringstream built2;
    write_nfa(written2, second);
    write_nfa(built2, thompson(parse_regex("(ab|a)*")));
    assert(written2.str() == built2.str());
    assert(second.states.size() == 10);
    // Todo .dfa es un .nfa válido.
    Nfa from_dfa = load_nfa("machines/even_ones.dfa");
    for (const std::string& w : all_strings({'0', '1'}, 8)) {
        assert(accepts(from_dfa, w) == (count_of(w, '1') % 2 == 0));
    }
}

static void test_closure_with_cycles() {
    // (a*)* tiene un ciclo de transiciones ε: la clausura debe terminar.
    Nfa n = thompson(parse_regex("(a*)*b"), {'a', 'b'});
    for (const std::string& w : all_strings({'a', 'b'}, 8)) {
        bool expected = !w.empty() && w.back() == 'b' && count_of(w, 'b') == 1;
        assert(accepts(n, w) == expected);
    }
}

int main() {
    test_cases_of_the_definition();
    std::size_t examples = test_examples();
    test_identities();
    test_run();
    test_closure_with_cycles();
    std::printf("test_thompson: ok (%zu expresiones contra su predicado)\n", examples);
}

Laboratorio

Archivos de partida del laboratorio de la semana.

lab/mini_grep/MakefileDescargar lab/mini_grep/Makefile
TIEMPO = 2
include ../../../lab.mk
lab/mini_grep/README.mdDescargar lab/mini_grep/README.md
# Un grep pequeño

`grep` recibe un patrón y un texto, y dice qué líneas del texto coinciden con el patrón. En este laboratorio
escriben la parte central de esa herramienta: reciben una expresión regular y una lista de líneas, y dicen por
cada línea si la expresión la describe **completa**.

Son las tres construcciones de la sesión A, una detrás de otra: el árbol de la expresión, el NFA de Thompson
y la simulación con el conjunto de estados activos.

## Entrada

La primera línea es la expresión regular. Después viene el bloque de cadenas de
[`code/formats.md`](../../../formats.md): una línea `strings: k` y $k$ líneas, una cadena por línea.

```text
(a|b)*abb
strings: 5
abb
babb

ab
abba
```

La expresión se escribe con la sintaxis del código de la semana, sin $\varepsilon$ ni $\emptyset$:

- Un **símbolo** es una letra minúscula de `a` a `z` o un dígito de `0` a `9`.
- La **unión** es `|`, la **concatenación** no se escribe y la **estrella** es `*`.
- Los **paréntesis** agrupan.
- **Precedencia:** primero la estrella, después la concatenación, al final la unión. `ab|cd*` es
  $(\mathtt{ab}) \cup (\mathtt{c}(\mathtt{d}^*))$.

Con más precisión, la expresión sigue esta gramática, y no tiene espacios:

```text
unión         →  concatenación ( '|' concatenación )*
concatenación →  estrella estrella*
estrella      →  átomo '*'*
átomo         →  símbolo  |  '(' unión ')'
```

Entonces una estrella puede llevar otra encima, `a**`, y puede haber paréntesis de más, `((a))`. No hay
alternativas vacías ni paréntesis vacíos: `a||b`, `(a|)` y `()` no aparecen.

Sobre las cadenas:

- **Una línea vacía es la cadena vacía $\varepsilon$**, y también hay que responder por ella.
- Las cadenas están formadas solo por letras minúsculas y dígitos. Pueden tener símbolos que no aparecen en
  la expresión: una cadena así nunca coincide.
- En esta entrada no hay comentarios: ninguna línea empieza con `#`.

## Salida

Una línea por cada cadena, en el mismo orden: `acepta` si la expresión describe la cadena completa, y
`rechaza` si no.

Un `grep` de verdad imprimiría las líneas que coinciden. Aquí se imprime un veredicto por línea por una razón
práctica: el juez compara la salida palabra por palabra, sin mirar los saltos de línea, y una línea vacía que
coincide no dejaría ninguna huella en la salida. Con un veredicto por cadena, la respuesta a la cadena vacía
se ve, y un programa que no imprime nada falla siempre.

## Límites

- La expresión tiene entre 1 y 200 caracteres, y siempre está bien formada: no tienen que detectar errores.
- $1 \leq k \leq 20\,000$.
- Las longitudes de las cadenas suman a lo sumo 100 000. Una sola cadena puede tener esa longitud.

## Ejemplo

Para la entrada de arriba, la salida es:

```text
acepta
acepta
rechaza
rechaza
rechaza
```

La expresión describe las cadenas de letras `a` y `b` que terminan en `abb`. La tercera cadena es la vacía. La
última contiene `abb`, pero no termina ahí: la expresión tiene que describir la línea completa, como con
`grep -x`.

## Tiempo

2 segundos por caso. Se compila con `g++ -Wall -Wextra -std=c++20 -O2`.

El NFA de Thompson de una expresión de 200 caracteres tiene a lo sumo 400 estados. Simularlo con el conjunto
de estados activos cuesta, por cada símbolo de la cadena, una pasada por los estados activos: en total, del
orden de $100\,000 \cdot 400$ pasos en el peor caso, que entra con holgura.

Lo que **no** entra es el backtracking: probar una alternativa y, si falla, volver atrás y probar la otra. Uno
de los casos es la expresión `(a|a)*b` contra una línea de 50 000 letras `a`. No hay ninguna `b`, así que la
respuesta es `rechaza`, y una búsqueda con backtracking la encuentra después de probar las $2^{50\,000}$
maneras de elegir una rama para cada letra. Otros casos tienen estrellas dentro de estrellas, como
`(a*b*)*c`, que hacen lo mismo.

Dos cuidados más:

- **Los ciclos de transiciones $\varepsilon$.** Una estrella sobre algo que puede ser vacío, como `(a*)*`, da
  un NFA en el que se puede volver al mismo estado sin leer nada. La clausura $\varepsilon$ tiene que marcar
  los estados ya visitados, o no termina.
- **No construyan el DFA completo.** Uno de los casos es "el símbolo que está 38 posiciones antes del último
  es una `a`", y su DFA tiene más de $2^{38}$ estados. El NFA tiene menos de 400.

## Qué se practica aquí

En `code/week-03` están `regex.h`, `thompson.h` y `nfa.h`, que hacen estos tres pasos para los ejemplos de los
apuntes, y pueden leerlos cuanto quieran. `solution.cpp` se escribe **sin incluirlos**: el juez compila ese
único archivo. Tampoco conviene copiarlos tal cual. Están escritos para parecerse a las definiciones, con los
estados guardados por su nombre en un `std::set`, y así la simulación no alcanza a pasar el caso más grande.

El trabajo del laboratorio es escribir los tres pasos de forma que el tercero cueste lo que dice el análisis:

- Los estados son **números** de 0 a $m - 1$, y $\delta$ son arreglos indexados por el estado. En el NFA de
  Thompson, de cada estado sale una flecha con un símbolo, o una o dos transiciones $\varepsilon$, o nada: no
  hace falta ninguna estructura más complicada.
- El conjunto de estados activos es una **lista** de estados más un arreglo de marcas, que dice si un estado
  ya está en la lista. Así agregar un estado y preguntar si ya está cuestan tiempo constante. Un
  `std::set<int>` también pasa, más justo.

## Cómo avanzar

```sh
make        # compila solution.cpp en build/
make test   # corre el juez con todos los casos
```

Los cuatro casos grandes no están guardados: `make test` los genera con los programas `casos/gen_NN.cpp`.

1. **Leer la entrada.** El esqueleto ya lee la expresión, la línea `strings:` y las cadenas, con
   `std::getline`: una línea vacía es una cadena, y `>>` se la saltaría.
2. **El árbol de la expresión.** Escriban el parser con una función por cada línea de la gramática:
   `parse_union` llama a `parse_concat`, que llama a `parse_star`, que llama a `parse_atom`. Cada función
   devuelve el nodo que construyó. El esqueleto trae un `struct Node` como propuesta. Antes de seguir,
   comprueben a mano el árbol de `ab|cd*` y el de `(a|b)*abb`.
3. **El NFA de Thompson.** Recorran el árbol de las hojas a la raíz. Cada nodo devuelve su pieza: el estado de
   entrada y el de salida. Un símbolo crea dos estados y una flecha. La unión y la estrella crean dos estados
   y cuatro transiciones $\varepsilon$. La concatenación no crea estados: une las dos piezas con una
   transición $\varepsilon$.
4. **La simulación.** Empiecen con la clausura $\varepsilon$ del estado inicial. Por cada símbolo de la línea,
   armen la lista siguiente: para cada estado activo que tenga una flecha con ese símbolo, agreguen el destino
   y su clausura $\varepsilon$. Al final, la respuesta es si el estado de aceptación está entre los activos.
   Si la lista queda vacía a mitad de la línea, ya pueden responder `rechaza`.
5. **Los casos de borde.** Antes de correr el juez, respondan a mano: ¿qué responde `a*` con la línea vacía?
   ¿Y `a`? ¿Qué pasa en su clausura $\varepsilon$ con `(a*)*`?
6. **El caso grande.** Corran `casos/11.in`, que es `(a|a)*b` con líneas de unas decenas de letras, y después
   el juez completo.

Para probar una expresión propia sin escribir un archivo:

```sh
printf '(0|1)*1\nstrings: 3\n011\n\n010\n' | build/solution
```

Debe imprimir `acepta`, `rechaza`, `rechaza`.

Mientras desarrollan, compilen con sanitizers, como explica [`labs/README.md`](../../../../labs/README.md).

## Para seguir

Opcional, sin casos en el juez.

- Agreguen las abreviaturas `+` y `?` al parser, sin agregar tipos de nodo: `R+` es $RR^*$ y `R?` necesita
  una pieza para $\varepsilon$.
- Hagan que el programa busque como `grep` sin `-x`: que acepte una línea si la expresión describe **alguna
  subcadena** suya. No hace falta cambiar la simulación: basta cambiar el autómata. ¿Cómo?
- Guarden cada conjunto de estados activos la primera vez que aparece, con un número, y también a qué
  conjunto lleva con cada símbolo. Es la construcción de subconjuntos de la semana pasada hecha sobre la
  marcha. Midan cuántos conjuntos distintos aparecen en `casos/14.in`.
lab/mini_grep/solution.cppDescargar lab/mini_grep/solution.cpp
// Un grep pequeño. Lee una expresión regular y una lista de líneas, e imprime por cada línea
// si la expresión la describe completa.
#include <iostream>
#include <string>
#include <vector>

// Un nodo del árbol de la expresión. Es una propuesta: pueden cambiarla.
// Los nodos se guardan en un std::vector y los hijos son posiciones en ese vector, así no
// hacen falta punteros.
struct Node {
    char kind;    // 'a' un símbolo, '|' unión, '.' concatenación, '*' estrella
    char symbol;  // solo si kind == 'a'
    int left;     // el hijo izquierdo, o el único hijo de una estrella; -1 si no tiene
    int right;    // el hijo derecho; -1 si no tiene
};

// El NFA de Thompson, también como propuesta. De cada estado sale una sola flecha con un
// símbolo o, como mucho, dos transiciones ε: δ cabe en tres arreglos indexados por el estado.
struct Nfa {
    std::vector<char> symbol;  // el símbolo de la flecha que sale del estado, o '\0' si no hay
    std::vector<int> next;     // a dónde lleva esa flecha
    std::vector<int> eps1;     // destinos de las transiciones ε, o -1
    std::vector<int> eps2;
    int start = 0;
    int accept = 0;
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::string expression;
    std::getline(std::cin, expression);
    std::vector<Node> nodes;
    // Por hacer (paso 2): el árbol de expression, respetando la precedencia.

    Nfa n;
    // Por hacer (paso 3): el NFA de Thompson del árbol.

    std::string line;
    std::getline(std::cin, line);  // strings: k
    int k = std::stoi(line.substr(line.find(':') + 1));
    for (int i = 0; i < k; i++) {
        std::getline(std::cin, line);  // una línea vacía es la cadena ε
        // Por hacer (paso 4): simular n con line, llevando el conjunto de estados activos,
        // e imprimir acepta o rechaza.
    }
    // Este esqueleto no imprime nada, así que el juez da WA en todos los casos.
    return static_cast<int>(nodes.size() + n.symbol.size());
}

Compilación

Cómo se compilan y ejecutan los ejemplos.

MakefileDescargar Makefile
# Semana 3: expresiones regulares, construcción de Thompson y eliminación de estados.
# Se usa dentro del entorno del curso.
#
#   make           compila los programas de la clase en build/
#   make test      corre las pruebas de los ejemplos, con sanitizers
#   make bench     compara el backtracking con la simulación del NFA (compila con -O2)
#   make clean     borra lo generado
#
# Las pruebas leen los autómatas de machines/, así que se corren desde esta carpeta.
# El laboratorio está en lab/mini_grep y tiene su propio Makefile: estas reglas no lo tocan.

CXX = g++
CXXFLAGS = -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined
BENCHFLAGS = -Wall -Wextra -std=c++20 -O2
BUILD = build
PROGRAMS = regex_tree regex_lang regex_diff thompson run_nfa eliminate orders growth backtrack
TESTS = test_regex test_thompson test_elimination test_backtrack
HEADERS = regex.h nfa.h dfa.h thompson.h gnfa.h backtrack.h words.h

.PHONY: all test bench clean

all: $(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%) $(BUILD)/matchers_bench

$(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(HEADERS) | $(BUILD)
	$(CXX) $(CXXFLAGS) $< -o $@

# Las mediciones se compilan con -O2 y sin sanitizers, como el juez.
$(BUILD)/matchers_bench: matchers_bench.cpp $(HEADERS) | $(BUILD)
	$(CXX) $(BENCHFLAGS) $< -o $@

$(BUILD):
	mkdir -p $@

test: $(TESTS:%=$(BUILD)/%) $(PROGRAMS:%=$(BUILD)/%)
	@for t in $(TESTS); do $(BUILD)/$$t || exit 1; done
	@echo "Todas las pruebas pasaron."

bench: $(BUILD)/matchers_bench
	$(BUILD)/matchers_bench

clean:
	rm -rf $(BUILD)