Semana 2 — No determinismo

Objetivos

  • Definir un NFA, con transiciones ε\varepsilon, y explicar qué significa que acepte una cadena.
  • Convertir un NFA en un DFA con la construcción de subconjuntos, y demostrar que son equivalentes.
  • Usar NFA para demostrar que los lenguajes regulares son cerrados bajo unión, concatenación y estrella.
  • Dar un lenguaje en el que el DFA necesita exponencialmente más estados que el NFA.

Sesión A — No determinismo: NFA y transiciones ε

Lectura: Apuntes, semana 2.

Apoyo: Sipser, sec. 1.2 (Nondeterminism), hasta la definición formal. Erickson, Models of Computation, nota 4 (Nondeterministic automata).

Temas:

  • Un diseño que con DFA cuesta: “el tercer símbolo desde el final es 1\mathtt{1}”. Con un NFA sale en cuatro estados.
  • Qué cambia: varias transiciones con el mismo símbolo, ninguna, o transiciones ε\varepsilon.
  • Tres maneras de pensar el no determinismo: adivinar bien, explorar todos los caminos a la vez, o un árbol de ejecuciones. Acepta si algún camino termina en aceptación.
  • Definición formal: δ\delta devuelve un conjunto de estados, δ:Q×(Σ∪{ε})→P(Q)\delta : Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q).
  • Seguir un NFA a mano: el conjunto de estados activos después de cada símbolo.
  • Clausura ε\varepsilon de un conjunto de estados.
  • Todo DFA es un NFA. La pregunta de la sesión B: ¿los NFA reconocen algo más?
  • Error común: creer que el NFA acepta si todos los caminos aceptan, o que “elige al azar”.

Sesión B — Construcción de subconjuntos · Propiedades de cierre

Lectura: Apuntes, semana 2.

Apoyo: Sipser, sec. 1.2 (Equivalence of NFAs and DFAs y Closure under the regular operations). Erickson, Models of Computation, nota 4.

Temas:

  • La idea: el conjunto de estados activos es un solo estado de un DFA.
  • Construcción de subconjuntos, con clausura ε\varepsilon, sobre el ejemplo de la sesión A. Solo se construyen los subconjuntos alcanzables.
  • Demostración de la equivalencia, por inducción sobre la longitud de la cadena.
  • El costo: hasta 2n2^n estados. Para “el kk-ésimo símbolo desde el final es 1\mathtt{1}”, el DFA necesita 2k2^k estados; se justifica con intuición y se demuestra en la semana 4.
  • Cierre bajo unión, concatenación y estrella, con construcciones sobre NFA y transiciones ε\varepsilon.
  • El detalle de la estrella: hace falta un estado inicial nuevo, y por qué no basta con marcar el anterior como de aceptación.
  • Cierre bajo reverso, como ejercicio de construcción.
  • Error común: para el complemento, intercambiar los estados de aceptación de un NFA. Solo funciona en un DFA.

Laboratorio — De NFA a DFA

  1. Leer un NFA con transiciones ε\varepsilon y escribir un DFA equivalente.
  2. Calcular la clausura ε\varepsilon con una búsqueda en el grafo de transiciones ε\varepsilon.
  3. Generar solo los subconjuntos alcanzables, con una cola, y darles nombres nuevos.
  4. Comprobar la salida con el verificador del problema, que compara lenguajes y no nombres de estados.
  5. Medir cuántos estados sale para “el kk-ésimo símbolo desde el final es 1\mathtt{1}” con kk de 1 a 12, y anotar la tabla.

Preguntas de repaso

  1. Sigan a mano un NFA con transiciones ε\varepsilon con una cadena de cinco símbolos, anotando el conjunto de estados activos.
  2. ¿Por qué el estado de aceptación del DFA construido es “cualquier subconjunto que contenga un estado de aceptación”?
  3. Apliquen la construcción de subconjuntos a un NFA de tres estados y dibujen solo los estados alcanzables.
  4. Den un NFA para el que intercambiar los estados de aceptación no da el complemento.
  5. Con la construcción de la estrella, ¿por qué ε\varepsilon siempre queda aceptada? Muestren qué falla en la construcción sin estado inicial nuevo.

Código de la semana

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

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

Ejemplos

Los programas que usan los apuntes y la clase.

combine.cppDescargar combine.cpp
// Construcciones de cierre sobre NFA:
//   combine union A.nfa B.nfa     combine concat A.nfa B.nfa
//   combine star A.nfa            combine reverse A.nfa
// Escribe el NFA resultante en formato .nfa. Los archivos .dfa también sirven de entrada.
#include <iostream>
#include <stdexcept>
#include <string>

#include "nfa.h"

int main(int argc, char** argv) {
    std::string mode = argc >= 2 ? argv[1] : "";
    bool two = (mode == "union" || mode == "concat");
    bool one = (mode == "star" || mode == "reverse");
    if (!(two && argc == 4) && !(one && argc == 3)) {
        std::cerr << "uso: combine (union|concat) A.nfa B.nfa\n     combine (star|reverse) A.nfa\n";
        return 2;
    }
    try {
        Nfa a = load_nfa(argv[2]);
        Nfa result;
        if (mode == "union") {
            result = nfa_union(a, load_nfa(argv[3]));
            std::cout << "# Unión de " << argv[2] << " y " << argv[3] << ".\n";
        } else if (mode == "concat") {
            result = nfa_concat(a, load_nfa(argv[3]));
            std::cout << "# Concatenación de " << argv[2] << " y " << argv[3] << ".\n";
        } else if (mode == "star") {
            result = nfa_star(a);
            std::cout << "# Estrella de " << argv[2] << ".\n";
        } else {
            result = nfa_reverse(a);
            std::cout << "# Reverso de " << argv[2] << ".\n";
        }
        write_nfa(std::cout, result);
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
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.
// Además: leer y escribir ese formato, la función de transición extendida, la construcción
// del producto y el complemento.
// Es el dfa.h de la semana 1, sin cambios: la construcción de subconjuntos de nfa.h produce un Dfa.
#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
kth_nfa.cppDescargar kth_nfa.cpp
// Escribe el NFA de "el k-ésimo símbolo desde el final es 1": kth_nfa K
#include <cstdlib>
#include <iostream>

#include "kth.h"

int main(int argc, char** argv) {
    int k = argc == 2 ? std::atoi(argv[1]) : 0;
    if (k < 1 || k > 30) {
        std::cerr << "uso: kth_nfa K, con K entre 1 y 30\n";
        return 2;
    }
    std::cout << "# El símbolo número " << k << " desde el final es 1.\n";
    write_nfa(std::cout, kth_from_end(k));
}
kth_table.cppDescargar kth_table.cpp
// Cuántos estados da la construcción de subconjuntos para "el k-ésimo símbolo desde el final
// es 1", con k de 1 a K: kth_table [K]. Por defecto, K = 12.
#include <cstdio>
#include <cstdlib>

#include "kth.h"

int main(int argc, char** argv) {
    int max_k = argc == 2 ? std::atoi(argv[1]) : 12;
    if (max_k < 1 || max_k > 16) {
        std::fprintf(stderr, "uso: kth_table [K], con K entre 1 y 16\n");
        return 2;
    }
    std::printf(" k   estados del NFA   subconjuntos posibles   estados del DFA (alcanzables)\n");
    for (int k = 1; k <= max_k; k++) {
        Nfa n = kth_from_end(k);
        Dfa d = subset_construction(n);
        std::printf("%2d   %15zu   %21lu   %29zu\n", k, n.states.size(), 1UL << n.states.size(), d.states.size());
    }
}
kth.hDescargar kth.h
// El NFA de "el k-ésimo símbolo desde el final es 1", con k + 1 estados.
#ifndef KTH_H
#define KTH_H

#include <string>

#include "nfa.h"

// q0 espera y, al leer un 1, puede adivinar que ese es el k-ésimo desde el final y pasar a q1.
// De q1 a qk se avanza con cualquier símbolo, y de qk no sale nada.
// Con k = 3 es la máquina de machines/third_from_end.nfa.
inline Nfa kth_from_end(int k) {
    Nfa n;
    n.alphabet = {'0', '1'};
    for (int i = 0; i <= k; i++) {
        n.states.push_back("q" + std::to_string(i));
    }
    n.start = "q0";
    n.accept = {"q" + std::to_string(k)};
    n.delta[{"q0", '0'}] = {"q0"};
    n.delta[{"q0", '1'}] = {"q0", "q1"};
    for (int i = 1; i < k; i++) {
        n.delta[{n.states[i], '0'}] = {n.states[i + 1]};
        n.delta[{n.states[i], '1'}] = {n.states[i + 1]};
    }
    return n;
}

#endif
nfa_to_dfa.cppDescargar nfa_to_dfa.cpp
// Construcción de subconjuntos: nfa_to_dfa ARCHIVO.nfa
// Escribe en la salida estándar, en formato .dfa, un DFA equivalente con solo los subconjuntos
// alcanzables. Con - en lugar del archivo, lee la descripción de la entrada estándar.
#include <iostream>
#include <stdexcept>
#include <string>

#include "nfa.h"

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: nfa_to_dfa ARCHIVO.nfa\n";
        return 2;
    }
    try {
        std::string path = argv[1];
        Nfa n = (path == "-") ? read_nfa(std::cin) : load_nfa(path);
        Dfa d = subset_construction(n);
        std::cout << "# Construcción de subconjuntos de " << (path == "-" ? "la entrada" : path) << ": "
                  << n.states.size() << " estados en el NFA, " << d.states.size() << " en el DFA.\n";
        write_dfa(std::cout, d);
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
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.
// La diferencia con el Dfa está en un solo tipo: δ devuelve un conjunto de estados.
// Además: leer y escribir el formato, la clausura ε, la simulación con el conjunto de estados
// activos, la construcción de subconjuntos y las construcciones de cierre (unión,
// concatenación, estrella y reverso).
#ifndef NFA_H
#define NFA_H

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

#include "dfa.h"

// ε no es un símbolo del alfabeto. En la clave de δ se representa con un carácter que ningún
// archivo puede usar como símbolo.
inline constexpr 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
// ------------------------------------------------------------

// Lanza std::runtime_error si n no cumple la definición. A diferencia de check_dfa, no pide
// que δ sea total: un par sin transiciones vale ∅.
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
// ------------------------------------------------------------

// Lee una descripción completa, hasta el final de la entrada. Si un par de estado y símbolo
// aparece en varias líneas, sus destinos se juntan.
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_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;
    };

    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… (uno o más destinos)");
        }
        char symbol = (words[1] == "eps") ? EPS : words[1][0];
        for (std::size_t i = 2; i < words.size(); i++) {
            n.delta[{words[0], symbol}].insert(words[i]);
        }
    }
    try {
        check_nfa(n);
    } catch (const std::runtime_error& error) {
        throw std::runtime_error(std::string("no es un NFA: ") + error.what());
    }
    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: una línea por cada par con al menos un destino, con los
// destinos en el orden de states. Lo que escribe se puede volver a leer con read_nfa.
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> columns = n.alphabet;
    columns.push_back(EPS);
    for (const std::string& state : n.states) {
        for (char a : columns) {
            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));
            for (const std::string& target : n.states) {
                if (it->second.count(target) > 0) {
                    out << ' ' << target;
                }
            }
            out << '\n';
        }
    }
}

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

// δ(q, a), con a ∈ Σ o a = EPS. Un par sin transiciones da ∅.
inline StateSet delta_of(const Nfa& n, const std::string& q, char a) {
    auto it = n.delta.find({q, a});
    return it == n.delta.end() ? StateSet{} : it->second;
}

// Clausura ε: E(S) son los estados a los que se llega desde algún estado de S con cero o más
// transiciones ε. Es una búsqueda en el grafo que solo tiene las flechas ε.
inline StateSet eps_closure(const Nfa& n, const StateSet& s) {
    StateSet closure = s;
    std::queue<std::string> pending;
    for (const std::string& q : s) {
        pending.push(q);
    }
    while (!pending.empty()) {
        std::string q = pending.front();
        pending.pop();
        for (const std::string& r : delta_of(n, q, EPS)) {
            if (closure.insert(r).second) {
                pending.push(r);
            }
        }
    }
    return closure;
}

// Un paso con el símbolo a desde un conjunto: primero todas las flechas con a que salen de
// algún estado de S, después la clausura ε. Es E(⋃ δ(q, a)), con q en S.
inline StateSet step(const Nfa& n, const StateSet& s, char a) {
    StateSet targets;
    for (const std::string& q : s) {
        StateSet next = delta_of(n, q, a);
        targets.insert(next.begin(), next.end());
    }
    return eps_closure(n, targets);
}

// La función extendida sobre conjuntos: δ*(S, ε) = E(S) y δ*(S, xa) = E(⋃ δ(q, a)), con q en δ*(S, x).
// δ*({q0}, w) es el conjunto de estados activos después de leer w.
inline StateSet delta_star(const Nfa& n, const StateSet& s, const std::string& w) {
    StateSet active = eps_closure(n, s);
    for (char a : w) {
        active = step(n, active, a);
    }
    return active;
}

// ¿S tiene algún estado de aceptación?
inline bool has_accept(const Nfa& n, const StateSet& s) {
    for (const std::string& q : s) {
        if (n.accept.count(q) > 0) {
            return true;
        }
    }
    return false;
}

// N acepta w si algún estado activo al final es de aceptación.
inline bool accepts(const Nfa& n, const std::string& w) {
    return has_accept(n, delta_star(n, {n.start}, w));
}

// Los conjuntos de estados activos: antes de leer nada y después de cada símbolo de w.
inline std::vector<StateSet> run(const Nfa& n, const std::string& w) {
    std::vector<StateSet> sequence = {eps_closure(n, {n.start})};
    for (char a : w) {
        sequence.push_back(step(n, sequence.back(), a));
    }
    return sequence;
}

// Un conjunto de estados escrito como {q0,q1}, en el orden de states y sin espacios, para que
// sirva de nombre de un estado en un archivo .dfa. El conjunto vacío es {}.
inline std::string set_name(const Nfa& n, const StateSet& s) {
    std::string name = "{";
    for (const std::string& q : n.states) {
        if (s.count(q) > 0) {
            name += (name.size() > 1 ? "," : "") + q;
        }
    }
    return name + "}";
}

// ------------------------------------------------------------
// De DFA a NFA y de NFA a DFA
// ------------------------------------------------------------

// Todo DFA es un NFA: la misma máquina, con δ(q, a) = {el único destino} y sin transiciones ε.
inline Nfa to_nfa(const Dfa& m) {
    Nfa n;
    n.states = m.states;
    n.alphabet = m.alphabet;
    n.start = m.start;
    n.accept = m.accept;
    for (const auto& [key, target] : m.delta) {
        n.delta[key] = {target};
    }
    return n;
}

// Construcción de subconjuntos. El DFA tiene un estado por cada conjunto de estados del NFA
// que se alcanza desde E({q0}):
//   inicial      E({q0})
//   transición   δ_D(S, a) = E(⋃ δ(q, a)), con q en S
//   aceptación   los S que contienen algún estado de F
// Solo genera los subconjuntos alcanzables, con una cola, en el orden en que aparecen.
// Si subsets no es nulo, deja ahí el conjunto que corresponde a cada estado del DFA.
inline Dfa subset_construction(const Nfa& n, std::vector<StateSet>* subsets = nullptr) {
    Dfa d;
    d.alphabet = n.alphabet;
    StateSet first = eps_closure(n, {n.start});
    d.start = set_name(n, first);

    std::vector<StateSet> found = {first};  // found[i] es el conjunto del estado d.states[i]
    std::set<StateSet> seen = {first};
    std::queue<StateSet> pending;
    pending.push(first);
    d.states.push_back(d.start);
    while (!pending.empty()) {
        StateSet s = pending.front();
        pending.pop();
        std::string name = set_name(n, s);
        if (has_accept(n, s)) {
            d.accept.insert(name);
        }
        for (char a : n.alphabet) {
            StateSet t = step(n, s, a);
            d.delta[{name, a}] = set_name(n, t);
            if (seen.insert(t).second) {
                found.push_back(t);
                d.states.push_back(set_name(n, t));
                pending.push(t);
            }
        }
    }
    check_dfa(d);
    if (subsets != nullptr) {
        *subsets = found;
    }
    return d;
}

// ------------------------------------------------------------
// Construcciones de cierre
// ------------------------------------------------------------

// Un nombre que no esté en used: name, o name con apóstrofos hasta que no choque.
inline std::string fresh_name(const std::vector<std::string>& used, std::string name) {
    StateSet taken(used.begin(), used.end());
    while (taken.count(name) > 0) {
        name += "'";
    }
    return name;
}

// El mismo NFA con prefix delante del nombre de cada estado. Sirve para que dos máquinas no
// compartan nombres: las construcciones necesitan Q1 ∩ Q2 = ∅.
inline Nfa with_prefix(const Nfa& n, const std::string& prefix) {
    Nfa result;
    result.alphabet = n.alphabet;
    result.start = prefix + n.start;
    for (const std::string& state : n.states) {
        result.states.push_back(prefix + state);
    }
    for (const std::string& state : n.accept) {
        result.accept.insert(prefix + state);
    }
    for (const auto& [key, targets] : n.delta) {
        for (const std::string& target : targets) {
            result.delta[{prefix + key.first, key.second}].insert(prefix + target);
        }
    }
    return result;
}

inline void require_same_alphabet(const Nfa& n1, const Nfa& n2) {
    std::set<char> sigma1(n1.alphabet.begin(), n1.alphabet.end());
    std::set<char> sigma2(n2.alphabet.begin(), n2.alphabet.end());
    if (sigma1 != sigma2) {
        throw std::runtime_error("la construcción necesita dos NFA con el mismo alfabeto");
    }
}

// Unión: un estado inicial nuevo s, con transiciones ε a los iniciales de N1 y de N2.
// F = F1 ∪ F2. Los estados de N1 pasan a llamarse 1.q y los de N2, 2.q.
inline Nfa nfa_union(const Nfa& first, const Nfa& second) {
    require_same_alphabet(first, second);
    Nfa n1 = with_prefix(first, "1.");
    Nfa n2 = with_prefix(second, "2.");
    Nfa n;
    n.alphabet = n1.alphabet;
    n.start = "s";
    n.states = {n.start};
    n.states.insert(n.states.end(), n1.states.begin(), n1.states.end());
    n.states.insert(n.states.end(), n2.states.begin(), n2.states.end());
    n.delta = n1.delta;
    n.delta.insert(n2.delta.begin(), n2.delta.end());
    n.delta[{n.start, EPS}] = {n1.start, n2.start};
    n.accept = n1.accept;
    n.accept.insert(n2.accept.begin(), n2.accept.end());
    check_nfa(n);
    return n;
}

// Concatenación: se empieza en N1, y de cada estado de aceptación de N1 sale una transición ε
// al inicial de N2. F = F2.
inline Nfa nfa_concat(const Nfa& first, const Nfa& second) {
    require_same_alphabet(first, second);
    Nfa n1 = with_prefix(first, "1.");
    Nfa n2 = with_prefix(second, "2.");
    Nfa n;
    n.alphabet = n1.alphabet;
    n.start = n1.start;
    n.states = n1.states;
    n.states.insert(n.states.end(), n2.states.begin(), n2.states.end());
    n.delta = n1.delta;
    n.delta.insert(n2.delta.begin(), n2.delta.end());
    for (const std::string& f : n1.accept) {
        n.delta[{f, EPS}].insert(n2.start);
    }
    n.accept = n2.accept;
    check_nfa(n);
    return n;
}

// Estrella: un estado inicial nuevo s, que es de aceptación, con una transición ε al inicial
// anterior. De cada estado de aceptación sale una transición ε al inicial anterior.
// F = F1 ∪ {s}.
inline Nfa nfa_star(const Nfa& n1) {
    Nfa n = n1;
    n.start = fresh_name(n1.states, "s");
    n.states.insert(n.states.begin(), n.start);
    n.delta[{n.start, EPS}] = {n1.start};
    for (const std::string& f : n1.accept) {
        n.delta[{f, EPS}].insert(n1.start);
    }
    n.accept.insert(n.start);
    check_nfa(n);
    return n;
}

// Reverso: todas las flechas al revés, un estado inicial nuevo s con transiciones ε a los que
// eran de aceptación, y un solo estado de aceptación: el que era inicial.
inline Nfa nfa_reverse(const Nfa& n1) {
    Nfa n;
    n.alphabet = n1.alphabet;
    n.start = fresh_name(n1.states, "s");
    n.states = {n.start};
    n.states.insert(n.states.end(), n1.states.begin(), n1.states.end());
    for (const auto& [key, targets] : n1.delta) {
        for (const std::string& target : targets) {
            n.delta[{target, key.second}].insert(key.first);
        }
    }
    if (!n1.accept.empty()) {
        n.delta[{n.start, EPS}] = n1.accept;
    }
    n.accept = {n1.start};
    check_nfa(n);
    return n;
}

#endif
paths_nfa.cppDescargar paths_nfa.cpp
// Todos los caminos de un NFA con una cadena, uno por línea: paths_nfa ARCHIVO.nfa CADENA
// Es el árbol de ejecuciones, con cada rama escrita desde la raíz. Una rama termina cuando
// se acaba la cadena o cuando el estado no tiene transición con el símbolo que toca (muere).
// La cadena vacía se pasa como '' en la terminal.
#include <cstddef>
#include <iostream>
#include <set>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

#include "nfa.h"
#include "strings.h"

struct Count {
    int finished = 0;   // caminos que leyeron toda la cadena
    int accepting = 0;  // de esos, los que terminan en F
    int dead = 0;       // caminos que murieron antes
};

// Extiende el camino text, que está en el estado q y ya leyó pos símbolos de w.
// on_path tiene los pares (estado, posición) del camino: evita dar vueltas por un ciclo de ε.
static void explore(const Nfa& n, const std::string& w, const std::string& q, std::size_t pos,
                    const std::string& text, std::set<std::pair<std::string, std::size_t>>& on_path, Count& count) {
    on_path.insert({q, pos});
    bool moved = false;
    if (pos == w.size()) {
        bool ok = n.accept.count(q) > 0;
        std::cout << "  " << text << "    termina en " << q << (ok ? ", que está en F" : ", que no está en F") << '\n';
        count.finished++;
        count.accepting += ok;
        moved = true;
    } else {
        for (const std::string& r : delta_of(n, q, w[pos])) {
            explore(n, w, r, pos + 1, text + " -" + w[pos] + "-> " + r, on_path, count);
            moved = true;
        }
    }
    for (const std::string& r : delta_of(n, q, EPS)) {
        if (on_path.count({r, pos}) == 0) {
            explore(n, w, r, pos, text + " -ε-> " + r, on_path, count);
            moved = true;
        }
    }
    if (!moved) {
        std::cout << "  " << text << "    muere: " << q << " no tiene transición con " << w[pos] << '\n';
        count.dead++;
    }
    on_path.erase({q, pos});
}

int main(int argc, char** argv) {
    if (argc != 3) {
        std::cerr << "uso: paths_nfa ARCHIVO.nfa CADENA\n";
        return 2;
    }
    try {
        Nfa n = load_nfa(argv[1]);
        std::string w = argv[2];
        std::cout << "w = " << show(w) << '\n';
        std::set<std::pair<std::string, std::size_t>> on_path;
        Count count;
        explore(n, w, n.start, 0, n.start, on_path, count);
        std::cout << "caminos que leen toda la cadena: " << count.finished << "    que mueren antes: " << count.dead
                  << "    que terminan en F: " << count.accepting << "\n"
                  << (count.accepting > 0 ? "algún camino termina en F: acepta" : "ningún camino termina en F: rechaza")
                  << '\n';
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
print.hDescargar print.h
// Ayudas para imprimir tablas alineadas aunque el texto tenga letras como δ o ε, que ocupan
// más de un byte y una sola columna.
#ifndef PRINT_H
#define PRINT_H

#include <cstddef>
#include <string>

// Cuántas columnas ocupa un texto en UTF-8: los bytes de continuación no cuentan.
inline std::size_t columns(const std::string& text) {
    std::size_t count = 0;
    for (unsigned char c : text) {
        count += ((c & 0xC0) != 0x80);
    }
    return count;
}

inline std::string padded(const std::string& text, std::size_t width) {
    std::size_t used = columns(text);
    return text + std::string(width > used ? width - used : 0, ' ');
}

#endif
run_dfa.cppDescargar run_dfa.cpp
// Sigue un DFA con una o más cadenas: run_dfa ARCHIVO.dfa CADENA...
// Con - en lugar del archivo, lee la descripción de la entrada estándar.
// La cadena vacía se pasa como '' en la terminal.
// Es el programa de la semana 1: sirve para seguir el DFA que escribe nfa_to_dfa.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

#include "dfa.h"

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cerr << "uso: run_dfa ARCHIVO.dfa CADENA...\n";
        return 2;
    }
    try {
        std::string path = argv[1];
        Dfa m = (path == "-") ? read_dfa(std::cin) : load_dfa(path);
        for (int i = 2; i < argc; i++) {
            std::string w = argv[i];
            std::vector<std::string> sequence = run(m, w);
            std::cout << "w = " << (w.empty() ? "ε" : w) << "\n  " << sequence[0];
            for (std::size_t k = 0; k < w.size(); k++) {
                std::cout << " -" << w[k] << "-> " << sequence[k + 1];
            }
            const std::string& last = sequence.back();
            bool ok = m.accept.count(last) > 0;
            std::cout << "\n  termina en " << last << (ok ? ", que está en F: acepta" : ", que no está en F: rechaza")
                      << '\n';
        }
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
run_nfa.cppDescargar run_nfa.cpp
// Sigue un NFA con una o más cadenas: run_nfa ARCHIVO.nfa CADENA...
// Imprime el conjunto de estados activos antes de leer nada y después de cada símbolo.
// Con - en lugar del archivo, lee la descripción de la entrada estándar.
// La cadena vacía se pasa como '' en la terminal.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

#include "nfa.h"
#include "strings.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> sequence = run(n, w);
            std::cout << "w = " << show(w) << "\n  " << set_name(n, sequence[0]);
            for (std::size_t k = 0; k < w.size(); k++) {
                std::cout << " -" << w[k] << "-> " << set_name(n, sequence[k + 1]);
            }
            const StateSet& last = sequence.back();
            std::cout << "\n  termina con " << set_name(n, last) << " activos";
            // El primero de los estados finales que está en F, en el orden de states.
            std::string witness;
            for (const std::string& state : n.states) {
                if (witness.empty() && last.count(state) > 0 && n.accept.count(state) > 0) {
                    witness = state;
                }
            }
            if (witness.empty()) {
                std::cout << ", y ninguno está en F: rechaza\n";
            } else {
                std::cout << ", y " << witness << " está en F: acepta\n";
            }
        }
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
show_nfa.cppDescargar show_nfa.cpp
// Muestra un NFA como quíntupla y como tabla de transiciones: show_nfa ARCHIVO.nfa
// Cada casilla de la tabla es un conjunto de estados, y hay una columna más para ε.
// En la tabla, -> marca el estado inicial y * los estados de aceptación.
// Si hay transiciones ε, al final imprime la clausura ε de cada estado.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

#include "nfa.h"
#include "print.h"

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: show_nfa ARCHIVO.nfa\n";
        return 2;
    }
    try {
        Nfa n = load_nfa(argv[1]);
        std::cout << "Q  = {";
        for (std::size_t i = 0; i < n.states.size(); i++) {
            std::cout << (i > 0 ? ", " : "") << n.states[i];
        }
        std::cout << "}\nΣ  = {";
        for (std::size_t i = 0; i < n.alphabet.size(); i++) {
            std::cout << (i > 0 ? ", " : "") << n.alphabet[i];
        }
        std::cout << "}\nq0 = " << n.start << "\nF  = {";
        bool first = true;
        for (const std::string& state : n.states) {
            if (n.accept.count(state) > 0) {
                std::cout << (first ? "" : ", ") << state;
                first = false;
            }
        }
        std::cout << "}\n\n";

        // Las columnas: los símbolos y, al final, ε.
        std::vector<char> symbols = n.alphabet;
        symbols.push_back(EPS);
        std::vector<std::string> heads;
        for (char a : symbols) {
            heads.push_back(a == EPS ? "ε" : std::string(1, a));
        }
        std::size_t name_width = 1;
        for (const std::string& state : n.states) {
            name_width = std::max(name_width, state.size());
        }
        std::vector<std::size_t> width(symbols.size(), 1);
        bool has_eps = false;
        for (const std::string& state : n.states) {
            for (std::size_t j = 0; j < symbols.size(); j++) {
                width[j] = std::max(width[j], set_name(n, delta_of(n, state, symbols[j])).size());
            }
            has_eps = has_eps || !delta_of(n, state, EPS).empty();
        }
        // La última columna va sin relleno, para no dejar espacios al final de la línea.
        std::cout << "     " << padded("δ", name_width);
        for (std::size_t j = 0; j < symbols.size(); j++) {
            std::cout << "  " << (j + 1 < symbols.size() ? padded(heads[j], width[j]) : heads[j]);
        }
        std::cout << '\n';
        for (const std::string& state : n.states) {
            std::cout << (state == n.start ? "-> " : "   ") << (n.accept.count(state) > 0 ? "* " : "  ")
                      << padded(state, name_width);
            for (std::size_t j = 0; j < symbols.size(); j++) {
                std::string cell = set_name(n, delta_of(n, state, symbols[j]));
                std::cout << "  " << (j + 1 < symbols.size() ? padded(cell, width[j]) : cell);
            }
            std::cout << '\n';
        }
        if (has_eps) {
            std::cout << "\nclausura ε de cada estado:\n";
            for (const std::string& state : n.states) {
                std::cout << "  E({" << state << "}) = " << set_name(n, eps_closure(n, {state})) << '\n';
            }
        } else {
            std::cout << "\nno tiene transiciones ε: E(S) = S para todo conjunto S\n";
        }
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
strings.hDescargar strings.h
// Cadenas, para las pruebas y los ejemplos: todas las cadenas hasta cierta longitud, y cómo
// se muestra la cadena vacía. all_strings es la de languages.h de la semana 1.
#ifndef STRINGS_H
#define STRINGS_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.
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
subset.cppDescargar subset.cpp
// La tabla de la construcción de subconjuntos: subset ARCHIVO.nfa
// Una fila por cada subconjunto alcanzable, en el orden en que la cola los encuentra.
// -> marca el estado inicial del DFA y * los de aceptación.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

#include "nfa.h"
#include "print.h"

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: subset ARCHIVO.nfa\n";
        return 2;
    }
    try {
        Nfa n = load_nfa(argv[1]);
        Dfa d = subset_construction(n);
        std::size_t width = 1;
        for (const std::string& state : d.states) {
            width = std::max(width, state.size());
        }
        std::cout << "E({" << n.start << "}) = " << d.start << "\n\n";
        std::cout << "     " << padded("S", width);
        for (std::size_t j = 0; j < d.alphabet.size(); j++) {
            std::string head(1, d.alphabet[j]);
            std::cout << "  " << (j + 1 < d.alphabet.size() ? padded(head, width) : head);
        }
        std::cout << '\n';
        for (const std::string& state : d.states) {
            std::cout << (state == d.start ? "-> " : "   ") << (d.accept.count(state) > 0 ? "* " : "  ")
                      << padded(state, width);
            for (std::size_t j = 0; j < d.alphabet.size(); j++) {
                const std::string& target = step(d, state, d.alphabet[j]);
                std::cout << "  " << (j + 1 < d.alphabet.size() ? padded(target, width) : target);
            }
            std::cout << '\n';
        }
        std::cout << "\nel NFA tiene " << n.states.size() << " estados: 2^" << n.states.size() << " = "
                  << (1UL << n.states.size()) << " subconjuntos, " << d.states.size() << " alcanzables\n";
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
swap_accept.cppDescargar swap_accept.cpp
// Intercambiar los estados de aceptación de un NFA no da el complemento:
//   swap_accept ARCHIVO.nfa CADENA...
// Por cada cadena dice qué responde el NFA, qué responde el NFA con F cambiado por Q − F, y
// qué responde el complemento bien hecho: construcción de subconjuntos y después el intercambio.
#include <iostream>
#include <stdexcept>
#include <string>

#include "errors/wrong_constructions.h"
#include "nfa.h"
#include "strings.h"

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cerr << "uso: swap_accept ARCHIVO.nfa CADENA...\n";
        return 2;
    }
    try {
        Nfa n = load_nfa(argv[1]);
        Nfa swapped = swap_accept(n);
        Dfa right = complement(subset_construction(n));
        std::cout << "F = " << set_name(n, n.accept) << "    Q − F = " << set_name(n, swapped.accept) << '\n';
        for (int i = 2; i < argc; i++) {
            std::string w = argv[i];
            std::cout << "w = " << show(w) << '\n';
            std::cout << "  activos al final: " << set_name(n, delta_star(n, {n.start}, w)) << '\n';
            std::cout << "  el NFA:                        " << (accepts(n, w) ? "acepta" : "rechaza") << '\n';
            std::cout << "  el NFA con Q − F:              " << (accepts(swapped, w) ? "acepta" : "rechaza") << '\n';
            std::cout << "  el DFA de subconjuntos, Q − F: " << (accepts(right, w) ? "acepta" : "rechaza") << '\n';
        }
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
wrong_star.cppDescargar wrong_star.cpp
// La estrella sin estado inicial nuevo acepta cadenas de más: wrong_star ARCHIVO.nfa [LONGITUD]
// Compara la construcción correcta con la incorrecta en todas las cadenas hasta la longitud
// dada (por defecto 4) e imprime las cadenas en las que no coinciden.
#include <cstddef>
#include <cstdlib>
#include <iostream>
#include <stdexcept>
#include <string>

#include "errors/wrong_constructions.h"
#include "nfa.h"
#include "strings.h"

int main(int argc, char** argv) {
    if (argc != 2 && argc != 3) {
        std::cerr << "uso: wrong_star ARCHIVO.nfa [LONGITUD]\n";
        return 2;
    }
    try {
        Nfa n = load_nfa(argv[1]);
        std::size_t max_len = argc == 3 ? static_cast<std::size_t>(std::atoi(argv[2])) : 4;
        Nfa good = nfa_star(n);
        Nfa bad = star_without_new_start(n);
        std::cout << "cadena   con estado inicial nuevo   sin estado inicial nuevo\n";
        int differences = 0;
        for (const std::string& w : all_strings(n.alphabet, max_len)) {
            bool in_good = accepts(good, w);
            bool in_bad = accepts(bad, w);
            if (in_good != in_bad) {
                std::cout << w << std::string(w.size() < 9 ? 9 - w.size() : 1, ' ')
                          << (in_good ? "acepta                     " : "rechaza                    ")
                          << (in_bad ? "acepta" : "rechaza") << '\n';
                differences++;
            }
        }
        std::cout << differences << " cadenas de longitud a lo sumo " << max_len << " en las que no coinciden\n";
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
machines/abc_blocks.nfaDescargar machines/abc_blocks.nfa
# Algunas a, después algunas b, después algunas c: cada bloque puede ser vacío.
# Las transiciones ε pasan al bloque siguiente sin leer nada.
states: qa qb qc
alphabet: a b c
start: qa
accept: qc
delta:
qa a qa
qa eps qb
qb b qb
qb eps qc
qc c qc
machines/contains_101_or_11.nfaDescargar machines/contains_101_or_11.nfa
# Cadenas binarias que contienen 101 o 11.
# q0: espera. q1: adivinó que aquí empieza el patrón y leyó su primer 1.
# q2: leyó el 0 del medio, o se lo saltó con la transición ε. q3: ya leyó el patrón completo.
states: q0 q1 q2 q3
alphabet: 0 1
start: q0
accept: q3
delta:
q0 0 q0
q0 1 q0 q1
q1 0 q2
q1 eps q2
q2 1 q3
q3 0 q3
q3 1 q3
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_01.nfaDescargar machines/ends_01.nfa
# Cadenas binarias que terminan en 01, con un NFA que adivina dónde empieza el 01 final.
states: q0 q1 q2
alphabet: 0 1
start: q0
accept: q2
delta:
q0 0 q0 q1
q0 1 q0
q1 1 q2
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/third_from_end.nfaDescargar machines/third_from_end.nfa
# El tercer símbolo desde el final es 1.
# q0: espera. q1: adivinó que el 1 que acaba de leer es el tercero desde el final.
# q2: leyó un símbolo más. q3: leyó dos más.
states: q0 q1 q2 q3
alphabet: 0 1
start: q0
accept: q3
delta:
q0 0 q0
q0 1 q0 q1
q1 0 q2
q1 1 q2
q2 0 q3
q2 1 q3
machines/zeros_then_one.nfaDescargar machines/zeros_then_one.nfa
# Algunos ceros y después un solo 1: 1, 01, 001, ...
# El estado inicial tiene una flecha que vuelve a él: es el ejemplo de la estrella.
states: q0 q1
alphabet: 0 1
start: q0
accept: q1
delta:
q0 0 q0
q0 1 q1

Errores

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

errors/eps_as_target.nfaDescargar errors/eps_as_target.nfa
# No es un NFA: a la transición ε le falta el destino. (eps va en el lugar del símbolo.)
states: q0 q1
alphabet: 0 1
start: q0
accept: q1
delta:
q0 1 q1
q0 eps
errors/unknown_state.nfaDescargar errors/unknown_state.nfa
# No es un NFA: una transición lleva a un estado que no está en states.
states: q0 q1
alphabet: 0 1
start: q0
accept: q1
delta:
q0 0 q0
q0 1 q0 q2
errors/wrong_constructions.hDescargar errors/wrong_constructions.h
// Dos construcciones INCORRECTAS, para los ejemplos de los apuntes. Parecen razonables y
// fallan con cadenas concretas: wrong_star.cpp y swap_accept.cpp muestran con cuáles, y
// test_closure.cpp lo comprueba.
#ifndef WRONG_CONSTRUCTIONS_H
#define WRONG_CONSTRUCTIONS_H

#include <string>

#include "../nfa.h"

// "Estrella" sin estado inicial nuevo: marca el inicial como de aceptación, para aceptar ε, y
// agrega las transiciones ε de los estados de aceptación al inicial.
// Falla cuando alguna flecha vuelve al estado inicial: una cadena que regresa a él queda
// aceptada aunque no sea una concatenación de cadenas del lenguaje.
inline Nfa star_without_new_start(const Nfa& n1) {
    Nfa n = n1;
    for (const std::string& f : n1.accept) {
        n.delta[{f, EPS}].insert(n1.start);
    }
    n.accept.insert(n1.start);
    return n;
}

// "Complemento" de un NFA: la misma máquina con F cambiado por Q − F.
// En un DFA es correcto. En un NFA no: una cadena con un camino que acepta y otro que no
// queda aceptada antes y después del intercambio.
inline Nfa swap_accept(const Nfa& n1) {
    Nfa n = n1;
    n.accept.clear();
    for (const std::string& state : n1.states) {
        if (n1.accept.count(state) == 0) {
            n.accept.insert(state);
        }
    }
    return n;
}

#endif

Pruebas

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

test_closure.cppDescargar test_closure.cpp
// Pruebas de las construcciones de cierre (sesión B): cada una se compara con el predicado que
// define la operación, calculado sin autómatas. Y las dos construcciones incorrectas de los
// apuntes fallan con las cadenas que los apuntes dicen.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <functional>
#include <random>
#include <string>
#include <vector>

#include "errors/wrong_constructions.h"
#include "nfa.h"
#include "strings.h"
#include "test_helpers.h"

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

// w ∈ AB: alguna partición w = uv tiene u ∈ A y v ∈ B.
static bool in_concat(const Predicate& in_a, const Predicate& in_b, const std::string& w) {
    for (std::size_t cut = 0; cut <= w.size(); cut++) {
        if (in_a(w.substr(0, cut)) && in_b(w.substr(cut))) {
            return true;
        }
    }
    return false;
}

// w ∈ A*: w se parte en cero o más trozos de A. splits[i] dice si el prefijo de longitud i está en A*.
static bool in_star(const Predicate& in_a, const std::string& w) {
    std::vector<bool> splits(w.size() + 1, false);
    splits[0] = true;
    for (std::size_t end = 1; end <= w.size(); end++) {
        for (std::size_t from = 0; from < end && !splits[end]; from++) {
            splits[end] = splits[from] && in_a(w.substr(from, end - from));
        }
    }
    return splits[w.size()];
}

static void test_examples_of_notes() {
    Nfa even = load_nfa("machines/even_ones.dfa");
    Nfa ends = load_nfa("machines/ends_01.dfa");
    Predicate in_even = [](const std::string& w) { return count_ones(w) % 2 == 0; };
    Predicate in_ends = [](const std::string& w) { return ends_with(w, "01"); };
    std::vector<std::string> words = all_strings({'0', '1'}, 9);

    // Unión: 1 + 2 + 3 estados, y el mismo lenguaje que el producto de la semana 1.
    Nfa either = nfa_union(even, ends);
    assert(either.states == (std::vector<std::string>{"s", "1.par", "1.impar", "2.q0", "2.q1", "2.q2"}));
    assert(delta_of(either, "s", EPS) == (StateSet{"1.par", "2.q0"}));
    assert(either.accept == (StateSet{"1.par", "2.q2"}));
    Dfa product_union = product(load_dfa("machines/even_ones.dfa"), load_dfa("machines/ends_01.dfa"), Combine::Union);
    for (const std::string& w : words) {
        assert(accepts(either, w) == (in_even(w) || in_ends(w)));
        assert(accepts(either, w) == accepts(product_union, w));
    }
    assert(run(either, "").front() == (StateSet{"s", "1.par", "2.q0"}));

    // Concatenación: termina en 01, y después una cantidad par de unos.
    Nfa both = nfa_concat(ends, even);
    assert(both.states.size() == 5 && both.start == "1.q0");
    assert(both.accept == (StateSet{"2.par"}));
    assert(delta_of(both, "1.q2", EPS) == (StateSet{"2.par"}));
    for (const std::string& w : words) {
        assert(accepts(both, w) == in_concat(in_ends, in_even, w));
    }
    // 0111 = 01 · 11 está; 011 no: después de cualquier 01 queda una cantidad impar de unos.
    assert(accepts(both, "0111") && accepts(both, "01") && !accepts(both, "011") && !accepts(both, ""));

    // Estrella de 0*1: ε y las cadenas que terminan en 1.
    Nfa one = load_nfa("machines/zeros_then_one.nfa");
    Predicate in_one = [](const std::string& w) { return !w.empty() && w.back() == '1' && count_ones(w) == 1; };
    Nfa star = nfa_star(one);
    assert(star.states == (std::vector<std::string>{"s", "q0", "q1"}));
    assert(star.start == "s" && star.accept == (StateSet{"s", "q1"}));
    assert(delta_of(star, "s", EPS) == (StateSet{"q0"}) && delta_of(star, "q1", EPS) == (StateSet{"q0"}));
    for (const std::string& w : words) {
        assert(accepts(star, w) == in_star(in_one, w));
        assert(accepts(star, w) == (w.empty() || w.back() == '1'));
    }

    // La estrella sin estado inicial nuevo acepta 0, que no está en (0*1)*: es exactamente
    // las cadenas no vacías que terminan en 0 lo que acepta de más.
    Nfa wrong = star_without_new_start(one);
    assert(accepts(wrong, "0") && !accepts(star, "0") && !in_star(in_one, "0"));
    assert(accepts(wrong, "") && accepts(wrong, "01"));
    for (const std::string& w : words) {
        assert(accepts(wrong, w));  // acepta todas las cadenas
    }

    // Reverso: de "termina en 01" a "empieza con 10", y de "tercero desde el final" a "tercero".
    Nfa backwards = nfa_reverse(ends);
    assert(backwards.states.size() == 4 && backwards.accept == (StateSet{"q0"}));
    assert(delta_of(backwards, "s", EPS) == (StateSet{"q2"}));
    Nfa third = load_nfa("machines/third_from_end.nfa");
    Nfa third_reversed = nfa_reverse(third);
    for (const std::string& w : words) {
        assert(accepts(backwards, w) == (w.size() >= 2 && w[0] == '1' && w[1] == '0'));
        assert(accepts(third_reversed, w) == (w.size() >= 3 && w[2] == '1'));
    }
    // El reverso de un DFA no es un DFA: de q1 salen tres flechas con 0 (eran q0→q1, q1→q1 y q2→q1).
    assert(delta_of(backwards, "q1", '0').size() == 3);
}

// Intercambiar F por Q − F en un NFA no da el complemento.
static void test_swap_accept() {
    Nfa third = load_nfa("machines/third_from_end.nfa");
    Nfa swapped = swap_accept(third);
    assert(swapped.accept == (StateSet{"q0", "q1", "q2"}));
    // 100 está en el lenguaje y el NFA intercambiado también la acepta.
    assert(accepts(third, "100") && accepts(swapped, "100"));
    // De hecho acepta todo, porque q0 siempre está activo.
    Dfa right = complement(subset_construction(third));
    for (const std::string& w : all_strings({'0', '1'}, 9)) {
        assert(accepts(swapped, w));
        assert(accepts(right, w) == !accepts(third, w));  // el camino correcto: primero el DFA
    }
    assert(!accepts(right, "100") && accepts(right, "000"));
}

// Las cuatro construcciones con NFA al azar, que tienen transiciones ε, ciclos y flechas que
// vuelven al estado inicial.
static int test_random() {
    std::mt19937 rng(40404);
    std::vector<std::string> words = all_strings({'0', '1'}, 5);
    int machines = 0;
    for (int round = 0; round < 100; round++) {
        Nfa a = random_nfa(rng, 1 + static_cast<int>(rng() % 4));
        Nfa b = random_nfa(rng, 1 + static_cast<int>(rng() % 4));
        Predicate in_a = [&a](const std::string& w) { return accepts_by_paths(a, w); };
        Predicate in_b = [&b](const std::string& w) { return accepts_by_paths(b, w); };
        Nfa either = nfa_union(a, b);
        Nfa both = nfa_concat(a, b);
        Nfa star = nfa_star(a);
        Nfa backwards = nfa_reverse(a);
        assert(either.states.size() == a.states.size() + b.states.size() + 1);
        assert(both.states.size() == a.states.size() + b.states.size());
        assert(star.states.size() == a.states.size() + 1 && backwards.states.size() == a.states.size() + 1);
        for (const std::string& w : words) {
            assert(accepts(either, w) == (in_a(w) || in_b(w)));
            assert(accepts(both, w) == in_concat(in_a, in_b, w));
            assert(accepts(star, w) == in_star(in_a, w));
            assert(accepts(backwards, w) == in_a(reversed(w)));
        }
        machines++;
    }
    return machines;
}

int main() {
    test_examples_of_notes();
    test_swap_accept();
    int machines = test_random();
    std::printf("test_closure: ok (unión, concatenación, estrella y reverso; %d pares de NFA al azar)\n", machines);
}
test_helpers.hDescargar test_helpers.h
// Ayudas compartidas por las pruebas: predicados sobre cadenas, la aceptación de un NFA
// calculada directamente con la definición (buscando un camino) y NFA al azar con semilla fija.
#ifndef TEST_HELPERS_H
#define TEST_HELPERS_H

#include <algorithm>
#include <cstddef>
#include <random>
#include <set>
#include <string>
#include <utility>
#include <vector>

#include "nfa.h"

inline bool ends_with(const std::string& w, const std::string& tail) {
    return w.size() >= tail.size() && w.compare(w.size() - tail.size(), tail.size(), tail) == 0;
}

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

inline int count_ones(const std::string& w) {
    return static_cast<int>(std::count(w.begin(), w.end(), '1'));
}

inline std::string reversed(const std::string& w) {
    return std::string(w.rbegin(), w.rend());
}

// ¿Hay un camino desde q, habiendo leído pos símbolos de w, que termine en F con toda la cadena leída?
// Es la definición de aceptación, sin conjuntos de estados activos. on_path evita los ciclos de ε.
inline bool path_exists(const Nfa& n, const std::string& w, const std::string& q, std::size_t pos,
                        std::set<std::pair<std::string, std::size_t>>& on_path) {
    if (pos == w.size() && n.accept.count(q) > 0) {
        return true;
    }
    if (!on_path.insert({q, pos}).second) {
        return false;
    }
    bool found = false;
    if (pos < w.size()) {
        for (const std::string& r : delta_of(n, q, w[pos])) {
            found = found || path_exists(n, w, r, pos + 1, on_path);
        }
    }
    for (const std::string& r : delta_of(n, q, EPS)) {
        found = found || path_exists(n, w, r, pos, on_path);
    }
    on_path.erase({q, pos});
    return found;
}

inline bool accepts_by_paths(const Nfa& n, const std::string& w) {
    std::set<std::pair<std::string, std::size_t>> on_path;
    return path_exists(n, w, n.start, 0, on_path);
}

// Un NFA al azar con size estados sobre {0, 1}, con transiciones ε (también ciclos de ε),
// pares sin transición y estados inalcanzables. Solo usa rng() y restos, para que salga igual
// en cualquier plataforma.
inline Nfa random_nfa(std::mt19937& rng, int size) {
    Nfa n;
    n.alphabet = {'0', '1'};
    for (int i = 0; i < size; i++) {
        n.states.push_back("p" + std::to_string(i));
    }
    n.start = n.states[rng() % size];
    for (const std::string& state : n.states) {
        if (rng() % 3 == 0) {
            n.accept.insert(state);
        }
        for (char a : {'0', '1', EPS}) {
            // Pocas transiciones ε, para que no todo quede conectado con todo.
            unsigned arrows = (a == EPS) ? (rng() % 4 == 0 ? 1 : 0) : rng() % 3;
            for (unsigned k = 0; k < arrows; k++) {
                n.delta[{state, a}].insert(n.states[rng() % size]);
            }
        }
    }
    return n;
}

#endif
test_nfa.cppDescargar test_nfa.cpp
// Pruebas de lo que los apuntes afirman sobre los NFA del capítulo (sesión A).
// Cada autómata de machines/ se compara con una función de C++ que decide el mismo lenguaje
// mirando la cadena completa, y la simulación con conjuntos de estados activos se compara
// con la definición: existe un camino que termina en un estado de aceptación.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <functional>
#include <random>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

#include "kth.h"
#include "nfa.h"
#include "strings.h"
#include "test_helpers.h"

// Compara N con el predicado y con la definición por caminos. Devuelve cuántas cadenas revisó.
static std::size_t check_language(const std::string& path, std::size_t max_len,
                                  const std::function<bool(const std::string&)>& in_language) {
    Nfa n = load_nfa(path);
    std::vector<std::string> words = all_strings(n.alphabet, max_len);
    for (const std::string& w : words) {
        assert(accepts(n, w) == in_language(w));
        assert(accepts_by_paths(n, w) == in_language(w));
    }
    return words.size();
}

static bool third_from_end_is_one(const std::string& w) {
    return w.size() >= 3 && w[w.size() - 3] == '1';
}

// a*b*c*: la cadena está ordenada.
static bool in_blocks(const std::string& w) {
    for (std::size_t i = 1; i < w.size(); i++) {
        if (w[i - 1] > w[i]) {
            return false;
        }
    }
    return true;
}

static std::size_t test_languages_of_machines() {
    std::size_t total = 0;
    total += check_language("machines/third_from_end.nfa", 10, third_from_end_is_one);
    total += check_language("machines/contains_101_or_11.nfa", 10,
                            [](const std::string& w) { return contains(w, "101") || contains(w, "11"); });
    total += check_language("machines/abc_blocks.nfa", 7, in_blocks);
    total += check_language("machines/ends_01.nfa", 10, [](const std::string& w) { return ends_with(w, "01"); });
    total += check_language("machines/zeros_then_one.nfa", 10, [](const std::string& w) {
        return !w.empty() && w.back() == '1' && count_ones(w) == 1;
    });
    // Todo archivo .dfa es un .nfa válido, y como NFA acepta lo mismo.
    total += check_language("machines/even_ones.dfa", 10, [](const std::string& w) { return count_ones(w) % 2 == 0; });
    total += check_language("machines/ends_01.dfa", 10, [](const std::string& w) { return ends_with(w, "01"); });
    return total;
}

static void test_runs_of_notes() {
    Nfa third = load_nfa("machines/third_from_end.nfa");
    // El conjunto de estados activos después de cada símbolo, como lo imprime run_nfa.
    assert(run(third, "0110") == (std::vector<StateSet>{{"q0"}, {"q0"}, {"q0", "q1"}, {"q0", "q1", "q2"},
                                                        {"q0", "q2", "q3"}}));
    assert(accepts(third, "0110") && accepts(third, "100") && !accepts(third, "") && !accepts(third, "011"));
    assert(run(third, "100").back() == (StateSet{"q0", "q3"}));
    // Sin transiciones ε, la clausura no agrega nada.
    assert(eps_closure(third, {"q0", "q2"}) == (StateSet{"q0", "q2"}));
    // De q3 no sale ninguna flecha: δ(q3, 0) = ∅.
    assert(delta_of(third, "q3", '0').empty() && delta_of(third, "q3", EPS).empty());
    assert(delta_of(third, "q0", '1') == (StateSet{"q0", "q1"}));

    Nfa either = load_nfa("machines/contains_101_or_11.nfa");
    assert(eps_closure(either, {"q1"}) == (StateSet{"q1", "q2"}));
    assert(eps_closure(either, {"q0"}) == (StateSet{"q0"}));
    assert(run(either, "01011") ==
           (std::vector<StateSet>{{"q0"}, {"q0"}, {"q0", "q1", "q2"}, {"q0", "q2"}, {"q0", "q1", "q2", "q3"},
                                  {"q0", "q1", "q2", "q3"}}));
    assert(run(either, "0100").back() == (StateSet{"q0"}));
    assert(accepts(either, "01011") && !accepts(either, "0100") && accepts(either, "11") && !accepts(either, "10"));

    Nfa blocks = load_nfa("machines/abc_blocks.nfa");
    // La clausura sigue varias transiciones ε seguidas, y el estado inicial ya llega activo a qc.
    assert(eps_closure(blocks, {"qa"}) == (StateSet{"qa", "qb", "qc"}));
    assert(eps_closure(blocks, {"qb"}) == (StateSet{"qb", "qc"}));
    assert(eps_closure(blocks, {}).empty());
    assert(accepts(blocks, "") && accepts(blocks, "aacc") && accepts(blocks, "b") && !accepts(blocks, "ba"));
    assert(run(blocks, "abca") ==
           (std::vector<StateSet>{{"qa", "qb", "qc"}, {"qa", "qb", "qc"}, {"qb", "qc"}, {"qc"}, {}}));
}

// Propiedades de la clausura ε: contiene a S, aplicarla dos veces no cambia nada, y crece con S.
static void test_closure_properties() {
    std::mt19937 rng(20202);
    for (int round = 0; round < 300; round++) {
        Nfa n = random_nfa(rng, 1 + static_cast<int>(rng() % 6));
        StateSet small;
        StateSet big;
        for (const std::string& state : n.states) {
            unsigned coin = rng() % 3;
            if (coin == 0) {
                small.insert(state);
            }
            if (coin <= 1) {
                big.insert(state);
            }
        }
        StateSet closed = eps_closure(n, small);
        assert(std::includes(closed.begin(), closed.end(), small.begin(), small.end()));
        assert(eps_closure(n, closed) == closed);
        StateSet closed_big = eps_closure(n, big);
        assert(std::includes(closed_big.begin(), closed_big.end(), closed.begin(), closed.end()));
    }
}

// El lema de los estados activos: la simulación con conjuntos acepta exactamente cuando la
// definición dice que hay un camino. Con NFA al azar, que tienen ciclos de ε y caminos que mueren.
static int test_active_sets_against_paths() {
    std::mt19937 rng(10102);
    int machines = 0;
    for (int round = 0; round < 200; round++) {
        Nfa n = random_nfa(rng, 1 + static_cast<int>(rng() % 6));
        check_nfa(n);
        for (const std::string& w : all_strings(n.alphabet, 6)) {
            assert(accepts(n, w) == accepts_by_paths(n, w));
        }
        machines++;
    }
    return machines;
}

static void test_format() {
    // Leer, escribir y volver a leer da la misma máquina.
    for (const char* path : {"machines/third_from_end.nfa", "machines/contains_101_or_11.nfa",
                             "machines/abc_blocks.nfa", "machines/ends_01.dfa"}) {
        Nfa n = load_nfa(path);
        std::ostringstream text;
        write_nfa(text, n);
        std::istringstream again(text.str());
        Nfa copy = read_nfa(again);
        assert(copy.states == n.states && copy.alphabet == n.alphabet && copy.delta == n.delta);
        assert(copy.start == n.start && copy.accept == n.accept);
    }
    // Un par de estado y símbolo puede estar en varias líneas: los destinos se juntan.
    std::istringstream split("states: a b\nalphabet: 0\nstart: a\naccept: b\ndelta:\na 0 a\n# otra\na 0 b a\na eps b\n");
    Nfa joined = read_nfa(split);
    assert(delta_of(joined, "a", '0') == (StateSet{"a", "b"}) && delta_of(joined, "a", EPS) == (StateSet{"b"}));

    // kth_from_end(3) es la máquina del archivo.
    Nfa third = load_nfa("machines/third_from_end.nfa");
    Nfa built = kth_from_end(3);
    assert(built.states == third.states && built.delta == third.delta && built.accept == third.accept);

    // Un DFA visto como NFA: δ(q, a) tiene exactamente un estado y no hay transiciones ε.
    Nfa even = to_nfa(load_dfa("machines/even_ones.dfa"));
    for (const std::string& state : even.states) {
        assert(delta_of(even, state, '0').size() == 1 && delta_of(even, state, '1').size() == 1);
        assert(delta_of(even, state, EPS).empty());
    }

    // Un NFA no suele ser un archivo .dfa válido.
    bool failed = false;
    try {
        load_dfa("machines/third_from_end.nfa");
    } catch (const std::runtime_error&) {
        failed = true;
    }
    assert(failed);
    for (const char* path : {"errors/unknown_state.nfa", "errors/eps_as_target.nfa"}) {
        failed = false;
        try {
            load_nfa(path);
        } catch (const std::runtime_error&) {
            failed = true;
        }
        assert(failed);
    }
}

int main() {
    std::size_t words = test_languages_of_machines();
    test_runs_of_notes();
    test_closure_properties();
    int machines = test_active_sets_against_paths();
    test_format();
    std::printf("test_nfa: ok (7 autómatas, %zu cadenas en total; %d NFA al azar contra la definición)\n", words,
                machines);
}
test_subset.cppDescargar test_subset.cpp
// Pruebas de la construcción de subconjuntos (sesión B): el DFA construido acepta lo mismo
// que el NFA, sigue al conjunto de estados activos cadena por cadena, y tiene los estados que
// dicen los apuntes.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <random>
#include <set>
#include <string>
#include <vector>

#include "kth.h"
#include "nfa.h"
#include "strings.h"
#include "test_helpers.h"

// El lema de la construcción: δ_D*(E({q0}), w) es el conjunto de estados activos de N con w.
// Y lo que importa: D acepta w si y solo si N acepta w. Devuelve cuántas cadenas revisó.
static std::size_t check_equivalent(const Nfa& n, const Dfa& d, std::size_t max_len) {
    std::vector<std::string> words = all_strings(n.alphabet, max_len);
    for (const std::string& w : words) {
        assert(delta_star(d, d.start, w) == set_name(n, delta_star(n, {n.start}, w)));
        assert(accepts(d, w) == accepts(n, w));
    }
    return words.size();
}

static void test_machines_of_notes() {
    // Tercero desde el final: 4 estados en el NFA, 8 subconjuntos alcanzables de 16.
    Nfa third = load_nfa("machines/third_from_end.nfa");
    std::vector<StateSet> subsets;
    Dfa d3 = subset_construction(third, &subsets);
    assert(d3.states.size() == 8 && subsets.size() == 8);
    assert(reachable(d3).size() == 8);
    assert(d3.start == "{q0}");
    assert(d3.accept == (std::set<std::string>{"{q0,q3}", "{q0,q1,q3}", "{q0,q2,q3}", "{q0,q1,q2,q3}"}));
    // Algunas casillas de la tabla de los apuntes.
    assert(step(d3, "{q0}", '1') == "{q0,q1}");
    assert(step(d3, "{q0,q1}", '0') == "{q0,q2}");
    assert(step(d3, "{q0,q1,q2}", '0') == "{q0,q2,q3}");
    assert(step(d3, "{q0,q3}", '0') == "{q0}");
    assert(step(d3, "{q0,q1,q2,q3}", '1') == "{q0,q1,q2,q3}");
    // Todos los subconjuntos alcanzables contienen a q0, y cada uno es de aceptación si tiene a q3.
    for (std::size_t i = 0; i < subsets.size(); i++) {
        assert(subsets[i].count("q0") == 1);
        assert((d3.accept.count(d3.states[i]) > 0) == (subsets[i].count("q3") > 0));
    }
    // La ejecución del DFA es la de run_nfa, conjunto por conjunto.
    assert(run(d3, "0110") ==
           (std::vector<std::string>{"{q0}", "{q0}", "{q0,q1}", "{q0,q1,q2}", "{q0,q2,q3}"}));
    check_equivalent(third, d3, 10);
    // El estado recuerda los tres últimos símbolos: las 8 cadenas de longitud 3 van a 8 estados distintos.
    std::set<std::string> ends;
    for (const std::string& w : all_strings({'0', '1'}, 3)) {
        if (w.size() == 3) {
            ends.insert(delta_star(d3, d3.start, w));
        }
    }
    assert(ends.size() == 8);

    // Contiene 101 o 11: con ε. 6 alcanzables.
    Nfa either = load_nfa("machines/contains_101_or_11.nfa");
    Dfa d_either = subset_construction(either);
    assert(d_either.states.size() == 6 && d_either.start == "{q0}");
    assert(step(d_either, "{q0}", '1') == "{q0,q1,q2}");  // la clausura ε agrega q2
    assert(step(d_either, "{q0,q1,q2}", '0') == "{q0,q2}");
    check_equivalent(either, d_either, 10);

    // a*b*c*: el inicial del DFA es E({qa}), y aparece el conjunto vacío como estado trampa.
    Nfa blocks = load_nfa("machines/abc_blocks.nfa");
    Dfa d_blocks = subset_construction(blocks);
    assert(d_blocks.states == (std::vector<std::string>{"{qa,qb,qc}", "{qb,qc}", "{qc}", "{}"}));
    assert(d_blocks.start == "{qa,qb,qc}" && d_blocks.accept.count("{qa,qb,qc}") == 1);
    assert(d_blocks.accept.count("{}") == 0);
    for (char a : blocks.alphabet) {
        assert(step(d_blocks, "{}", a) == "{}");
    }
    check_equivalent(blocks, d_blocks, 7);

    // Termina en 01: el NFA de 3 estados da un DFA de 3 estados, con el mismo lenguaje que el de la semana 1.
    Nfa ends_nfa = load_nfa("machines/ends_01.nfa");
    Dfa d_ends = subset_construction(ends_nfa);
    Dfa week1 = load_dfa("machines/ends_01.dfa");
    assert(d_ends.states == (std::vector<std::string>{"{q0}", "{q0,q1}", "{q0,q2}"}));
    for (const std::string& w : all_strings({'0', '1'}, 10)) {
        assert(accepts(d_ends, w) == accepts(week1, w));
    }
    check_equivalent(ends_nfa, d_ends, 10);

    // Un DFA pasado por la construcción sale igual, con cada estado q convertido en {q}.
    Dfa again = subset_construction(to_nfa(week1));
    assert(again.states == (std::vector<std::string>{"{q0}", "{q1}", "{q2}"}));
}

// La tabla de los apuntes: para "el k-ésimo símbolo desde el final es 1", el NFA tiene k + 1
// estados y la construcción da exactamente 2^k.
static void test_kth_table() {
    for (int k = 1; k <= 12; k++) {
        Nfa n = kth_from_end(k);
        Dfa d = subset_construction(n);
        assert(n.states.size() == static_cast<std::size_t>(k) + 1);
        assert(d.states.size() == (std::size_t{1} << k));
        if (k <= 6) {
            for (const std::string& w : all_strings({'0', '1'}, 10)) {
                bool in_language = w.size() >= static_cast<std::size_t>(k) && w[w.size() - k] == '1';
                assert(accepts(d, w) == in_language);
            }
        }
    }
}

static int test_random() {
    std::mt19937 rng(30303);
    int machines = 0;
    for (int round = 0; round < 200; round++) {
        Nfa n = random_nfa(rng, 1 + static_cast<int>(rng() % 6));
        Dfa d = subset_construction(n);
        assert(d.states.size() <= (std::size_t{1} << n.states.size()));
        assert(reachable(d).size() == d.states.size());
        check_equivalent(n, d, 6);
        // Y contra la definición por caminos, que no usa conjuntos.
        for (const std::string& w : all_strings(n.alphabet, 5)) {
            assert(accepts(d, w) == accepts_by_paths(n, w));
        }
        machines++;
    }
    return machines;
}

int main() {
    test_machines_of_notes();
    test_kth_table();
    int machines = test_random();
    std::printf("test_subset: ok (4 autómatas de los apuntes, k de 1 a 12, %d NFA al azar)\n", machines);
}

Laboratorio

Archivos de partida del laboratorio de la semana.

lab/nfa_to_dfa/MakefileDescargar lab/nfa_to_dfa/Makefile
TIEMPO = 2
VERIFICADOR = verificador.cpp
include ../../../lab.mk
lab/nfa_to_dfa/README.mdDescargar lab/nfa_to_dfa/README.md
# De NFA a DFA

En clase se demostró que todo autómata finito no determinista (NFA) tiene un autómata finito determinista (DFA)
equivalente, con la construcción de subconjuntos. Aquí la programan: su programa recibe un NFA, que puede tener
transiciones $\varepsilon$, y escribe un DFA que reconoce el mismo lenguaje.

Si el NFA es $N = (Q, \Sigma, \delta, q_0, F)$ y $E(S)$ es la clausura $\varepsilon$ de un conjunto de estados
$S$, el DFA de la construcción tiene un estado por cada conjunto de estados de $N$:

- su estado inicial es $E(\{q_0\})$;
- desde el conjunto $S$, con el símbolo $a$, va al conjunto $E\bigl(\bigcup_{q \in S} \delta(q, a)\bigr)$;
- un conjunto es de aceptación si contiene algún estado de $F$.

## Entrada

La descripción de un NFA en el formato `.nfa` de [`code/formats.md`](../../../formats.md):

```text
# Cadenas binarias que contienen 101 o 11.
states: q0 q1 q2 q3
alphabet: 0 1
start: q0
accept: q3
delta:
q0 0 q0
q0 1 q0 q1
q1 0 q2
q1 eps q2
q2 1 q3
q3 0 q3
q3 1 q3
```

- Una línea que empieza con `#` es un comentario. Puede haber comentarios en cualquier línea, también entre
  las transiciones.
- Puede haber líneas vacías antes de `delta:`. Después de `delta:` no hay líneas vacías, y la descripción
  termina donde termina la entrada.
- `states:`, `alphabet:`, `start:`, `accept:` y `delta:` vienen siempre en ese orden. `accept:` puede no tener
  ningún estado.
- Después de `delta:`, cada línea es `estado símbolo destino…`, con uno o más destinos. Una transición
  $\varepsilon$ lleva `eps` en el lugar del símbolo.
- Un par de estado y símbolo que no aparece no tiene transiciones. Puede no haber ninguna línea después de
  `delta:`.
- El mismo par puede aparecer en varias líneas, y un destino puede estar repetido: los destinos de todas esas
  líneas se juntan en un solo conjunto.

## Salida

Un DFA equivalente al NFA de la entrada, en el formato `.dfa` del mismo documento: los cinco campos en su orden
y, después de `delta:`, exactamente una línea `estado símbolo destino` por cada par de estado y símbolo.

- El alfabeto del DFA tiene los mismos símbolos que el del NFA, en cualquier orden.
- Los nombres de los estados los eligen ustedes. Cada uno tiene entre 1 y 20 caracteres visibles, sin espacios,
  no empieza con `#` y no termina con `:`.
- El DFA tiene **a lo sumo 10 000 estados**.

Hay muchas respuestas correctas: los estados pueden llamarse de otro modo, ir en otro orden o ser más o menos
que los de `casos/NN.out`. El juez no compara textos. Usa un verificador, que se describe más abajo.

## Límites

- $1 \leq |Q| \leq 60$ y $1 \leq |\Sigma| \leq 10$.
- El nombre de un estado tiene entre 1 y 20 caracteres visibles, sin espacios. No empieza con `#` ni termina con
  `:`. Un nombre puede ser prefijo de otro, puede ser igual a un símbolo, y puede ser `eps`: en una línea de
  `delta:`, lo que decide qué es cada palabra es su posición.
- Un símbolo es un solo carácter visible, distinto de `#`.
- Se garantiza que la construcción de subconjuntos, **si solo genera los subconjuntos alcanzables** desde
  $E(\{q_0\})$, produce a lo sumo 5000 estados.
- La entrada siempre describe un NFA válido: no tienen que detectar errores en la descripción.

## Ejemplo

Para la entrada de arriba, una salida correcta es:

```text
states: s0 s1 s2 s3 s4 s5
alphabet: 0 1
start: s0
accept: s3 s4 s5
delta:
s0 0 s0
s0 1 s1
s1 0 s2
s1 1 s3
s2 0 s0
s2 1 s3
s3 0 s4
s3 1 s3
s4 0 s5
s4 1 s3
s5 0 s5
s5 1 s3
```

Es la de `casos/02.out`. Los seis estados son los subconjuntos alcanzables, numerados en el orden en que una
cola los encuentra:

| Nombre | Subconjunto |
|---|---|
| `s0` | $\{q_0\}$ |
| `s1` | $\{q_0, q_1, q_2\}$ |
| `s2` | $\{q_0, q_2\}$ |
| `s3` | $\{q_0, q_1, q_2, q_3\}$ |
| `s4` | $\{q_0, q_2, q_3\}$ |
| `s5` | $\{q_0, q_3\}$ |

Desde $\{q_0\}$ con $\mathtt{1}$ se llega a $q_0$ y a $q_1$, y la clausura $\varepsilon$ agrega $q_2$: por eso
`s0 1 s1`. El NFA tiene 4 estados y $2^4 = 16$ subconjuntos, pero desde el inicial solo se alcanzan estos 6.

## Tiempo

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

Un NFA de 60 estados tiene $2^{60}$ subconjuntos, más de $10^{18}$. Un programa que escribe un estado por cada
subconjunto no termina nunca con ese caso, y el juez da `TLE`. Con 18 estados sí termina, pero escribe $2^{18} =
262\,144$ estados y el verificador lo rechaza por pasarse de 10 000. La construcción tiene que partir de
$E(\{q_0\})$ y generar solo los subconjuntos que va encontrando.

## El verificador

`make test` compila `verificador.cpp` y el juez lo llama con cada caso. Pueden leerlo: son las ideas de la semana
1. Con la salida de su programa hace tres cosas.

1. **Comprueba que es un DFA bien formado**: los cinco campos, ningún estado repetido, el estado inicial y los
   de aceptación dentro de `states:`, y exactamente una transición por cada par de estado y símbolo.
2. **Comprueba los límites**: el mismo alfabeto que el NFA, a lo sumo 10 000 estados, nombres de hasta 20
   caracteres.
3. **Compara los lenguajes.** Recorre a la vez el NFA, con su conjunto de estados activos, y el DFA que
   ustedes entregaron, como en la construcción del producto: parte del par formado por $E(\{q_0\})$ y su estado
   inicial, y avanza en los dos con cada símbolo. Si llega a un par en el que uno acepta y el otro no, las
   máquinas no son equivalentes, y la cadena que llevó hasta ese par lo demuestra.

Cuando algo falla, el juez muestra el motivo al lado del veredicto. Con una solución que olvida la clausura
$\varepsilon$ del estado inicial, el caso 07 da:

```text
07           WA     0.01 s  no reconocen el mismo lenguaje: la cadena vacía la acepta el NFA y la rechaza el DFA
```

La cadena que muestra es de las más cortas en las que las dos máquinas difieren: síganla a mano en el NFA y en
su DFA.

## Qué se practica aquí

En `code/week-02/nfa.h` hay un `struct Nfa` y una función `subset_construction`: es lo que usan los ejemplos de
los apuntes, y pueden leerla cuanto quieran. Está escrita para que se lea como la definición, con conjuntos de
nombres, y no para ser rápida. `solution.cpp` se escribe **sin incluir `nfa.h`**: el juez compila ese único
archivo.

El trabajo del laboratorio está en tres decisiones:

- **Cómo representar un conjunto de estados** para que compararlos y buscarlos sea barato. Con $|Q| \leq 60$,
  un conjunto cabe en un entero de 64 bits, con un bit por estado. La unión es `|` y preguntar si hay algún
  estado de aceptación es `&`.
- **Cómo saber si un subconjunto ya apareció**, para no generarlo dos veces: un `std::map` o un
  `std::unordered_map` del conjunto a su número.
- **Qué nombre darle a cada uno.** El nombre natural, $\{q_0, q_1, q_2\}$, puede pasar de 20 caracteres. Basta
  el número de orden: `s0`, `s1`, `s2`…

Los casos traen, entre otros: transiciones $\varepsilon$ en cadena y en ciclo, un NFA sin estados de aceptación,
uno con un solo estado y ninguna transición, estados inalcanzables, un DFA como entrada, un estado que se llama
`eps`, pares repartidos en varias líneas y cuatro casos grandes.

## Cómo avanzar

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

1. **Lean el NFA.** Numeren los estados y los símbolos en el orden en que aparecen, y guarden $\delta$ por
   números. Empiecen con `casos/01.in`, que no tiene transiciones $\varepsilon$.
2. **Calculen la clausura $\varepsilon$** con una búsqueda en el grafo que solo tiene las flechas
   $\varepsilon$: desde cada estado del conjunto, sigan esas flechas hasta que no aparezca ningún estado nuevo.
   Antes de programarla, calculen a mano $E(\{q_a\})$ en `casos/03.in`.
3. **Generen los subconjuntos alcanzables con una cola.** El primero es $E(\{q_0\})$. Mientras la cola no esté
   vacía, saquen un subconjunto $S$ y calculen, para cada símbolo $a$, el conjunto
   $E\bigl(\bigcup_{q \in S} \delta(q, a)\bigr)$. Si es nuevo, denle el siguiente número y pónganlo en la cola.
   El conjunto vacío es un subconjunto como cualquier otro: si aparece, es el estado trampa del DFA.
4. **Escriban el DFA** y pásenlo por el juez. Si un caso da `WA`, lean el motivo que da el verificador y sigan a
   mano la cadena que muestra.
5. **Midan** cuántos estados salen con la familia de la sección siguiente.

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

Para ver su DFA funcionando, pásenle la salida al simulador que escribieron en el laboratorio de la semana 1,
agregando el bloque de cadenas:

```sh
{ build/solution < casos/02.in; printf 'strings: 3\n0101\n0100\n\n'; } | ../../../week-01/lab/dfa_sim/build/solution
```

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

## El k-ésimo símbolo desde el final

El lenguaje "el $k$-ésimo símbolo desde el final es $\mathtt{1}$" tiene un NFA de $k + 1$ estados. El programa
`kth_nfa` de la carpeta de la semana lo escribe para el $k$ que le pidan. Desde `code/week-02`, después de
correr `make` ahí:

```sh
build/kth_nfa 3 | lab/nfa_to_dfa/build/solution | head -1 | wc -w
```

La primera línea de su salida es `states:` seguida de los nombres, así que la cantidad de estados es ese número
menos 1. Con $k = 3$ debe salir 9: ocho estados.

Corran su programa con $k$ de 1 a 12 y llenen la tabla:

| $k$ | Estados del NFA | Estados de su DFA |
|---|---|---|
| 1 | 2 | |
| 2 | 3 | |
| 3 | 4 | 8 |
| … | | |
| 12 | 13 | |

Después respondan:

1. ¿Qué fórmula sigue la tercera columna? Compárenla con la tabla de los apuntes, en la sección *El costo: hasta
   2ⁿ estados*.
2. Para $k = 12$ el NFA tiene 13 estados y $2^{13} = 8192$ subconjuntos. ¿Cuántos alcanzó su programa? ¿Qué
   tienen en común todos los subconjuntos alcanzables?
3. ¿Hasta qué $k$ llega su programa en 2 segundos? ¿Qué se acaba primero, el tiempo o el límite de 10 000
   estados?

## Para seguir

Opcional, sin casos en el juez.

- Escriban la construcción de la unión: un programa que lea dos NFA, uno después del otro, y escriba el NFA con
  un estado inicial nuevo y dos transiciones $\varepsilon$. Pásenlo por su `solution` y comparen la cantidad de
  estados con el producto de la semana 1.
- Su DFA puede tener estados de más: dos subconjuntos distintos a veces se comportan igual. Con `casos/12.in`,
  ¿cuántos estados produce su programa? En la semana 4 veremos cómo hallar el DFA más pequeño.
lab/nfa_to_dfa/solution.cppDescargar lab/nfa_to_dfa/solution.cpp
// De NFA a DFA. Lee un NFA con transiciones ε en formato .nfa y escribe un DFA equivalente en
// formato .dfa, con solo los subconjuntos alcanzables.
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

// Con |Q| ≤ 60, un conjunto de estados cabe en un entero de 64 bits: el bit i dice si el
// estado número i está en el conjunto. Es una propuesta: también sirve un std::set<int>.
using StateSet = std::uint64_t;

// Los cinco componentes de N = (Q, Σ, δ, q0, F), con los nombres del formato.
struct Nfa {
    std::vector<std::string> states;               // Q: los nombres, en el orden de la entrada
    std::vector<char> alphabet;                    // Σ
    std::vector<std::vector<StateSet>> delta;      // δ: delta[i][j] es el conjunto al que va states[i] con alphabet[j]
    std::vector<StateSet> eps;                     // δ(q, ε): eps[i] es el conjunto al que va states[i] sin leer nada
    int start = 0;                                 // q0, como posición en states
    StateSet accept = 0;                           // F
};

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

    Nfa n;
    std::string line;
    // Por hacer:
    //   1. Leer la descripción línea por línea, hasta el final de la entrada.
    //   2. Calcular la clausura ε con una búsqueda en el grafo de las transiciones ε.
    //   3. Generar los subconjuntos alcanzables con una cola, a partir de E({q0}), y darle a
    //      cada uno un nombre nuevo y corto: s0, s1, s2…
    //   4. Escribir el DFA en formato .dfa.
    while (std::getline(std::cin, line)) {
    }
    // Este esqueleto no escribe nada, así que el verificador da WA en todos los casos.
    return static_cast<int>(n.states.size());
}
lab/nfa_to_dfa/verificador.cppDescargar lab/nfa_to_dfa/verificador.cpp
// Verificador de "De NFA a DFA": verificador ENTRADA ESPERADA SALIDA
// Hay muchos DFA correctos para un mismo NFA, así que no compara textos. Comprueba que SALIDA
//   1. es un DFA bien formado, en formato .dfa, con el mismo alfabeto que el NFA de ENTRADA;
//   2. respeta los límites del enunciado: a lo sumo 10 000 estados, nombres de hasta 20 caracteres;
//   3. reconoce el mismo lenguaje que el NFA.
// Para el punto 3 recorre a la vez el NFA (con su conjunto de estados activos) y el DFA
// entregado, como en la construcción del producto, y busca un par alcanzable en el que uno
// acepte y el otro no. Si lo encuentra, imprime la cadena más corta que lleva hasta él.
// ESPERADA (una respuesta correcta) no se usa. Termina con 0 si la salida es correcta.
#include <cstddef>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using Mask = std::uint64_t;

constexpr std::size_t MAX_STATES = 10000;
constexpr std::size_t MAX_NAME = 20;

struct Nfa {
    std::vector<std::string> states;
    std::vector<char> alphabet;
    std::vector<std::vector<Mask>> delta;  // delta[i][j]: destinos del estado i con alphabet[j]
    std::vector<Mask> eps;                 // eps[i]: destinos del estado i con ε
    int start = 0;
    Mask accept = 0;
};

struct Dfa {
    std::vector<std::string> states;
    std::vector<std::vector<int>> delta;  // delta[i][j]: destino del estado i con el símbolo j del NFA
    int start = 0;
    std::vector<bool> accept;
};

static 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;
}

// Las líneas de una descripción que no son comentarios ni están vacías, ya separadas en palabras.
static std::vector<std::vector<std::string>> read_lines(std::istream& in) {
    std::vector<std::vector<std::string>> lines;
    std::string line;
    while (std::getline(in, line)) {
        if (!line.empty() && line[0] == '#') {
            continue;
        }
        std::vector<std::string> words = split_words(line);
        if (!words.empty()) {
            lines.push_back(words);
        }
    }
    return lines;
}

// La entrada la escribió el curso: se lee sin revisar.
static Nfa read_nfa(std::istream& in) {
    Nfa n;
    std::map<std::string, int> index;
    std::map<char, int> column;
    bool in_delta = false;
    for (const std::vector<std::string>& words : read_lines(in)) {
        if (in_delta) {
            int from = index.at(words[0]);
            for (std::size_t i = 2; i < words.size(); i++) {
                Mask bit = Mask{1} << index.at(words[i]);
                if (words[1] == "eps") {
                    n.eps[from] |= bit;
                } else {
                    n.delta[from][column.at(words[1][0])] |= bit;
                }
            }
        } else if (words[0] == "states:") {
            n.states.assign(words.begin() + 1, words.end());
            for (std::size_t i = 0; i < n.states.size(); i++) {
                index[n.states[i]] = static_cast<int>(i);
            }
        } else if (words[0] == "alphabet:") {
            for (std::size_t i = 1; i < words.size(); i++) {
                column[words[i][0]] = static_cast<int>(n.alphabet.size());
                n.alphabet.push_back(words[i][0]);
            }
        } else if (words[0] == "start:") {
            n.start = index.at(words[1]);
        } else if (words[0] == "accept:") {
            for (std::size_t i = 1; i < words.size(); i++) {
                n.accept |= Mask{1} << index.at(words[i]);
            }
        } else if (words[0] == "delta:") {
            in_delta = true;
            n.delta.assign(n.states.size(), std::vector<Mask>(n.alphabet.size(), 0));
            n.eps.assign(n.states.size(), 0);
        }
    }
    return n;
}

// Lee el DFA entregado, revisando todo. Si algo está mal, deja el motivo en error y devuelve false.
static bool read_dfa(std::istream& in, const Nfa& n, Dfa& d, std::string& error) {
    std::vector<std::vector<std::string>> lines = read_lines(in);
    const char* fields[] = {"states:", "alphabet:", "start:", "accept:", "delta:"};
    if (lines.size() < 5) {
        error = "la salida no tiene los cinco campos states:, alphabet:, start:, accept: y delta:";
        return false;
    }
    for (int i = 0; i < 5; i++) {
        if (lines[i][0] != fields[i]) {
            error = std::string("se esperaba el campo ") + fields[i] + " y salió " + lines[i][0];
            return false;
        }
    }

    // states:
    d.states.assign(lines[0].begin() + 1, lines[0].end());
    if (d.states.empty()) {
        error = "states: no tiene ningún estado";
        return false;
    }
    if (d.states.size() > MAX_STATES) {
        error = "el DFA tiene " + std::to_string(d.states.size()) + " estados, y el límite es " +
                std::to_string(MAX_STATES) + ": construyan solo los subconjuntos alcanzables";
        return false;
    }
    std::unordered_map<std::string, int> index;
    for (std::size_t i = 0; i < d.states.size(); i++) {
        const std::string& name = d.states[i];
        if (name.size() > MAX_NAME) {
            error = "el nombre " + name.substr(0, 30) + "… pasa de " + std::to_string(MAX_NAME) + " caracteres";
            return false;
        }
        if (name.back() == ':') {
            error = "el nombre " + name + " termina con dos puntos";
            return false;
        }
        if (!index.insert({name, static_cast<int>(i)}).second) {
            error = "el estado " + name + " está repetido en states:";
            return false;
        }
    }

    // alphabet: los mismos símbolos que el NFA, en cualquier orden.
    std::map<char, int> column;
    for (std::size_t j = 0; j < n.alphabet.size(); j++) {
        column[n.alphabet[j]] = static_cast<int>(j);
    }
    std::set<char> sigma;
    for (std::size_t i = 1; i < lines[1].size(); i++) {
        const std::string& symbol = lines[1][i];
        if (symbol.size() != 1 || column.count(symbol[0]) == 0) {
            error = "el símbolo " + symbol + " no está en el alfabeto del NFA";
            return false;
        }
        if (!sigma.insert(symbol[0]).second) {
            error = "el símbolo " + symbol + " está repetido en alphabet:";
            return false;
        }
    }
    if (sigma.size() != n.alphabet.size()) {
        error = "al alfabeto del DFA le faltan símbolos del NFA";
        return false;
    }

    // start: y accept:
    if (lines[2].size() != 2 || index.count(lines[2][1]) == 0) {
        error = "start: lleva exactamente un estado, que debe estar en states:";
        return false;
    }
    d.start = index[lines[2][1]];
    d.accept.assign(d.states.size(), false);
    for (std::size_t i = 1; i < lines[3].size(); i++) {
        if (index.count(lines[3][i]) == 0) {
            error = "el estado de aceptación " + lines[3][i] + " no está en states:";
            return false;
        }
        d.accept[index[lines[3][i]]] = true;
    }

    // delta: exactamente una línea por cada par de estado y símbolo.
    if (lines[4].size() != 1) {
        error = "después de delta: las transiciones van una por línea";
        return false;
    }
    d.delta.assign(d.states.size(), std::vector<int>(n.alphabet.size(), -1));
    for (std::size_t k = 5; k < lines.size(); k++) {
        const std::vector<std::string>& words = lines[k];
        if (words.size() != 3) {
            error = "una transición de un DFA se escribe: estado símbolo destino. Salió una línea con " +
                    std::to_string(words.size()) + " palabras que empieza con " + words[0].substr(0, 30);
            return false;
        }
        if (index.count(words[0]) == 0 || index.count(words[2]) == 0) {
            error = "la transición " + words[0] + " " + words[1] + " " + words[2] + " usa un estado que no está en states:";
            return false;
        }
        if (words[1].size() != 1 || column.count(words[1][0]) == 0) {
            error = "la transición " + words[0] + " " + words[1] + " " + words[2] + " usa un símbolo que no está en el alfabeto";
            return false;
        }
        int& cell = d.delta[index[words[0]]][column[words[1][0]]];
        if (cell != -1) {
            error = "hay dos transiciones para δ(" + words[0] + ", " + words[1] + "): no es un DFA";
            return false;
        }
        cell = index[words[2]];
    }
    for (std::size_t i = 0; i < d.states.size(); i++) {
        for (std::size_t j = 0; j < n.alphabet.size(); j++) {
            if (d.delta[i][j] == -1) {
                error = "falta la transición δ(" + d.states[i] + ", " + n.alphabet[j] + "): en un DFA, δ es total";
                return false;
            }
        }
    }
    return true;
}

static Mask eps_closure(const Nfa& n, Mask set) {
    Mask closure = set;
    for (bool changed = true; changed;) {
        changed = false;
        for (std::size_t i = 0; i < n.states.size(); i++) {
            if (((closure >> i) & 1) && (n.eps[i] & ~closure) != 0) {
                closure |= n.eps[i];
                changed = true;
            }
        }
    }
    return closure;
}

// Un par alcanzable: el conjunto de estados activos del NFA y el estado del DFA entregado,
// con el par del que se llegó y el símbolo, para reconstruir la cadena.
struct Pair {
    int subset;
    int state;
    int parent;
    char symbol;
};

int main(int argc, char** argv) {
    if (argc != 4) {
        std::cout << "uso: verificador ENTRADA ESPERADA SALIDA\n";
        return 2;
    }
    std::ifstream input(argv[1]);
    std::ifstream output(argv[3]);
    if (!input || !output) {
        std::cout << "no se pudo abrir la entrada o la salida\n";
        return 2;
    }
    Nfa n = read_nfa(input);
    Dfa d;
    std::string error;
    if (!read_dfa(output, n, d, error)) {
        std::cout << error << '\n';
        return 1;
    }

    // closed[i][j] = E(δ(i, alphabet[j])).
    std::size_t symbols = n.alphabet.size();
    std::vector<std::vector<Mask>> closed(n.states.size(), std::vector<Mask>(symbols, 0));
    for (std::size_t i = 0; i < n.states.size(); i++) {
        for (std::size_t j = 0; j < symbols; j++) {
            closed[i][j] = eps_closure(n, n.delta[i][j]);
        }
    }

    // Recorrido en anchura de los pares (conjunto activo del NFA, estado del DFA).
    std::vector<Mask> subsets = {eps_closure(n, Mask{1} << n.start)};
    std::unordered_map<Mask, int> number = {{subsets[0], 0}};
    std::vector<Pair> pairs = {{0, d.start, -1, ' '}};
    std::unordered_set<std::uint64_t> seen = {static_cast<std::uint64_t>(d.start)};
    for (std::size_t at = 0; at < pairs.size(); at++) {
        Pair current = pairs[at];
        Mask set = subsets[current.subset];
        bool nfa_accepts = (set & n.accept) != 0;
        bool dfa_accepts = d.accept[current.state];
        if (nfa_accepts != dfa_accepts) {
            std::string w;
            for (int k = static_cast<int>(at); pairs[k].parent != -1; k = pairs[k].parent) {
                w = pairs[k].symbol + w;
            }
            std::string shown = w.empty() ? "la cadena vacía" : "la cadena " + (w.size() > 60 ? w.substr(0, 60) + "…" : w);
            std::cout << "no reconocen el mismo lenguaje: " << shown
                      << (nfa_accepts ? " la acepta el NFA y la rechaza el DFA" : " la rechaza el NFA y la acepta el DFA")
                      << '\n';
            return 1;
        }
        for (std::size_t j = 0; j < symbols; j++) {
            Mask target = 0;
            for (std::size_t i = 0; i < n.states.size(); i++) {
                if ((set >> i) & 1) {
                    target |= closed[i][j];
                }
            }
            auto [it, is_new] = number.insert({target, static_cast<int>(subsets.size())});
            if (is_new) {
                subsets.push_back(target);
            }
            int next_state = d.delta[current.state][j];
            std::uint64_t key = static_cast<std::uint64_t>(it->second) * (MAX_STATES + 1) +
                                static_cast<std::uint64_t>(next_state);
            if (seen.insert(key).second) {
                pairs.push_back({it->second, next_state, static_cast<int>(at), n.alphabet[j]});
            }
        }
    }
    return 0;
}

Compilación

Cómo se compilan y ejecutan los ejemplos.

MakefileDescargar Makefile
# Semana 2: autómatas finitos no deterministas, construcción de subconjuntos y propiedades de cierre.
# 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 clean     borra lo generado
#
# Las pruebas leen los autómatas de machines/ y de errors/, así que se corren desde esta carpeta.
# El laboratorio está en lab/nfa_to_dfa y tiene su propio Makefile: estas reglas no lo tocan.

CXX = g++
CXXFLAGS = -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined
BUILD = build
PROGRAMS = show_nfa run_nfa paths_nfa subset nfa_to_dfa run_dfa combine kth_nfa kth_table wrong_star swap_accept
TESTS = test_nfa test_subset test_closure
HEADERS = dfa.h nfa.h kth.h strings.h print.h test_helpers.h errors/wrong_constructions.h

.PHONY: all test clean

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

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

$(BUILD):
	mkdir -p $@

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

clean:
	rm -rf $(BUILD)