Semana 9 — Lo decidible y lo indecidible

Objetivos

  • Demostrar que un problema sobre autómatas o gramáticas es decidible, dando el algoritmo.
  • Describir la máquina universal y explicar por qué un programa puede recibir programas.
  • Demostrar por diagonalización que ATMA_{\mathrm{TM}} es indecidible.
  • Dar un lenguaje que ni siquiera es reconocible.

Sesión A — Lenguajes decidibles: problemas sobre autómatas y gramáticas

Lectura: Apuntes, semana 9.

Apoyo: Sipser, sec. 4.1 (Decidable Languages).

Temas:

  • Las máquinas como entradas: el lenguaje ADFA={ ⟨B,w⟩:B es un DFA que acepta w }A_{\mathrm{DFA}} = \{\, \langle B, w \rangle : B \text{ es un DFA que acepta } w \,\}. Decidirlo es simular.
  • ANFAA_{\mathrm{NFA}} y AREXA_{\mathrm{REX}}: se convierten con las construcciones de las semanas 2 y 3. Las demostraciones de entonces ahora son algoritmos.
  • EDFAE_{\mathrm{DFA}}, ¿el lenguaje es vacío?: alcanzabilidad en el diagrama.
  • EQDFA\mathrm{EQ}_{\mathrm{DFA}}, ¿dos DFA son equivalentes?: la diferencia simétrica con la construcción del producto, y después EDFAE_{\mathrm{DFA}}.
  • ACFGA_{\mathrm{CFG}}: con la forma normal de Chomsky, una derivación tiene 2n−12n - 1 pasos, o directamente CYK. ECFGE_{\mathrm{CFG}}: marcar las variables que generan algo.
  • EQCFG\mathrm{EQ}_{\mathrm{CFG}} no se resuelve igual, porque los lenguajes libres de contexto no son cerrados bajo complemento. Queda abierto hasta la semana 10.
  • Todo lenguaje libre de contexto es decidible. El mapa: regulares ⊂\subset libres de contexto ⊂\subset decidibles ⊂\subset reconocibles.
  • Error común: “decidir” simulando una máquina que podría no detenerse. Un DFA siempre termina; una máquina de Turing, no.

Sesión B — Máquina universal · Diagonalización · El problema de la parada

Lectura: Apuntes, semana 9.

Apoyo: Sipser, sec. 4.2 (Undecidability). Erickson, Models of Computation, nota 7 (Undecidability).

Temas:

  • ATM={ ⟨M,w⟩:M acepta w }A_{\mathrm{TM}} = \{\, \langle M, w \rangle : M \text{ acepta } w \,\}. Es reconocible: la máquina universal simula a MM. Un intérprete es una máquina universal.
  • Por qué simular no decide: si MM no se detiene, la simulación tampoco.
  • Repaso de una página: conjuntos numerables, y la diagonal de Cantor para los reales.
  • Hay más lenguajes que máquinas: las máquinas son numerables y los lenguajes no. Casi todos los lenguajes son irreconocibles.
  • ATMA_{\mathrm{TM}} es indecidible: si HH lo decidiera, la máquina DD, que con ⟨M⟩\langle M \rangle hace lo contrario de MM con ⟨M⟩\langle M \rangle, se contradice con la entrada ⟨D⟩\langle D \rangle. La tabla de la diagonal.
  • El problema de la parada, HALTTM\mathrm{HALT}_{\mathrm{TM}}, y por qué es el mismo fenómeno.
  • Si un lenguaje y su complemento son reconocibles, es decidible. Entonces el complemento de ATMA_{\mathrm{TM}} no es reconocible.
  • Qué significa en la práctica: no existe un programa que revise cualquier programa y diga si entra en un ciclo infinito.
  • Error común: concluir que “no se puede saber nada de ningún programa”. Indecidible quiere decir que ningún algoritmo acierta en todos los casos.

Laboratorio — ¿Son equivalentes dos DFA?

  1. Leer dos DFA sobre el mismo alfabeto y responder si reconocen el mismo lenguaje.
  2. Si no son equivalentes, imprimir una cadena más corta que uno acepta y el otro no.
  3. Recorrer solo los pares de estados alcanzables del producto, con una búsqueda en anchura.
  4. Pasar el caso grande, en el que construir el producto completo da TLE.
  5. Comprobar con su programa que el DFA de la semana 2 y su versión minimizada de la semana 4 son equivalentes.

Preguntas de repaso

  1. Den un algoritmo que decida si un DFA acepta alguna cadena de longitud par.
  2. ¿Por qué el argumento de EQDFA\mathrm{EQ}_{\mathrm{DFA}} no sirve para EQCFG\mathrm{EQ}_{\mathrm{CFG}}?
  3. Escriban la demostración de que ATMA_{\mathrm{TM}} es indecidible sin mirar los apuntes. ¿En qué paso se usa que HH siempre se detiene?
  4. Demuestren que si LL y su complemento son reconocibles, entonces LL es decidible.
  5. Un compañero dice que su programa detecta ciclos infinitos y que lo probó con mil programas. ¿Qué le responden, con precisión?

Código de la semana

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

Ejemplos (29)Pruebas (3)Laboratorio (10)Compilación (1)

Ejemplos

Los programas que usan los apuntes y la clase.

a_cfg.cppDescargar a_cfg.cpp
// A_CFG: ¿la gramática G genera la cadena w? Uso: a_cfg G.cfg CADENA...
// G debe estar en forma normal de Chomsky. Responde de las dos maneras de la clase: probando
// las derivaciones de 2n − 1 pasos y con CYK, y comprueba que coinciden.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>

#include "cfg.h"

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cerr << "uso: a_cfg G.cfg CADENA...\n";
        return 2;
    }
    try {
        Cfg g = load_cfg(argv[1]);
        std::cout << "G = " << argv[1] << ", " << g.rules.size() << " reglas, en forma normal de Chomsky: "
                  << (is_chomsky(g) ? "sí" : "no") << '\n';
        for (int i = 2; i < argc; i++) {
            std::string w = argv[i];
            std::size_t steps = w.empty() ? 1 : 2 * w.size() - 1;
            bool by_derivations = derives_bounded(g, w);
            bool by_table = cyk(g, w);
            if (by_derivations != by_table) {
                throw std::runtime_error("los dos algoritmos no coinciden");
            }
            std::cout << "w = " << (w.empty() ? "ε" : w) << ": n = " << w.size() << ", derivaciones de " << steps
                      << (steps == 1 ? " paso; " : " pasos; ")
                      << (by_table ? "G la genera, ⟨G, w⟩ ∈ A_CFG" : "G no la genera, ⟨G, w⟩ ∉ A_CFG") << '\n';
        }
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
a_dfa.cppDescargar a_dfa.cpp
// A_DFA: ¿el DFA B acepta la cadena w? Uso: a_dfa B.dfa CADENA...
// Decidir es simular: |w| pasos y una respuesta. La cadena vacía se pasa como ''.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

#include "decide.h"
#include "dfa.h"

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cerr << "uso: a_dfa B.dfa CADENA...\n";
        return 2;
    }
    try {
        Dfa b = load_dfa(argv[1]);
        std::cout << "B = " << argv[1] << ", " << b.states.size() << " estados\n";
        for (int i = 2; i < argc; i++) {
            std::string w = argv[i];
            std::vector<std::string> sequence = run(b, w);
            std::cout << "w = " << show(w) << "\n  " << sequence[0];
            for (std::size_t k = 0; k < w.size(); k++) {
                std::cout << " -" << w[k] << "-> " << sequence[k + 1];
            }
            bool ok = b.accept.count(sequence.back()) > 0;
            std::cout << "\n  " << w.size() << " pasos; termina en " << sequence.back()
                      << (ok ? ", que está en F: ⟨B, w⟩ ∈ A_DFA" : ", que no está en F: ⟨B, w⟩ ∉ A_DFA") << '\n';
        }
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
a_nfa.cppDescargar a_nfa.cpp
// A_NFA: ¿el NFA N acepta la cadena w? Uso: a_nfa N.nfa CADENA...
// Como en la demostración: primero se convierte N en un DFA con la construcción de
// subconjuntos, y después se corre el algoritmo de A_DFA.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

#include "decide.h"
#include "dfa.h"
#include "nfa.h"

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cerr << "uso: a_nfa N.nfa CADENA...\n";
        return 2;
    }
    try {
        Nfa n = load_nfa(argv[1]);
        Dfa d = subset_construction(n);
        std::cout << "N = " << argv[1] << ", " << n.states.size() << " estados\n";
        std::cout << "1. Construcción de subconjuntos: un DFA D con " << d.states.size()
                  << " estados (los subconjuntos alcanzables)\n";
        std::cout << "2. Correr D con cada cadena:\n";
        for (int i = 2; i < argc; i++) {
            std::string w = argv[i];
            std::vector<std::string> sequence = run(d, w);
            std::cout << "w = " << show(w) << "\n  " << sequence[0];
            for (std::size_t k = 0; k < w.size(); k++) {
                std::cout << " -" << w[k] << "-> " << sequence[k + 1];
            }
            bool ok = d.accept.count(sequence.back()) > 0;
            std::cout << "\n  " << (ok ? "acepta: ⟨N, w⟩ ∈ A_NFA" : "rechaza: ⟨N, w⟩ ∉ A_NFA") << '\n';
        }
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
alternate.cppDescargar alternate.cpp
// Dos reconocedores dan un decididor. Uso: alternate M1.tm M2.tm CADENA...
// M1 reconoce un lenguaje L y M2 reconoce su complemento. Con cada cadena se corren las dos,
// alternando un paso de cada una, hasta que alguna acepte. La cadena vacía se pasa como ''.
#include <iostream>
#include <stdexcept>
#include <string>

#include "tm.h"

int main(int argc, char** argv) {
    if (argc < 4) {
        std::cerr << "uso: alternate M1.tm M2.tm CADENA...\n";
        return 2;
    }
    try {
        Tm m1 = load_tm(argv[1]);
        Tm m2 = load_tm(argv[2]);
        const long limit = 1000000;
        for (int i = 3; i < argc; i++) {
            std::string w = argv[i];
            Alternation result = alternate(m1, m2, w, limit);
            std::cout << "w = " << (w.empty() ? "ε" : w) << ": ";
            if (result.winner == 0) {
                std::cout << "ninguna aceptó en " << limit << " rondas: M1 y M2 no reconocen un lenguaje y su complemento\n";
            } else {
                std::cout << "M" << result.winner << " acepta después de " << result.rounds
                          << (result.rounds == 1 ? " ronda; " : " rondas; ")
                          << (result.winner == 1 ? "se acepta" : "se rechaza") << '\n';
            }
        }
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
cfg.hDescargar cfg.h
// Gramática libre de contexto G = (V, Σ, R, S), en el formato .cfg de code/formats.md.
// Los procedimientos de decisión de la sesión A sobre gramáticas:
//
//   generating        E_CFG: marcar las variables que generan alguna cadena de terminales
//   derives_bounded   A_CFG como en la demostración: probar las derivaciones de 2n − 1 pasos
//   cyk               A_CFG con programación dinámica (semana 5)
#ifndef CFG_H
#define CFG_H

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

// Una regla A → X1 X2 … Xk. Cada símbolo del cuerpo es el nombre de una variable o un terminal
// (una cadena de un carácter). El cuerpo vacío es la regla A → ε.
struct Rule {
    std::string head;
    std::vector<std::string> body;
};

struct Cfg {
    std::vector<std::string> variables;  // V
    std::vector<char> terminals;         // Σ
    std::vector<Rule> rules;             // R, en el orden del archivo
    std::string start;                   // S
};

inline bool is_variable(const Cfg& g, const std::string& symbol) {
    for (const std::string& v : g.variables) {
        if (v == symbol) {
            return true;
        }
    }
    return false;
}

inline Cfg read_cfg(std::istream& in) {
    int number = 0;
    auto fail = [&number](const std::string& message) {
        throw std::runtime_error("línea " + std::to_string(number) + ": " + message);
    };
    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;
            }
            std::istringstream text(line);
            words.clear();
            std::string word;
            while (text >> word) {
                words.push_back(word);
            }
            if (!words.empty()) {
                return true;
            }
        }
        return false;
    };
    auto field = [&next_line, &fail](const std::string& name) {
        std::vector<std::string> words;
        if (!next_line(words) || words[0] != name + ":") {
            fail("se esperaba el campo " + name + ":");
        }
        words.erase(words.begin());
        return words;
    };

    Cfg g;
    g.variables = field("variables");
    std::set<std::string> known(g.variables.begin(), g.variables.end());
    for (const std::string& symbol : field("terminals")) {
        if (symbol.size() != 1 || symbol[0] == '#') {
            fail("un terminal es un solo carácter distinto de #: " + symbol);
        }
        if (known.count(symbol) > 0) {
            fail("el símbolo " + symbol + " es variable y terminal a la vez");
        }
        g.terminals.push_back(symbol[0]);
        known.insert(symbol);
    }
    std::vector<std::string> start = field("start");
    if (start.size() != 1 || !is_variable(g, start[0])) {
        fail("start: lleva exactamente una variable");
    }
    g.start = start[0];
    if (!field("rules").empty()) {
        fail("después de rules: las reglas van una por línea");
    }
    std::vector<std::string> words;
    while (next_line(words)) {
        if (words.size() < 3 || words[1] != "->" || !is_variable(g, words[0])) {
            fail("una regla se escribe: variable -> alternativa | alternativa");
        }
        Rule rule = {words[0], {}};
        bool is_eps = false;
        bool any = false;
        auto close = [&]() {
            if (!any || (is_eps && !rule.body.empty())) {
                fail("alternativa vacía o mal escrita (la vacía se escribe eps)");
            }
            g.rules.push_back(rule);
            rule.body.clear();
            is_eps = false;
            any = false;
        };
        for (std::size_t i = 2; i < words.size(); i++) {
            if (words[i] == "|") {
                close();
            } else if (words[i] == "eps") {
                is_eps = true;
                any = true;
            } else {
                if (known.count(words[i]) == 0) {
                    fail("símbolo desconocido: " + words[i]);
                }
                rule.body.push_back(words[i]);
                any = true;
            }
        }
        close();
    }
    return g;
}

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

inline std::string show_rule(const Rule& rule) {
    std::string text = rule.head + " →";
    for (const std::string& symbol : rule.body) {
        text += " " + symbol;
    }
    return rule.body.empty() ? text + " ε" : text;
}

// ------------------------------------------------------------
// E_CFG: marcar
// ------------------------------------------------------------

// Las variables que generan alguna cadena de terminales, agrupadas por ronda. En cada ronda
// se marca toda variable A con una regla A → X1 … Xk cuyos símbolos son todos terminales o
// variables marcadas en rondas anteriores. Se detiene cuando una ronda no marca nada: como en
// cada ronda útil se marca al menos una variable, hay a lo sumo |V| + 1 rondas.
inline std::vector<std::vector<std::string>> generating_rounds(const Cfg& g) {
    std::set<std::string> marked;
    std::vector<std::vector<std::string>> rounds;
    while (true) {
        std::vector<std::string> fresh;
        for (const std::string& v : g.variables) {
            if (marked.count(v) > 0) {
                continue;
            }
            for (const Rule& rule : g.rules) {
                if (rule.head != v) {
                    continue;
                }
                bool all = true;
                for (const std::string& symbol : rule.body) {
                    if (is_variable(g, symbol) && marked.count(symbol) == 0) {
                        all = false;
                        break;
                    }
                }
                if (all) {
                    fresh.push_back(v);
                    break;
                }
            }
        }
        if (fresh.empty()) {
            return rounds;
        }
        marked.insert(fresh.begin(), fresh.end());
        rounds.push_back(fresh);
    }
}

inline std::set<std::string> generating(const Cfg& g) {
    std::set<std::string> marked;
    for (const std::vector<std::string>& round : generating_rounds(g)) {
        marked.insert(round.begin(), round.end());
    }
    return marked;
}

// ¿L(G) = ∅? Es decir, ¿⟨G⟩ ∈ E_CFG? L(G) es vacío si y solo si S no queda marcada.
inline bool is_empty(const Cfg& g) {
    return generating(g).count(g.start) == 0;
}

// ------------------------------------------------------------
// A_CFG
// ------------------------------------------------------------

// ¿Está G en forma normal de Chomsky? Reglas A → BC, con B y C variables distintas de S;
// A → a; y S → ε, solo para la variable inicial.
inline bool is_chomsky(const Cfg& g) {
    for (const Rule& rule : g.rules) {
        if (rule.body.empty()) {
            if (rule.head != g.start) {
                return false;
            }
        } else if (rule.body.size() == 1) {
            if (is_variable(g, rule.body[0])) {
                return false;
            }
        } else if (rule.body.size() == 2) {
            for (const std::string& symbol : rule.body) {
                if (!is_variable(g, symbol) || symbol == g.start) {
                    return false;
                }
            }
        } else {
            return false;
        }
    }
    return true;
}

// A_CFG como en la demostración. Con G en forma normal de Chomsky, toda derivación de una
// cadena de longitud n ≥ 1 tiene exactamente 2n − 1 pasos (y la de ε, un paso). Entonces basta
// probar las derivaciones por la izquierda de a lo sumo `steps` pasos, que son finitas.
// Se descartan las formas que ya no pueden dar w: en forma normal de Chomsky una forma nunca
// se acorta, y los terminales de su prefijo ya no cambian.
inline bool derives_within(const Cfg& g, const std::vector<std::string>& form, const std::string& w,
                           std::size_t steps) {
    if (form.size() > w.size() && !(w.empty() && form.size() == 1)) {
        return false;
    }
    std::size_t i = 0;
    while (i < form.size() && !is_variable(g, form[i])) {
        if (i >= w.size() || form[i][0] != w[i]) {
            return false;
        }
        i++;
    }
    if (i == form.size()) {
        return form.size() == w.size();
    }
    if (steps == 0) {
        return false;
    }
    for (const Rule& rule : g.rules) {
        if (rule.head != form[i]) {
            continue;
        }
        std::vector<std::string> next(form.begin(), form.begin() + static_cast<std::ptrdiff_t>(i));
        next.insert(next.end(), rule.body.begin(), rule.body.end());
        next.insert(next.end(), form.begin() + static_cast<std::ptrdiff_t>(i) + 1, form.end());
        if (derives_within(g, next, w, steps - 1)) {
            return true;
        }
    }
    return false;
}

inline bool derives_bounded(const Cfg& g, const std::string& w) {
    if (!is_chomsky(g)) {
        throw std::runtime_error("la gramática no está en forma normal de Chomsky");
    }
    std::size_t steps = w.empty() ? 1 : 2 * w.size() - 1;
    return derives_within(g, {g.start}, w, steps);
}

// CYK. table[i][j] es el conjunto de variables que generan la subcadena de w que empieza en
// la posición i y tiene longitud j + 1.
using CykTable = std::vector<std::vector<std::set<std::string>>>;

inline CykTable cyk_table(const Cfg& g, const std::string& w) {
    if (!is_chomsky(g)) {
        throw std::runtime_error("la gramática no está en forma normal de Chomsky");
    }
    std::size_t n = w.size();
    CykTable table(n, std::vector<std::set<std::string>>(n));
    for (std::size_t i = 0; i < n; i++) {
        for (const Rule& rule : g.rules) {
            if (rule.body.size() == 1 && rule.body[0][0] == w[i]) {
                table[i][0].insert(rule.head);
            }
        }
    }
    for (std::size_t len = 2; len <= n; len++) {
        for (std::size_t i = 0; i + len <= n; i++) {
            for (std::size_t left = 1; left < len; left++) {
                for (const Rule& rule : g.rules) {
                    if (rule.body.size() == 2 && table[i][left - 1].count(rule.body[0]) > 0 &&
                        table[i + left][len - left - 1].count(rule.body[1]) > 0) {
                        table[i][len - 1].insert(rule.head);
                    }
                }
            }
        }
    }
    return table;
}

inline bool cyk(const Cfg& g, const std::string& w) {
    if (w.empty()) {
        if (!is_chomsky(g)) {
            throw std::runtime_error("la gramática no está en forma normal de Chomsky");
        }
        for (const Rule& rule : g.rules) {
            if (rule.head == g.start && rule.body.empty()) {
                return true;
            }
        }
        return false;
    }
    return cyk_table(g, w)[0][w.size() - 1].count(g.start) > 0;
}

#endif
decide.hDescargar decide.h
// Procedimientos de decisión sobre DFA. Cada función es uno de los algoritmos de la sesión A,
// y todas terminan siempre: recorren un conjunto finito de estados o de pares de estados.
//
//   accepts (en dfa.h)       A_DFA: simular
//   shortest_accepted        E_DFA: alcanzabilidad, con una búsqueda en anchura
//   symmetric_difference     el DFA C de la demostración de EQ_DFA, con el producto completo
//   compare                  EQ_DFA: solo los pares alcanzables, y una cadena más corta que separa
#ifndef DECIDE_H
#define DECIDE_H

#include <algorithm>
#include <cstddef>
#include <map>
#include <optional>
#include <queue>
#include <set>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

#include "dfa.h"

// E_DFA. Busca en anchura desde q0 y devuelve una cadena más corta de L(M), o nada si
// L(M) = ∅. La búsqueda visita cada estado una sola vez, así que termina.
inline std::optional<std::string> shortest_accepted(const Dfa& m) {
    // Cómo se llegó a cada estado marcado: desde qué estado y con qué símbolo.
    std::map<std::string, std::pair<std::string, char>> parent;
    std::set<std::string> marked = {m.start};
    std::queue<std::string> pending;
    pending.push(m.start);
    while (!pending.empty()) {
        std::string q = pending.front();
        pending.pop();
        if (m.accept.count(q) > 0) {
            std::string w;
            while (q != m.start) {
                w += parent.at(q).second;
                q = parent.at(q).first;
            }
            std::reverse(w.begin(), w.end());
            return w;
        }
        for (char a : m.alphabet) {
            const std::string& next = step(m, q, a);
            if (marked.insert(next).second) {
                parent[next] = {q, a};
                pending.push(next);
            }
        }
    }
    return std::nullopt;
}

// ¿L(M) = ∅? Es decir, ¿⟨M⟩ ∈ E_DFA?
inline bool is_empty(const Dfa& m) {
    return !shortest_accepted(m).has_value();
}

inline void require_same_alphabet(const Dfa& a, const Dfa& b) {
    std::set<char> sigma_a(a.alphabet.begin(), a.alphabet.end());
    std::set<char> sigma_b(b.alphabet.begin(), b.alphabet.end());
    if (sigma_a != sigma_b) {
        throw std::runtime_error("los dos DFA deben tener el mismo alfabeto");
    }
}

// El DFA C con L(C) = diferencia simétrica de L(A) y L(B): el producto completo, con todos
// los pares, y F = los pares en los que exactamente uno de los dos estados es de aceptación.
inline Dfa symmetric_difference(const Dfa& a, const Dfa& b) {
    require_same_alphabet(a, b);
    Dfa c;
    c.alphabet = a.alphabet;
    c.start = pair_name(a.start, b.start);
    for (const std::string& p : a.states) {
        for (const std::string& q : b.states) {
            std::string name = pair_name(p, q);
            c.states.push_back(name);
            if ((a.accept.count(p) > 0) != (b.accept.count(q) > 0)) {
                c.accept.insert(name);
            }
            for (char s : c.alphabet) {
                c.delta[{name, s}] = pair_name(step(a, p, s), step(b, q, s));
            }
        }
    }
    check_dfa(c);
    return c;
}

// El resultado de comparar dos DFA.
struct Comparison {
    bool equivalent = true;
    std::string witness;                                     // si no lo son: una cadena más corta que los separa
    std::vector<std::pair<std::string, std::string>> pairs;  // los pares visitados, en el orden de la búsqueda
};

// EQ_DFA sin construir el producto. Busca en anchura desde (qA, qB) y solo genera los pares
// alcanzables. Si encuentra un par con un estado de aceptación y otro que no, la cadena que
// llevó hasta él separa a los dos autómatas, y por ser búsqueda en anchura es de las más cortas.
// Termina: hay a lo sumo |QA| · |QB| pares y cada uno se visita una vez.
inline Comparison compare(const Dfa& a, const Dfa& b) {
    require_same_alphabet(a, b);
    using Pair = std::pair<std::string, std::string>;
    Comparison result;
    std::map<Pair, std::pair<Pair, char>> parent;
    std::set<Pair> marked;
    std::queue<Pair> pending;
    Pair first = {a.start, b.start};
    marked.insert(first);
    pending.push(first);
    while (!pending.empty()) {
        Pair current = pending.front();
        pending.pop();
        result.pairs.push_back(current);
        if ((a.accept.count(current.first) > 0) != (b.accept.count(current.second) > 0)) {
            result.equivalent = false;
            while (current != first) {
                result.witness += parent.at(current).second;
                current = parent.at(current).first;
            }
            std::reverse(result.witness.begin(), result.witness.end());
            return result;
        }
        for (char s : a.alphabet) {
            Pair next = {step(a, current.first, s), step(b, current.second, s)};
            if (marked.insert(next).second) {
                parent[next] = {current, s};
                pending.push(next);
            }
        }
    }
    return result;
}

// Todos los pares alcanzables desde (qA, qB), sin detenerse en el primero que separa.
inline std::size_t reachable_pairs(const Dfa& a, const Dfa& b) {
    require_same_alphabet(a, b);
    using Pair = std::pair<std::string, std::string>;
    std::set<Pair> marked = {{a.start, b.start}};
    std::queue<Pair> pending;
    pending.push({a.start, b.start});
    while (!pending.empty()) {
        Pair current = pending.front();
        pending.pop();
        for (char s : a.alphabet) {
            Pair next = {step(a, current.first, s), step(b, current.second, s)};
            if (marked.insert(next).second) {
                pending.push(next);
            }
        }
    }
    return marked.size();
}

// La cadena w como se muestra en pantalla: ε si es vacía.
inline std::string show(const std::string& w) {
    return w.empty() ? "ε" : w;
}

#endif
dfa.hDescargar dfa.h
// Autómata finito determinista. El struct tiene los cinco componentes de la definición
// M = (Q, Σ, δ, q0, F), con los nombres del formato .dfa de code/formats.md.
// Es el dfa.h de la semana 1, copiado sin cambios para que esta carpeta se compile sola:
// leer y escribir el formato, la función de transición extendida, la construcción del
// producto y el complemento. Los procedimientos de decisión de esta semana están en decide.h.
#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
e_cfg.cppDescargar e_cfg.cpp
// E_CFG: ¿el lenguaje de la gramática G es vacío? Uso: e_cfg G.cfg
// Marca las variables que generan alguna cadena de terminales, ronda por ronda.
#include <cstddef>
#include <iostream>
#include <set>
#include <stdexcept>
#include <string>
#include <vector>

#include "cfg.h"

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: e_cfg G.cfg\n";
        return 2;
    }
    try {
        Cfg g = load_cfg(argv[1]);
        std::cout << "G = " << argv[1] << ", " << g.variables.size() << " variables, " << g.rules.size()
                  << " reglas, inicial " << g.start << '\n';
        std::vector<std::vector<std::string>> rounds = generating_rounds(g);
        std::set<std::string> marked;
        for (std::size_t i = 0; i < rounds.size(); i++) {
            std::cout << "ronda " << i + 1 << ":";
            for (const std::string& v : rounds[i]) {
                // La primera regla de v cuyos símbolos ya estaban todos marcados o son terminales.
                for (const Rule& rule : g.rules) {
                    bool all = rule.head == v;
                    for (const std::string& symbol : rule.body) {
                        all = all && (!is_variable(g, symbol) || marked.count(symbol) > 0);
                    }
                    if (all) {
                        std::cout << "  se marca " << v << " por " << show_rule(rule) << ";";
                        break;
                    }
                }
            }
            std::cout << '\n';
            marked.insert(rounds[i].begin(), rounds[i].end());
        }
        std::cout << "ronda " << rounds.size() + 1 << ":  no se marca nada, termina\n";
        std::cout << "marcadas: " << marked.size() << " de " << g.variables.size() << '\n';
        if (marked.count(g.start) > 0) {
            std::cout << g.start << " está marcada: L(G) ≠ ∅, ⟨G⟩ ∉ E_CFG\n";
        } else {
            std::cout << g.start << " no está marcada: L(G) = ∅, ⟨G⟩ ∈ E_CFG\n";
        }
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
e_dfa.cppDescargar e_dfa.cpp
// E_DFA: ¿el lenguaje del DFA A es vacío? Uso: e_dfa A.dfa
// Marca los estados alcanzables desde el inicial, por distancia, y mira si alguno es de
// aceptación. No prueba ninguna cadena.
#include <cstddef>
#include <iostream>
#include <optional>
#include <set>
#include <stdexcept>
#include <string>
#include <vector>

#include "decide.h"
#include "dfa.h"

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: e_dfa A.dfa\n";
        return 2;
    }
    try {
        Dfa a = load_dfa(argv[1]);
        std::cout << "A = " << argv[1] << ", " << a.states.size() << " estados, F = {";
        bool first = true;
        for (const std::string& q : a.states) {
            if (a.accept.count(q) > 0) {
                std::cout << (first ? "" : ", ") << q;
                first = false;
            }
        }
        std::cout << "}\n";
        // Las mismas marcas que shortest_accepted, mostradas ronda por ronda.
        std::set<std::string> marked = {a.start};
        std::vector<std::string> round = {a.start};
        for (int number = 0; !round.empty(); number++) {
            std::cout << "ronda " << number << ": se marca";
            for (const std::string& q : round) {
                std::cout << ' ' << q;
            }
            std::cout << '\n';
            std::vector<std::string> next;
            for (const std::string& q : round) {
                for (char s : a.alphabet) {
                    const std::string& target = step(a, q, s);
                    if (marked.insert(target).second) {
                        next.push_back(target);
                    }
                }
            }
            round = next;
        }
        std::cout << "marcados: " << marked.size() << " de " << a.states.size() << '\n';
        std::optional<std::string> w = shortest_accepted(a);
        if (w.has_value()) {
            std::cout << "hay un estado de aceptación marcado: L(A) ≠ ∅, ⟨A⟩ ∉ E_DFA\n";
            std::cout << "una cadena más corta de L(A): " << show(*w) << '\n';
        } else {
            std::cout << "ningún estado de aceptación está marcado: L(A) = ∅, ⟨A⟩ ∈ E_DFA\n";
        }
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
eq_dfa.cppDescargar eq_dfa.cpp
// EQ_DFA: ¿dos DFA reconocen el mismo lenguaje? Uso: eq_dfa A.dfa B.dfa [--producto] [--pares]
// Sin opciones recorre solo los pares alcanzables del producto. Con --producto construye el
// DFA C de la demostración, con todos los pares, y le aplica el algoritmo de E_DFA: la
// respuesta es la misma. Con --pares lista los pares en el orden en que se visitan.
#include <cstddef>
#include <iostream>
#include <optional>
#include <stdexcept>
#include <string>

#include "decide.h"
#include "dfa.h"

int main(int argc, char** argv) {
    bool full = false;
    bool list = false;
    bool usage = argc < 3;
    for (int i = 3; i < argc; i++) {
        std::string option = argv[i];
        if (option == "--producto") {
            full = true;
        } else if (option == "--pares") {
            list = true;
        } else {
            usage = true;
        }
    }
    if (usage) {
        std::cerr << "uso: eq_dfa A.dfa B.dfa [--producto] [--pares]\n";
        return 2;
    }
    try {
        Dfa a = load_dfa(argv[1]);
        Dfa b = load_dfa(argv[2]);
        std::cout << "A = " << argv[1] << ", " << a.states.size() << " estados\n";
        std::cout << "B = " << argv[2] << ", " << b.states.size() << " estados\n";
        std::string witness;
        bool equivalent = true;
        if (full) {
            Dfa c = symmetric_difference(a, b);
            std::cout << "C, el producto completo: " << c.states.size() << " estados, " << c.accept.size()
                      << " de aceptación, " << reachable(c).size() << " alcanzables\n";
            std::optional<std::string> w = shortest_accepted(c);
            equivalent = !w.has_value();
            witness = w.value_or("");
            std::cout << (equivalent ? "L(C) = ∅" : "L(C) ≠ ∅") << '\n';
        } else {
            Comparison result = compare(a, b);
            equivalent = result.equivalent;
            witness = result.witness;
            std::cout << "pares visitados: " << result.pairs.size() << " de " << a.states.size() * b.states.size()
                      << '\n';
            if (list) {
                for (const auto& [p, q] : result.pairs) {
                    bool differ = (a.accept.count(p) > 0) != (b.accept.count(q) > 0);
                    std::cout << "  " << pair_name(p, q) << (differ ? "  <- uno acepta y el otro no" : "") << '\n';
                }
            }
        }
        if (equivalent) {
            std::cout << "equivalentes: L(A) = L(B), ⟨A, B⟩ ∈ EQ_DFA\n";
        } else {
            std::cout << "distintos: ⟨A, B⟩ ∉ EQ_DFA\n";
            std::cout << "una cadena más corta que los separa: " << show(witness) << " (" << witness.size()
                      << " símbolos); A la " << (accepts(a, witness) ? "acepta" : "rechaza") << " y B la "
                      << (accepts(b, witness) ? "acepta" : "rechaza") << '\n';
        }
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
make_kth.cppDescargar make_kth.cpp
// Escribe los autómatas de "el k-ésimo símbolo desde el final es 1" que usa el laboratorio.
// Uso: make_kth K CARPETA
//
//   kthK.nfa          el NFA de k + 1 estados de la semana 2
//   kthK_subsets.dfa  la construcción de subconjuntos, solo los subconjuntos alcanzables
//   kthK_all.dfa      la construcción de subconjuntos con los 2^(k+1) subconjuntos
//   kthK_history.dfa  un DFA escrito a mano: recuerda los últimos k símbolos, o menos si aún
//                     no leyó k; un estado por cada cadena de longitud a lo sumo k
//   kthK_min.dfa      el DFA mínimo, que sale de minimizar kthK_history.dfa
//   kthK_wrong.dfa    el mínimo con dos estados fusionados por error: ya no es equivalente
#include <cstddef>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

#include "decide.h"
#include "dfa.h"
#include "minimize.h"
#include "nfa.h"

// El NFA: q0 se queda en q0 con todo y, con un 1, además adivina que ese es el k-ésimo desde
// el final. Después cuenta k − 1 símbolos más.
static Nfa kth_nfa(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++) {
        for (char a : n.alphabet) {
            n.delta[{"q" + std::to_string(i), a}] = {"q" + std::to_string(i + 1)};
        }
    }
    return n;
}

// El DFA que recuerda lo último leído. El estado h seguido de una cadena u, con |u| ≤ k, dice:
// "lo leído termina en u" si |u| = k, y "lo leído es exactamente u" si |u| < k.
static Dfa kth_history(int k) {
    Dfa m;
    m.alphabet = {'0', '1'};
    std::vector<std::string> histories = {""};
    for (std::size_t i = 0; i < histories.size(); i++) {
        if (histories[i].size() < static_cast<std::size_t>(k)) {
            histories.push_back(histories[i] + "0");
            histories.push_back(histories[i] + "1");
        }
    }
    for (const std::string& u : histories) {
        std::string name = "h" + u;
        m.states.push_back(name);
        if (u.size() == static_cast<std::size_t>(k) && u[0] == '1') {
            m.accept.insert(name);
        }
        for (char a : m.alphabet) {
            std::string next = u + a;
            if (next.size() > static_cast<std::size_t>(k)) {
                next = next.substr(1);
            }
            m.delta[{name, a}] = "h" + next;
        }
    }
    m.start = "h";
    check_dfa(m);
    return m;
}

static void save(const std::string& path, const std::string& comment, const Dfa& m) {
    std::ofstream file(path);
    if (!file) {
        throw std::runtime_error("no se pudo escribir " + path);
    }
    file << comment;
    write_dfa(file, m);
}

int main(int argc, char** argv) {
    if (argc != 3 || std::atoi(argv[1]) < 1 || std::atoi(argv[1]) > 10) {
        std::cerr << "uso: make_kth K CARPETA, con K de 1 a 10\n";
        return 2;
    }
    try {
        int k = std::atoi(argv[1]);
        std::string base = std::string(argv[2]) + "/kth" + std::to_string(k);
        std::string title = "# El símbolo número " + std::to_string(k) + " desde el final es 1.\n";

        Nfa n = kth_nfa(k);
        {
            std::ofstream file(base + ".nfa");
            if (!file) {
                throw std::runtime_error("no se pudo escribir " + base + ".nfa");
            }
            file << title << "# El NFA de " << k + 1 << " estados.\nstates:";
            for (const std::string& q : n.states) {
                file << ' ' << q;
            }
            file << "\nalphabet: 0 1\nstart: q0\naccept: q" << k << "\ndelta:\n";
            for (const auto& [key, targets] : n.delta) {
                file << key.first << ' ' << key.second;
                for (const std::string& q : targets) {
                    file << ' ' << q;
                }
                file << '\n';
            }
        }
        Dfa subsets = subset_construction(n);
        Dfa all = subset_construction(n, true);
        Dfa history = kth_history(k);
        Dfa minimal = minimize(history);
        save(base + "_subsets.dfa", title + "# Construcción de subconjuntos del NFA: solo los subconjuntos alcanzables.\n", subsets);
        save(base + "_all.dfa", title + "# Construcción de subconjuntos del NFA con todos los subconjuntos, alcanzables o no.\n", all);
        save(base + "_history.dfa", title + "# Recuerda los últimos símbolos leídos: un estado por cada cadena de longitud a lo sumo " +
                                        std::to_string(k) + ".\n", history);
        save(base + "_min.dfa", title + "# El DFA mínimo: sale de minimizar el que recuerda los últimos símbolos.\n", minimal);

        // El error de la semana 4: fusionar dos estados porque "se parecen". Aquí, el estado al
        // que se llega con 11 se fusiona con el estado al que se llega con 10.
        Dfa wrong = minimal;
        std::string kept = delta_star(minimal, minimal.start, "10");
        std::string gone = delta_star(minimal, minimal.start, "11");
        for (auto& [key, target] : wrong.delta) {
            if (target == gone) {
                target = kept;
            }
        }
        wrong = remove_unreachable(wrong);
        save(base + "_wrong.dfa", title + "# El DFA mínimo con dos estados fusionados por error. No es equivalente a los otros.\n", wrong);

        std::cout << "k = " << k << '\n';
        std::cout << "archivo               estados  alcanzables\n";
        auto row = [](const std::string& name, const Dfa& m) {
            std::string count = std::to_string(m.states.size());
            std::string reach = std::to_string(reachable(m).size());
            std::cout << name << std::string(22 - name.size(), ' ') << std::string(7 - count.size(), ' ') << count
                      << std::string(13 - reach.size(), ' ') << reach << '\n';
        };
        std::string stem = "kth" + std::to_string(k);
        row(stem + "_subsets.dfa", subsets);
        row(stem + "_all.dfa", all);
        row(stem + "_history.dfa", history);
        row(stem + "_min.dfa", minimal);
        row(stem + "_wrong.dfa", wrong);
        std::cout << "minimizar " << stem << "_subsets.dfa da " << minimize(subsets).states.size() << " estados\n";
        if (!compare(subsets, all).equivalent || !compare(subsets, history).equivalent ||
            !compare(subsets, minimal).equivalent) {
            throw std::runtime_error("los autómatas generados no son equivalentes");
        }
        std::cout << "los cuatro primeros son equivalentes\n";
        Comparison broken = compare(minimal, wrong);
        if (broken.equivalent) {
            throw std::runtime_error("el autómata con el error salió equivalente");
        }
        std::cout << stem << "_min.dfa y " << stem << "_wrong.dfa se separan con " << show(broken.witness) << '\n';
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
minimize.hDescargar minimize.h
// Minimización de un DFA, como en la semana 4: quitar los estados inalcanzables y fusionar los
// indistinguibles, refinando la partición {F, Q − F} hasta que no cambie.
// Aquí solo se usa para producir los autómatas de lab/dfa_equiv/machines.
#ifndef MINIMIZE_H
#define MINIMIZE_H

#include <cstddef>
#include <map>
#include <string>
#include <utility>
#include <vector>

#include "dfa.h"

// Devuelve el DFA mínimo equivalente a m. Sus estados se llaman prefix0, prefix1, ...
inline Dfa minimize(const Dfa& original, const std::string& prefix = "s") {
    Dfa m = remove_unreachable(original);
    // block[q] es el número del bloque de q. Se empieza con dos bloques: F y Q − F.
    std::map<std::string, std::size_t> block;
    for (const std::string& q : m.states) {
        block[q] = m.accept.count(q) > 0 ? 1 : 0;
    }
    std::size_t count = 0;
    while (true) {
        // La firma de un estado: su bloque y el bloque de cada uno de sus destinos.
        // Dos estados siguen juntos solo si tienen la misma firma.
        std::map<std::vector<std::size_t>, std::size_t> number;
        std::map<std::string, std::size_t> refined;
        for (const std::string& q : m.states) {
            std::vector<std::size_t> signature = {block.at(q)};
            for (char a : m.alphabet) {
                signature.push_back(block.at(step(m, q, a)));
            }
            auto it = number.find(signature);
            if (it == number.end()) {
                it = number.insert({signature, number.size()}).first;
            }
            refined[q] = it->second;
        }
        bool stable = number.size() == count;
        count = number.size();
        block = refined;
        if (stable) {
            break;
        }
    }
    Dfa result;
    result.alphabet = m.alphabet;
    std::vector<bool> done(count, false);
    for (const std::string& q : m.states) {
        std::size_t b = block.at(q);
        if (done[b]) {
            continue;
        }
        done[b] = true;
        std::string name = prefix + std::to_string(b);
        result.states.push_back(name);
        if (m.accept.count(q) > 0) {
            result.accept.insert(name);
        }
        for (char a : m.alphabet) {
            result.delta[{name, a}] = prefix + std::to_string(block.at(step(m, q, a)));
        }
    }
    result.start = prefix + std::to_string(block.at(m.start));
    check_dfa(result);
    return result;
}

#endif
nfa.hDescargar nfa.h
// Autómata finito no determinista, con transiciones ε, en el formato .nfa de code/formats.md.
// Solo lo que hace falta esta semana: leerlo, y la construcción de subconjuntos de la semana 2,
// que es el paso 1 del algoritmo que decide A_NFA.
#ifndef NFA_H
#define NFA_H

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

#include "dfa.h"

const char EPS = '\0';  // la clave de las transiciones ε en delta

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

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);
    };
    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;
    };
    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::set<std::string> q(n.states.begin(), n.states.end());
    std::set<char> sigma(n.alphabet.begin(), n.alphabet.end());
    std::vector<std::string> words;
    while (next_line(words)) {
        if (words.size() < 3) {
            fail("una transición se escribe: estado símbolo destino...");
        }
        char symbol = EPS;
        if (words[1] != "eps") {
            if (words[1].size() != 1 || sigma.count(words[1][0]) == 0) {
                fail("símbolo desconocido: " + words[1]);
            }
            symbol = words[1][0];
        }
        if (q.count(words[0]) == 0) {
            fail("estado desconocido: " + words[0]);
        }
        for (std::size_t i = 2; i < words.size(); i++) {
            if (q.count(words[i]) == 0) {
                fail("estado desconocido: " + words[i]);
            }
            n.delta[{words[0], symbol}].insert(words[i]);
        }
    }
    if (q.count(n.start) == 0) {
        fail("el estado inicial no está en states");
    }
    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());
    }
}

// Clausura ε: los estados a los que se llega desde el conjunto con cero o más transiciones ε.
inline std::set<std::string> eps_closure(const Nfa& n, std::set<std::string> current) {
    std::queue<std::string> pending;
    for (const std::string& q : current) {
        pending.push(q);
    }
    while (!pending.empty()) {
        std::string q = pending.front();
        pending.pop();
        auto it = n.delta.find({q, EPS});
        if (it == n.delta.end()) {
            continue;
        }
        for (const std::string& next : it->second) {
            if (current.insert(next).second) {
                pending.push(next);
            }
        }
    }
    return current;
}

// Un paso del conjunto de estados activos con el símbolo a, con su clausura ε.
inline std::set<std::string> move(const Nfa& n, const std::set<std::string>& current, char a) {
    std::set<std::string> next;
    for (const std::string& q : current) {
        auto it = n.delta.find({q, a});
        if (it != n.delta.end()) {
            next.insert(it->second.begin(), it->second.end());
        }
    }
    return eps_closure(n, next);
}

// El nombre del estado del DFA que corresponde a un conjunto de estados del NFA: {q0,q2}.
inline std::string set_name(const std::set<std::string>& subset) {
    std::string name = "{";
    for (const std::string& q : subset) {
        name += (name.size() > 1 ? "," : "") + q;
    }
    return name + "}";
}

// Construcción de subconjuntos. Con all_subsets = false genera solo los subconjuntos
// alcanzables desde la clausura ε de {q0}; con true, los 2^|Q|, como dice el teorema.
inline Dfa subset_construction(const Nfa& n, bool all_subsets = false) {
    Dfa d;
    d.alphabet = n.alphabet;
    std::set<std::string> first = eps_closure(n, {n.start});
    d.start = set_name(first);
    std::vector<std::set<std::string>> subsets;
    if (all_subsets) {
        if (n.states.size() > 20) {
            throw std::runtime_error("demasiados estados para generar todos los subconjuntos");
        }
        for (std::size_t mask = 0; mask < (std::size_t{1} << n.states.size()); mask++) {
            std::set<std::string> subset;
            for (std::size_t i = 0; i < n.states.size(); i++) {
                if ((mask >> i) & 1) {
                    subset.insert(n.states[i]);
                }
            }
            subsets.push_back(subset);
        }
    } else {
        std::set<std::set<std::string>> seen = {first};
        subsets.push_back(first);
        for (std::size_t i = 0; i < subsets.size(); i++) {
            for (char a : n.alphabet) {
                std::set<std::string> next = move(n, subsets[i], a);
                if (seen.insert(next).second) {
                    subsets.push_back(next);
                }
            }
        }
    }
    for (const std::set<std::string>& subset : subsets) {
        std::string name = set_name(subset);
        d.states.push_back(name);
        for (const std::string& q : subset) {
            if (n.accept.count(q) > 0) {
                d.accept.insert(name);
                break;
            }
        }
        for (char a : n.alphabet) {
            d.delta[{name, a}] = set_name(move(n, subset, a));
        }
    }
    check_dfa(d);
    return d;
}

#endif
tm.hDescargar tm.h
// Máquina de Turing determinista de una cinta, M = (Q, Σ, Γ, δ, q0, q_accept, q_reject), en el
// formato .tm de code/formats.md, y un simulador que la recibe como dato.
//
// El simulador es la máquina universal de la clase escrita en C++: no sabe nada de ninguna
// máquina en particular, y lo único que hace es aplicar δ un paso por vez. Avanza de a un paso
// para poder cortarlo con un límite y para poder alternar dos simulaciones.
#ifndef TM_H
#define TM_H

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

const char BLANK = '_';

// δ(q, a) = (r, b, L o R).
struct Action {
    std::string next;
    char write = BLANK;
    char move = 'R';
};

struct Tm {
    std::vector<std::string> states;                       // Q
    std::vector<char> alphabet;                            // Σ
    std::vector<char> tape;                                // Γ, que contiene a Σ y al blanco
    std::map<std::pair<std::string, char>, Action> delta;  // δ; lo que falta lleva a reject
    std::string start;                                     // q0
    std::string accept;                                    // q_accept
    std::string reject;                                    // q_reject
};

inline Tm read_tm(std::istream& in) {
    int number = 0;
    auto fail = [&number](const std::string& message) {
        throw std::runtime_error("línea " + std::to_string(number) + ": " + message);
    };
    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;
            }
            std::istringstream text(line);
            words.clear();
            std::string word;
            while (text >> word) {
                words.push_back(word);
            }
            if (!words.empty()) {
                return true;
            }
        }
        return false;
    };
    auto field = [&next_line, &fail](const std::string& name) {
        std::vector<std::string> words;
        if (!next_line(words) || words[0] != name + ":") {
            fail("se esperaba el campo " + name + ":");
        }
        words.erase(words.begin());
        return words;
    };
    auto symbols = [&fail](const std::vector<std::string>& words) {
        std::vector<char> result;
        for (const std::string& word : words) {
            if (word.size() != 1 || word[0] == '#') {
                fail("un símbolo es un solo carácter distinto de #: " + word);
            }
            result.push_back(word[0]);
        }
        return result;
    };
    auto one = [&fail](const std::vector<std::string>& words, const std::string& name) {
        if (words.size() != 1) {
            fail(name + ": lleva exactamente un estado");
        }
        return words[0];
    };

    Tm m;
    m.states = field("states");
    m.alphabet = symbols(field("alphabet"));
    m.tape = symbols(field("tape"));
    m.start = one(field("start"), "start");
    m.accept = one(field("accept"), "accept");
    m.reject = one(field("reject"), "reject");
    if (!field("delta").empty()) {
        fail("después de delta: las transiciones van una por línea");
    }
    std::set<std::string> q(m.states.begin(), m.states.end());
    std::set<char> gamma(m.tape.begin(), m.tape.end());
    if (gamma.count(BLANK) == 0) {
        fail("tape: debe contener el blanco _");
    }
    for (char a : m.alphabet) {
        if (gamma.count(a) == 0 || a == BLANK) {
            fail("alphabet: debe estar contenido en tape y no tener el blanco");
        }
    }
    if (q.count(m.start) == 0 || q.count(m.accept) == 0 || q.count(m.reject) == 0 || m.accept == m.reject) {
        fail("start, accept y reject deben ser estados, y accept distinto de reject");
    }
    std::vector<std::string> words;
    while (next_line(words)) {
        // estado lee -> destino escribe movimiento
        if (words.size() != 6 || words[2] != "->" || words[1].size() != 1 || words[4].size() != 1 ||
            (words[5] != "L" && words[5] != "R")) {
            fail("una transición se escribe: estado lee -> destino escribe L|R");
        }
        if (q.count(words[0]) == 0 || q.count(words[3]) == 0) {
            fail("estado desconocido en la transición");
        }
        if (gamma.count(words[1][0]) == 0 || gamma.count(words[4][0]) == 0) {
            fail("símbolo que no está en tape");
        }
        if (words[0] == m.accept || words[0] == m.reject) {
            fail("accept y reject no tienen transiciones de salida");
        }
        std::pair<std::string, char> key = {words[0], words[1][0]};
        if (m.delta.count(key) > 0) {
            fail("transición repetida: este simulador es para máquinas deterministas");
        }
        m.delta[key] = {words[3], words[4][0], words[5][0]};
    }
    return m;
}

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

// La descripción ⟨M⟩: la máquina escrita como una cadena, en el mismo formato .tm.
inline std::string encode(const Tm& m) {
    std::ostringstream out;
    out << "states:";
    for (const std::string& state : m.states) {
        out << ' ' << state;
    }
    out << "\nalphabet:";
    for (char a : m.alphabet) {
        out << ' ' << a;
    }
    out << "\ntape:";
    for (char a : m.tape) {
        out << ' ' << a;
    }
    out << "\nstart: " << m.start << "\naccept: " << m.accept << "\nreject: " << m.reject << "\ndelta:\n";
    for (const auto& [key, action] : m.delta) {
        out << key.first << ' ' << key.second << " -> " << action.next << ' ' << action.write << ' '
            << action.move << '\n';
    }
    return out.str();
}

// ------------------------------------------------------------
// Simular
// ------------------------------------------------------------

// Una configuración: estado, contenido de la cinta y posición del cabezal.
struct Config {
    std::string state;
    std::string tape;      // las celdas usadas; a su derecha todo es blanco
    std::size_t head = 0;
};

enum class Status { Running, Accepted, Rejected };

inline Config initial_config(const Tm& m, const std::string& w) {
    return {m.start, w.empty() ? std::string(1, BLANK) : w, 0};
}

inline Status status(const Tm& m, const Config& c) {
    if (c.state == m.accept) {
        return Status::Accepted;
    }
    return c.state == m.reject ? Status::Rejected : Status::Running;
}

// Un paso: aplica δ a la configuración. No hace nada si la máquina ya se detuvo.
inline void step(const Tm& m, Config& c) {
    if (status(m, c) != Status::Running) {
        return;
    }
    auto it = m.delta.find({c.state, c.tape[c.head]});
    if (it == m.delta.end()) {
        c.state = m.reject;  // un par sin transición lleva a reject
        return;
    }
    c.tape[c.head] = it->second.write;
    c.state = it->second.next;
    if (it->second.move == 'R') {
        c.head++;
        if (c.head == c.tape.size()) {
            c.tape.push_back(BLANK);
        }
    } else if (c.head > 0) {
        c.head--;  // en la primera celda, L deja el cabezal donde está
    }
}

// La configuración escrita como u q v.
inline std::string show_config(const Config& c) {
    std::string tape = c.tape;
    while (tape.size() > c.head + 1 && tape.back() == BLANK) {
        tape.pop_back();
    }
    return tape.substr(0, c.head) + " " + c.state + " " + tape.substr(c.head);
}

struct Outcome {
    Status status = Status::Running;  // Running: no se detuvo dentro del límite
    long steps = 0;
};

// Simula M con w durante a lo sumo `limit` pasos. Si la máquina se detiene antes, dice cómo.
// Si no, devuelve Running: con eso NO se sabe si M se detendría con más pasos.
inline Outcome simulate(const Tm& m, const std::string& w, long limit) {
    Config c = initial_config(m, w);
    Outcome result;
    while (status(m, c) == Status::Running && result.steps < limit) {
        step(m, c);
        result.steps++;
    }
    result.status = status(m, c);
    return result;
}

// Corre dos máquinas con la misma entrada, alternando un paso de cada una, hasta que alguna
// acepte. Devuelve 1 o 2 según cuál aceptó, o 0 si ninguna lo hizo en `limit` rondas.
// Es la máquina de la demostración "L y su complemento reconocibles implica L decidible".
struct Alternation {
    int winner = 0;
    long rounds = 0;
};

inline Alternation alternate(const Tm& m1, const Tm& m2, const std::string& w, long limit) {
    Config c1 = initial_config(m1, w);
    Config c2 = initial_config(m2, w);
    Alternation result;
    while (true) {
        if (status(m1, c1) == Status::Accepted) {
            result.winner = 1;
            return result;
        }
        if (status(m2, c2) == Status::Accepted) {
            result.winner = 2;
            return result;
        }
        if (result.rounds == limit) {
            return result;
        }
        step(m1, c1);
        step(m2, c2);
        result.rounds++;
    }
}

#endif
universal.cppDescargar universal.cpp
// La máquina universal como programa. Uso: universal M.tm CADENA [PASOS] [--traza]
// Recibe una máquina de Turing como dato y la simula con la cadena, a lo sumo PASOS pasos
// (1000 si no se indica). Tiene tres respuestas: acepta, rechaza, o no se detuvo en N pasos.
// La tercera no dice nada sobre lo que pasaría con más pasos. La cadena vacía se pasa como ''.
#include <cstdlib>
#include <iostream>
#include <stdexcept>
#include <string>

#include "tm.h"

int main(int argc, char** argv) {
    bool trace = argc >= 4 && std::string(argv[argc - 1]) == "--traza";
    if (trace) {
        argc--;
    }
    if (argc != 3 && argc != 4) {
        std::cerr << "uso: universal M.tm CADENA [PASOS] [--traza]\n";
        return 2;
    }
    try {
        Tm m = load_tm(argv[1]);
        std::string w = argv[2];
        long limit = argc == 4 ? std::atol(argv[3]) : 1000;
        std::cout << "⟨M⟩ = " << argv[1] << ": " << m.states.size() << " estados, " << m.delta.size()
                  << " transiciones, " << encode(m).size() << " caracteres\n";
        std::cout << "w = " << (w.empty() ? "ε" : w) << '\n';
        Config c = initial_config(m, w);
        long steps = 0;
        if (trace) {
            std::cout << "  " << show_config(c) << '\n';
        }
        while (status(m, c) == Status::Running && steps < limit) {
            step(m, c);
            steps++;
            if (trace) {
                std::cout << "  " << show_config(c) << '\n';
            }
        }
        if (status(m, c) == Status::Accepted) {
            std::cout << "M acepta w después de " << steps << " pasos\n";
        } else if (status(m, c) == Status::Rejected) {
            std::cout << "M rechaza w después de " << steps << " pasos\n";
        } else {
            std::cout << "M no se detuvo en " << limit << " pasos\n";
        }
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
machines/anbn_chomsky.cfgDescargar machines/anbn_chomsky.cfg
# { a^n b^n : n >= 0 }, en forma normal de Chomsky.
# S0 es la variable inicial y no aparece a la derecha de ninguna regla.
variables: S0 S T A B
terminals: a b
start: S0
rules:
S0 -> A T | A B | eps
S -> A T | A B
T -> S B
A -> a
B -> b
machines/contains_101.dfaDescargar machines/contains_101.dfa
# Cadenas binarias que contienen 101 como subcadena.
# q0, q1, q2: todavía no apareció 101, y lo leído termina con 0, 1 o 2 símbolos de 101 ya avanzados.
# q3: ya apareció 101.
states: q0 q1 q2 q3
alphabet: 0 1
start: q0
accept: q3
delta:
q0 0 q0
q0 1 q1
q1 0 q2
q1 1 q1
q2 0 q0
q2 1 q3
q3 0 q3
q3 1 q3
machines/ends_01_history.dfaDescargar machines/ends_01_history.dfa
# Cadenas binarias que terminan en 01, recordando los dos últimos símbolos leídos.
# e: no se leyó nada. s0, s1: se leyó un solo símbolo. s00, s01, s10, s11: los dos últimos.
states: e s0 s1 s00 s01 s10 s11
alphabet: 0 1
start: e
accept: s01
delta:
e 0 s0
e 1 s1
s0 0 s00
s0 1 s01
s1 0 s10
s1 1 s11
s00 0 s00
s00 1 s01
s01 0 s10
s01 1 s11
s10 0 s00
s10 1 s01
s11 0 s10
s11 1 s11
machines/ends_01_wrong.dfaDescargar machines/ends_01_wrong.dfa
# Un intento equivocado de "termina en 01": desde q2, con 0, vuelve a q0 y olvida ese 0.
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 q0
q2 1 q0
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/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/has_one.tmDescargar machines/has_one.tm
# Decide { w : w contiene un 1 }: avanza a la derecha hasta ver un 1 o el primer blanco.
states: scan q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: scan
accept: q_accept
reject: q_reject
delta:
scan 0 -> scan 0 R
scan 1 -> q_accept 1 R
scan _ -> q_reject _ R
machines/no_base_case.cfgDescargar machines/no_base_case.cfg
# Una gramática con reglas pero sin caso base para S: toda derivación desde S sigue teniendo
# una S o una C, así que no genera ninguna cadena. A y B sí generan, pero eso no alcanza.
variables: S A B C
terminals: a b
start: S
rules:
S -> A S B | C A
A -> a | a A
B -> b
C -> C b | S a
machines/parens.cfgDescargar machines/parens.cfg
# Paréntesis balanceados.
variables: S
terminals: ( )
start: S
rules:
S -> ( S ) S | eps
machines/search_end.tmDescargar machines/search_end.tm
# Reconoce { w : w no contiene ningún 1 }, pero no lo decide: acepta si llega al primer blanco
# sin ver un 1. Si ve un 1, pasa a un estado del que no sale y sigue a la derecha para siempre.
states: scan lost q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: scan
accept: q_accept
reject: q_reject
delta:
scan 0 -> scan 0 R
scan _ -> q_accept _ R
scan 1 -> lost 1 R
lost 0 -> lost 0 R
lost 1 -> lost 1 R
lost _ -> lost _ R
machines/search_one.tmDescargar machines/search_one.tm
# Reconoce { w : w contiene un 1 }, pero no lo decide: busca un 1 hacia la derecha sin
# detenerse en los blancos. Si w no tiene ningún 1, no se detiene nunca.
states: scan q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: scan
accept: q_accept
reject: q_reject
delta:
scan 0 -> scan 0 R
scan 1 -> q_accept 1 R
scan _ -> scan _ R
machines/third_from_end.nfaDescargar machines/third_from_end.nfa
# El tercer símbolo desde el final es 1.
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/unreachable_accept.dfaDescargar machines/unreachable_accept.dfa
# Tiene un estado de aceptación, pero no se llega a él desde el inicial: su lenguaje es vacío.
states: a b c d
alphabet: 0 1
start: a
accept: d
delta:
a 0 b
a 1 a
b 0 b
b 1 a
c 0 d
c 1 a
d 0 d
d 1 c
machines/zeros_ones.tmDescargar machines/zeros_ones.tm
# Decide { 0^n 1^n : n >= 0 }.
states: q0 q1 q2 q3 q_accept q_reject
alphabet: 0 1
tape: 0 1 X Y _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q1 X R
q0 Y -> q3 Y R
q0 _ -> q_accept _ R
q1 0 -> q1 0 R
q1 Y -> q1 Y R
q1 1 -> q2 Y L
q2 0 -> q2 0 L
q2 Y -> q2 Y L
q2 X -> q0 X R
q3 Y -> q3 Y R
q3 _ -> q_accept _ R

Pruebas

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

test_cfg.cppDescargar test_cfg.cpp
// Pruebas de los procedimientos de decisión sobre gramáticas: E_CFG y A_CFG.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <random>
#include <set>
#include <stdexcept>
#include <string>
#include <vector>

#include "cfg.h"

static std::vector<std::string> all_strings(const std::vector<char>& alphabet, std::size_t max_len) {
    std::vector<std::string> result = {""};
    std::size_t begin = 0;
    for (std::size_t len = 1; len <= max_len; len++) {
        std::size_t end = result.size();
        for (std::size_t i = begin; i < end; i++) {
            for (char a : alphabet) {
                result.push_back(result[i] + a);
            }
        }
        begin = end;
    }
    return result;
}

static bool is_anbn(const std::string& w) {
    std::size_t n = w.size() / 2;
    return w.size() % 2 == 0 && w == std::string(n, 'a') + std::string(n, 'b');
}

// E_CFG: las marcas de los apuntes.
static void test_marking() {
    Cfg parens = load_cfg("machines/parens.cfg");
    assert(generating(parens) == (std::set<std::string>{"S"}));
    assert(!is_empty(parens));

    Cfg anbn = load_cfg("machines/anbn_chomsky.cfg");
    std::vector<std::vector<std::string>> rounds = generating_rounds(anbn);
    assert(rounds.size() == 3);
    assert(rounds[0] == (std::vector<std::string>{"S0", "A", "B"}));
    assert(rounds[1] == (std::vector<std::string>{"S"}));
    assert(rounds[2] == (std::vector<std::string>{"T"}));
    assert(!is_empty(anbn));

    // Tiene reglas y dos variables que generan, pero S no genera nada.
    Cfg none = load_cfg("machines/no_base_case.cfg");
    assert(none.rules.size() == 7);
    assert(generating(none) == (std::set<std::string>{"A", "B"}));
    assert(is_empty(none));

    // Con una regla más para C, S pasa a generar: C → b, y entonces S → C A.
    Cfg fixed = none;
    fixed.rules.push_back({"C", {"b"}});
    assert(generating(fixed) == (std::set<std::string>{"S", "A", "B", "C"}));
    assert(!is_empty(fixed));
}

// A_CFG: las derivaciones de 2n − 1 pasos y CYK deciden lo mismo.
static void test_membership() {
    Cfg anbn = load_cfg("machines/anbn_chomsky.cfg");
    assert(is_chomsky(anbn));
    assert(cyk(anbn, "aabb") && !cyk(anbn, "abab") && cyk(anbn, "") && cyk(anbn, "ab"));
    int in_language = 0;
    for (const std::string& w : all_strings({'a', 'b'}, 10)) {
        bool expected = is_anbn(w);
        assert(cyk(anbn, w) == expected);
        assert(derives_bounded(anbn, w) == expected);
        if (expected && !w.empty()) {
            in_language++;
            // Exactamente 2n − 1 pasos: con uno menos no se llega.
            assert(derives_within(anbn, {anbn.start}, w, 2 * w.size() - 1));
            assert(!derives_within(anbn, {anbn.start}, w, 2 * w.size() - 2));
        }
    }
    assert(in_language == 5);

    // La de los paréntesis no está en forma normal de Chomsky: estos algoritmos no la aceptan.
    Cfg parens = load_cfg("machines/parens.cfg");
    assert(!is_chomsky(parens));
    bool failed = false;
    try {
        cyk(parens, "()");
    } catch (const std::runtime_error&) {
        failed = true;
    }
    assert(failed);
}

// Gramáticas al azar en forma normal de Chomsky, con variables S, A, B. El algoritmo de marcas
// dice "no vacío" si y solo si CYK encuentra alguna cadena. Si L(G) no es vacío, tiene una cadena
// con un árbol de derivación sin variables repetidas en ningún camino: a lo sumo |V| = 3
// variables por camino, y entonces a lo sumo 2^2 = 4 hojas.
static void test_emptiness_random() {
    std::mt19937 rng(4129);
    const std::vector<std::string> inner = {"A", "B"};
    int empty = 0;
    for (int round = 0; round < 500; round++) {
        Cfg g;
        g.variables = {"S", "A", "B"};
        g.terminals = {'a', 'b'};
        g.start = "S";
        int count = 1 + static_cast<int>(rng() % 6);
        for (int i = 0; i < count; i++) {
            std::string head = g.variables[rng() % 3];
            unsigned kind = rng() % 8;
            if (kind == 0) {
                std::string terminal(1, g.terminals[rng() % 2]);
                g.rules.push_back({head, {terminal}});
            } else if (kind == 1 && head == "S") {
                g.rules.push_back({head, {}});
            } else {
                std::string left = inner[rng() % 2];
                std::string right = inner[rng() % 2];
                g.rules.push_back({head, {left, right}});
            }
        }
        assert(is_chomsky(g));
        bool found = false;
        for (const std::string& w : all_strings(g.terminals, 4)) {
            if (cyk(g, w)) {
                found = true;
                break;
            }
        }
        assert(is_empty(g) == !found);
        empty += is_empty(g) ? 1 : 0;
    }
    assert(empty > 50 && empty < 450);
}

int main() {
    test_marking();
    test_membership();
    test_emptiness_random();
    std::printf("test_cfg: ok (E_CFG, A_CFG; 500 gramáticas al azar)\n");
}
test_dfa.cppDescargar test_dfa.cpp
// Pruebas de los procedimientos de decisión sobre DFA y NFA: A_DFA, A_NFA, E_DFA y EQ_DFA.
// Comprueban lo que los apuntes afirman sobre los autómatas de machines/ y los del laboratorio.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <optional>
#include <random>
#include <string>
#include <vector>

#include "decide.h"
#include "dfa.h"
#include "minimize.h"
#include "nfa.h"

// Todas las cadenas sobre el alfabeto de longitud a lo sumo max_len, las más cortas primero.
static std::vector<std::string> all_strings(const std::vector<char>& alphabet, std::size_t max_len) {
    std::vector<std::string> result = {""};
    std::size_t begin = 0;
    for (std::size_t len = 1; len <= max_len; len++) {
        std::size_t end = result.size();
        for (std::size_t i = begin; i < end; i++) {
            for (char a : alphabet) {
                result.push_back(result[i] + a);
            }
        }
        begin = end;
    }
    return result;
}

static const std::vector<char> BINARY = {'0', '1'};

static bool ends_in_01(const std::string& w) {
    return w.size() >= 2 && w.substr(w.size() - 2) == "01";
}

static bool kth_from_end_is_1(const std::string& w, std::size_t k) {
    return w.size() >= k && w[w.size() - k] == '1';
}

// A_DFA y A_NFA: simular, y convertir y simular.
static void test_acceptance() {
    Dfa ends = load_dfa("machines/ends_01.dfa");
    assert(run(ends, "0101") == (std::vector<std::string>{"q0", "q1", "q2", "q1", "q2"}));
    assert(accepts(ends, "0101") && !accepts(ends, ""));
    for (const std::string& w : all_strings(BINARY, 12)) {
        assert(run(ends, w).size() == w.size() + 1);  // |w| pasos, siempre termina
        assert(accepts(ends, w) == ends_in_01(w));
    }

    Nfa third = load_nfa("machines/third_from_end.nfa");
    Dfa d = subset_construction(third);
    assert(third.states.size() == 4 && d.states.size() == 8);
    assert(subset_construction(third, true).states.size() == 16);
    assert(run(d, "0100") == (std::vector<std::string>{"{q0}", "{q0}", "{q0,q1}", "{q0,q2}", "{q0,q3}"}));
    for (const std::string& w : all_strings(BINARY, 12)) {
        assert(accepts(d, w) == kth_from_end_is_1(w, 3));
    }
    assert(accepts(d, "0100") && !accepts(d, "0010"));
}

// E_DFA: alcanzabilidad.
static void test_emptiness() {
    Dfa ends = load_dfa("machines/ends_01.dfa");
    assert(!is_empty(ends));
    assert(shortest_accepted(ends) == std::optional<std::string>("01"));

    // Tiene un estado de aceptación, pero inalcanzable.
    Dfa unreachable = load_dfa("machines/unreachable_accept.dfa");
    assert(unreachable.accept.size() == 1 && reachable(unreachable).size() == 2);
    assert(is_empty(unreachable));
    for (const std::string& w : all_strings(BINARY, 12)) {
        assert(!accepts(unreachable, w));
    }

    // F = ∅: vacío. F = Q: no vacío, y la cadena más corta es ε.
    Dfa none = ends;
    none.accept.clear();
    assert(is_empty(none));
    Dfa everything = complement(none);
    assert(shortest_accepted(everything) == std::optional<std::string>(""));

    // L(M) = ∅ si y solo si el complemento acepta todo... y un lenguaje y su complemento no son vacíos a la vez.
    assert(!is_empty(complement(ends)));
    assert(shortest_accepted(complement(ends)) == std::optional<std::string>(""));
}

// EQ_DFA con los autómatas de los apuntes.
static void test_equivalence_of_notes() {
    Dfa ends = load_dfa("machines/ends_01.dfa");
    Dfa history = load_dfa("machines/ends_01_history.dfa");
    Dfa wrong = load_dfa("machines/ends_01_wrong.dfa");
    Dfa even = load_dfa("machines/even_ones.dfa");

    // El de 3 estados y el de 7 son equivalentes: 7 pares alcanzables de 21.
    Comparison same = compare(ends, history);
    assert(same.equivalent && same.witness.empty());
    assert(same.pairs.size() == 7 && reachable_pairs(ends, history) == 7);
    Dfa c = symmetric_difference(ends, history);
    assert(c.states.size() == 21 && c.accept.size() == 8 && reachable(c).size() == 7);
    assert(is_empty(c));
    for (const std::string& w : all_strings(BINARY, 12)) {
        assert(accepts(ends, w) == accepts(history, w));
    }

    // El equivocado se separa con 0101, y con ninguna cadena más corta.
    Comparison differ = compare(ends, wrong);
    assert(!differ.equivalent && differ.witness == "0101" && differ.pairs.size() == 5);
    assert(differ.pairs.back() == (std::pair<std::string, std::string>{"q2", "q0"}));
    assert(accepts(ends, "0101") && !accepts(wrong, "0101"));
    for (const std::string& w : all_strings(BINARY, 3)) {
        assert(accepts(ends, w) == accepts(wrong, w));
    }
    Dfa c2 = symmetric_difference(ends, wrong);
    assert(c2.states.size() == 9 && c2.accept.size() == 4 && reachable(c2).size() == 5);
    assert(shortest_accepted(c2) == std::optional<std::string>("0101"));
    // L(C) es la diferencia simétrica: C acepta w si y solo si exactamente uno de los dos la acepta.
    for (const std::string& w : all_strings(BINARY, 12)) {
        assert(accepts(c2, w) == (accepts(ends, w) != accepts(wrong, w)));
    }

    // Dos lenguajes que no tienen nada que ver: los separa ε.
    Comparison other = compare(ends, even);
    assert(!other.equivalent && other.witness.empty() && other.pairs.size() == 1);

    // Todo DFA es equivalente a sí mismo y a su versión mínima; no a su complemento.
    for (const Dfa& m : {ends, history, wrong, even}) {
        assert(compare(m, m).equivalent);
        assert(compare(m, minimize(m)).equivalent);
        assert(!compare(m, complement(m)).equivalent);
    }
    assert(minimize(history).states.size() == 3);
}

// Un DFA al azar con n estados sobre {0, 1}.
static Dfa random_dfa(std::mt19937& rng, std::size_t n, const std::string& prefix) {
    Dfa m;
    m.alphabet = BINARY;
    for (std::size_t i = 0; i < n; i++) {
        m.states.push_back(prefix + std::to_string(i));
    }
    m.start = m.states[0];
    for (const std::string& q : m.states) {
        if (rng() % 3 == 0) {
            m.accept.insert(q);
        }
        for (char a : m.alphabet) {
            m.delta[{q, a}] = m.states[rng() % n];
        }
    }
    return m;
}

// Las dos maneras de decidir EQ_DFA coinciden, y la cadena que devuelven es de las más cortas.
// Si dos DFA son distintos, alguna cadena de longitud menor que |QA| · |QB| los separa: basta
// probar esas para comparar con la fuerza bruta.
static void test_equivalence_random() {
    std::mt19937 rng(90210);
    int different = 0;
    for (int round = 0; round < 400; round++) {
        std::size_t na = 1 + rng() % 3;
        std::size_t nb = 1 + rng() % 3;
        Dfa a = random_dfa(rng, na, "p");
        Dfa b = (round % 5 == 0) ? minimize(a, "m") : random_dfa(rng, nb, "r");
        nb = b.states.size();
        Comparison result = compare(a, b);
        Dfa c = symmetric_difference(a, b);
        std::optional<std::string> from_product = shortest_accepted(c);
        assert(result.equivalent == !from_product.has_value());
        assert(result.pairs.size() <= na * nb);

        std::optional<std::string> brute;
        for (const std::string& w : all_strings(BINARY, na * nb - 1)) {
            if (accepts(a, w) != accepts(b, w)) {
                brute = w;
                break;  // all_strings va de las más cortas a las más largas
            }
        }
        assert(result.equivalent == !brute.has_value());
        if (!result.equivalent) {
            different++;
            assert(accepts(a, result.witness) != accepts(b, result.witness));
            assert(result.witness.size() == brute->size());
            assert(result.witness.size() == from_product->size());
            assert(result.witness.size() < na * nb);
            assert(result.witness.size() + 2 <= na + nb);  // la cota fina del ejercicio 5
        }
    }
    assert(different > 100 && different < 400);
}

// Los autómatas de lab/dfa_equiv/machines, que escribe make_kth.
static void test_kth_machines() {
    const std::string dir = "lab/dfa_equiv/machines/";
    Nfa n = load_nfa(dir + "kth6.nfa");
    Dfa subsets = load_dfa(dir + "kth6_subsets.dfa");
    Dfa all = load_dfa(dir + "kth6_all.dfa");
    Dfa history = load_dfa(dir + "kth6_history.dfa");
    Dfa minimal = load_dfa(dir + "kth6_min.dfa");
    Dfa wrong = load_dfa(dir + "kth6_wrong.dfa");

    assert(n.states.size() == 7);
    assert(subsets.states.size() == 64 && reachable(subsets).size() == 64);
    assert(all.states.size() == 128 && reachable(all).size() == 64);
    assert(history.states.size() == 127 && reachable(history).size() == 127);
    assert(minimal.states.size() == 64);
    assert(wrong.states.size() == 63);
    // Los archivos son lo que la construcción produce.
    assert(subset_construction(n).delta == subsets.delta);
    // El de subconjuntos ya es mínimo: minimizar no le quita nada.
    assert(minimize(subsets).states.size() == 64 && minimize(all).states.size() == 64);
    assert(minimize(history).states.size() == 64);

    for (const std::string& w : all_strings(BINARY, 12)) {
        bool expected = kth_from_end_is_1(w, 6);
        assert(accepts(subsets, w) == expected && accepts(all, w) == expected);
        assert(accepts(history, w) == expected && accepts(minimal, w) == expected);
    }
    assert(compare(subsets, minimal).equivalent && compare(subsets, minimal).pairs.size() == 64);
    assert(compare(all, history).equivalent && compare(all, history).pairs.size() == 127);
    assert(compare(history, minimal).equivalent && compare(all, minimal).equivalent);

    Comparison broken = compare(minimal, wrong);
    assert(!broken.equivalent && broken.witness == "1100000");
    for (const std::string& w : all_strings(BINARY, 6)) {
        assert(accepts(minimal, w) == accepts(wrong, w));
    }
}

int main() {
    test_acceptance();
    test_emptiness();
    test_equivalence_of_notes();
    test_equivalence_random();
    test_kth_machines();
    std::printf("test_dfa: ok (A_DFA, A_NFA, E_DFA, EQ_DFA; 400 pares de DFA al azar)\n");
}
test_tm.cppDescargar test_tm.cpp
// Pruebas de la sesión B: el simulador que recibe la máquina como dato, lo que dice y lo que
// no dice un límite de pasos, y las dos máquinas que se alternan.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <sstream>
#include <string>
#include <vector>

#include "tm.h"

static std::vector<std::string> all_strings(const std::vector<char>& alphabet, std::size_t max_len) {
    std::vector<std::string> result = {""};
    std::size_t begin = 0;
    for (std::size_t len = 1; len <= max_len; len++) {
        std::size_t end = result.size();
        for (std::size_t i = begin; i < end; i++) {
            for (char a : alphabet) {
                result.push_back(result[i] + a);
            }
        }
        begin = end;
    }
    return result;
}

static const std::vector<char> BINARY = {'0', '1'};

static bool is_0n1n(const std::string& w) {
    std::size_t n = w.size() / 2;
    return w.size() % 2 == 0 && w == std::string(n, '0') + std::string(n, '1');
}

static bool has_one(const std::string& w) {
    return w.find('1') != std::string::npos;
}

// Un decididor: se detiene con todas las entradas.
static void test_decider() {
    Tm m = load_tm("machines/zeros_ones.tm");
    Outcome traced = simulate(m, "0011", 1000);
    assert(traced.status == Status::Accepted && traced.steps == 13);
    for (const std::string& w : all_strings(BINARY, 10)) {
        Outcome result = simulate(m, w, 1000);
        assert(result.status != Status::Running);
        assert((result.status == Status::Accepted) == is_0n1n(w));
    }
    // El mismo cómputo cortado antes: "no se detuvo en 5 pasos" no dice que no se detenga.
    assert(simulate(m, "0011", 5).status == Status::Running);
    assert(simulate(m, "0011", 12).status == Status::Running);
    assert(simulate(m, "0011", 13).status == Status::Accepted);

    Tm scan = load_tm("machines/has_one.tm");
    for (const std::string& w : all_strings(BINARY, 10)) {
        Outcome result = simulate(scan, w, 1000);
        assert(result.status != Status::Running && result.steps <= static_cast<long>(w.size()) + 1);
        assert((result.status == Status::Accepted) == has_one(w));
    }
    assert(simulate(scan, "000", 1000).steps == 4);
}

// Un reconocedor que no decide: mismo lenguaje que has_one.tm, pero no se detiene sin un 1.
static void test_recognizer() {
    Tm m = load_tm("machines/search_one.tm");
    for (const std::string& w : all_strings(BINARY, 10)) {
        Outcome result = simulate(m, w, 20000);
        if (has_one(w)) {
            assert(result.status == Status::Accepted && result.steps <= static_cast<long>(w.size()));
        } else {
            assert(result.status == Status::Running && result.steps == 20000);
        }
    }
    assert(simulate(m, "0001", 1000).steps == 4);
    // Con 000 nunca se detiene, y aquí se ve por qué: después de t pasos está en el estado
    // scan, con el cabezal en la celda t, y de ahí en adelante solo lee blancos.
    Config c = initial_config(m, "000");
    for (std::size_t t = 1; t <= 5000; t++) {
        step(m, c);
        assert(c.state == "scan" && c.head == t);
        assert(t < 3 || c.tape[c.head] == BLANK);
    }
    for (long limit : {10L, 1000L, 100000L, 1000000L}) {
        assert(simulate(m, "000", limit).status == Status::Running);
    }
}

// La máquina es un dato: de la cadena ⟨M⟩ se recupera una máquina que hace lo mismo.
static void test_encoding() {
    for (const char* path : {"machines/zeros_ones.tm", "machines/has_one.tm", "machines/search_one.tm",
                             "machines/search_end.tm"}) {
        Tm m = load_tm(path);
        std::string description = encode(m);
        std::istringstream in(description);
        Tm again = read_tm(in);
        assert(encode(again) == description);
        for (const std::string& w : all_strings(BINARY, 8)) {
            Outcome a = simulate(m, w, 500);
            Outcome b = simulate(again, w, 500);
            assert(a.status == b.status && a.steps == b.steps);
        }
    }
    assert(encode(load_tm("machines/zeros_ones.tm")).size() == 296);
}

// Dos reconocedores, uno del lenguaje y otro del complemento, alternados: un decididor.
static void test_alternation() {
    Tm yes = load_tm("machines/search_one.tm");
    Tm no = load_tm("machines/search_end.tm");
    for (const std::string& w : all_strings(BINARY, 10)) {
        // Ninguna de las dos decide: cada una se queda corriendo con las cadenas de la otra.
        assert((simulate(yes, w, 200).status == Status::Accepted) == has_one(w));
        assert((simulate(no, w, 200).status == Status::Accepted) == !has_one(w));
        assert(simulate(has_one(w) ? no : yes, w, 200).status == Status::Running);
        // Alternadas, siempre termina, y en pocas rondas.
        Alternation result = alternate(yes, no, w, 10000);
        assert(result.winner == (has_one(w) ? 1 : 2));
        assert(result.rounds <= static_cast<long>(w.size()) + 1);
    }
    assert(alternate(yes, no, "0001", 10000).rounds == 4);
    assert(alternate(yes, no, "000", 10000).rounds == 4);
    // Si las dos máquinas no cubren todas las cadenas, la alternancia no termina.
    assert(alternate(yes, yes, "000", 10000).winner == 0);
}

int main() {
    test_decider();
    test_recognizer();
    test_encoding();
    test_alternation();
    std::printf("test_tm: ok (4 máquinas, 2047 cadenas cada una)\n");
}

Laboratorio

Archivos de partida del laboratorio de la semana.

lab/dfa_equiv/MakefileDescargar lab/dfa_equiv/Makefile
TIEMPO = 2
VERIFICADOR = verificador.cpp
include ../../../lab.mk
lab/dfa_equiv/README.mdDescargar lab/dfa_equiv/README.md
# ¿Son equivalentes dos DFA?

Dos autómatas finitos deterministas (DFA) pueden verse muy distintos y reconocer el mismo lenguaje: uno tiene
estados de más, el otro salió de una construcción automática y nadie lo dibujó. En la clase se demostró que
decidir si $L(A) = L(B)$ es posible: el lenguaje $\mathrm{EQ}_{\mathrm{DFA}}$ es decidible. Este laboratorio
convierte esa demostración en un programa que además, cuando los autómatas no son equivalentes, lo prueba con
una cadena: una de las más cortas que uno acepta y el otro rechaza.

## Entrada

Dos descripciones de DFA en el formato `.dfa` de [`code/formats.md`](../../../formats.md), separadas por una
línea que contiene solo `---`. El primero es $A$ y el segundo es $B$.

```text
# A: cadenas binarias que terminan 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
---
# B: un intento equivocado. Desde q2, con 0, vuelve a q0.
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 q0
q2 1 q0
```

- La primera descripción termina en la línea `---`, y la segunda donde termina la entrada.
- Una línea que empieza con `#` es un comentario. Puede haber comentarios en cualquier línea, también entre
  las transiciones y justo después de `---`.
- Puede haber líneas vacías antes de `delta:`. Después de `delta:` no hay líneas vacías.
- En cada descripción, `states:`, `alphabet:`, `start:`, `accept:` y `delta:` vienen en ese orden, y `accept:`
  puede no tener ningún estado. Después de `delta:` hay exactamente una línea `estado símbolo destino` por
  cada par de estado y símbolo, en cualquier orden.
- **Los dos autómatas tienen los mismos símbolos**, pero `alphabet:` puede listarlos en otro orden.
- **Los nombres de los estados son de cada autómata.** Que los dos tengan un estado `q0` no significa nada:
  son estados distintos.

## Salida

Si $L(A) = L(B)$, una línea:

```text
equivalentes
```

Si no, dos líneas: `distintos` y una cadena $w$ de **longitud mínima** entre las que están en exactamente uno
de los dos lenguajes.

```text
distintos
0101
```

La cadena vacía no se puede imprimir como una línea vacía, porque el juez no la vería. Si la cadena más corta
que separa a los autómatas es $\varepsilon$, se imprime `eps`, como en el resto de los formatos del curso:

```text
distintos
eps
```

Suele haber varias cadenas de longitud mínima, y cualquiera vale. El juez usa un verificador: comprueba que
su cadena solo usa símbolos del alfabeto, que uno de los autómatas la acepta y el otro no, y que tiene la
misma longitud que la respuesta de referencia. No compara el texto.

## Límites

- $1 \leq |Q_A|, |Q_B| \leq 50\,000$ y $1 \leq |\Sigma| \leq 14$. Cada autómata tiene a lo sumo 200 000
  transiciones.
- Un símbolo es un dígito o una letra de la `a` a la `d`. Así, `eps` nunca se confunde con una cadena de
  tres símbolos.
- El nombre de un estado tiene entre 1 y 30 caracteres visibles, sin espacios. No empieza con `#` ni con `-`,
  y no termina con `:`. Puede llevar llaves, comas y paréntesis, como `{q0,q1}`.
- **A lo sumo 200 000 pares $(p, q)$ son alcanzables** desde el par de estados iniciales, donde $p$ es un
  estado de $A$ y $q$ uno de $B$. El número total de pares, $|Q_A| \cdot |Q_B|$, puede llegar a
  2 500 000 000.
- La entrada siempre describe dos DFA válidos: no tienen que detectar errores.

## Ejemplo

Para la entrada de arriba la salida es `distintos` y `0101`. Con esa cadena, $A$ pasa por $q_0, q_1, q_2, q_1,
q_2$ y acepta. $B$ pasa por $q_0, q_1, q_2, q_0, q_0$ y rechaza: al volver a $q_0$ olvidó el $\mathtt{0}$ que
acababa de leer. Ninguna cadena de longitud 3 o menos los separa.

## Tiempo

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

## La idea

La demostración de la clase construye un tercer autómata $C$, con la construcción del producto: sus estados
son los pares $(p, q)$, y un par es de aceptación cuando exactamente uno de los dos estados lo es. Entonces
$C$ acepta justo las cadenas en las que $A$ y $B$ no coinciden, y $A$ y $B$ son equivalentes si y solo si
$L(C) = \emptyset$, cosa que se decide viendo si algún estado de aceptación de $C$ es alcanzable.

Como demostración está completa. Como programa tiene un problema: $C$ tiene $|Q_A| \cdot |Q_B|$ estados, y
casi siempre se llega a muy pocos. En el caso 16 los dos autómatas tienen 50 000 estados: el producto tendría
2 500 000 000 de pares, y desde el inicial se alcanzan 50 000. Construirlo entero no entra ni en el tiempo ni
en la memoria. Lo que hay que hacer es no construirlo:

1. Empezar en el par $(q_A, q_B)$ de los estados iniciales.
2. Buscar **en anchura**. De cada par $(p, q)$ que sale de la cola, y con cada símbolo $a$, se calcula el par
   $(\delta_A(p, a), \delta_B(q, a))$; si es nuevo, entra a la cola.
3. Si sale de la cola un par en el que un estado es de aceptación y el otro no, la respuesta es `distintos`.
   La cadena se reconstruye hacia atrás, guardando de cada par desde cuál se llegó y con qué símbolo.
4. Si la cola se vacía, la respuesta es `equivalentes`.

La búsqueda en anchura descubre los pares por distancia creciente desde el inicial, y la distancia de un par
es la longitud de la cadena más corta que lleva a él. Por eso el primer par "malo" que aparece da una cadena
de longitud mínima. Una búsqueda en profundidad también decide si son equivalentes, pero la cadena que
entrega puede ser mucho más larga, y el verificador la rechaza.

Otra idea que no sirve: probar todas las cadenas, de las más cortas a las más largas. Es correcta, porque si
los autómatas son distintos alguna cadena de longitud menor que $|Q_A| \cdot |Q_B|$ los separa, y entonces se
puede parar ahí. Pero con dos símbolos hay $2^n$ cadenas de longitud $n$: en el caso 02, con autómatas de 3 y
7 estados que sí son equivalentes, habría que probar todas las de longitud hasta 20 antes de responder.

## Cómo avanzar

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

Los dos casos más grandes no están guardados: `make test` los genera con los programas `casos/gen_NN.cpp`.
`solution.cpp` se escribe sin incluir los archivos de la carpeta de la semana: el juez compila ese único
archivo.

1. Lean los dos autómatas. Empiecen con `casos/01.in`. Lean por líneas, con `std::getline`, y fíjense en qué
   línea termina cada descripción. Guarden cada estado por su posición en la lista, y pasen los nombres a
   posiciones una sola vez, al leer: con 50 000 estados, buscar un nombre en una lista por cada transición es
   demasiado lento.
2. Respondan `equivalentes` o `distintos` con la búsqueda en anchura sobre los pares. Un par $(p, q)$ se
   puede guardar como el número $p \cdot |Q_B| + q$, que no entra en un `int`: usen `long long`. Para saber
   si un par ya se visitó sirve un `std::unordered_set` o un `std::set` de esos números. Un arreglo con una
   casilla por cada par posible es justo el producto completo que hay que evitar.
3. Agreguen la cadena. Antes de correr el juez, respondan a mano: ¿qué imprime su programa si un autómata
   acepta $\varepsilon$ y el otro no? ¿Y si los dos tienen `accept:` vacío?
4. Pasen los casos grandes, del 13 al 17. Si alguno da `TLE`, cuenten cuántos pares genera su programa y
   compárenlo con los 200 000 del enunciado.
5. Comprueben con su programa los autómatas de `machines/`, que reconocen todos "el sexto símbolo desde el
   final es $\mathtt{1}$":

   | Archivo | Qué es | Estados |
   |---|---|---|
   | `kth6.nfa` | El NFA de la semana 2 | 7 |
   | `kth6_subsets.dfa` | Su construcción de subconjuntos, solo con los subconjuntos alcanzables | 64 |
   | `kth6_all.dfa` | La construcción de subconjuntos con todos los subconjuntos | 128 |
   | `kth6_history.dfa` | Un DFA que recuerda los últimos símbolos leídos, con un estado por cada cadena de longitud a lo sumo 6 | 127 |
   | `kth6_min.dfa` | El DFA mínimo, como lo deja la minimización de la semana 4 | 64 |
   | `kth6_wrong.dfa` | El mínimo con dos estados fusionados por error | 63 |

   Para comparar dos archivos se arma la entrada con la línea `---` en medio:

   ```sh
   { cat machines/kth6_subsets.dfa; echo '---'; cat machines/kth6_min.dfa; } | build/solution
   ```

   Debe imprimir `equivalentes`. Comparen también `kth6_all.dfa` con `kth6_history.dfa`, y el DFA que su
   propio programa de la semana 2 produjo para $k = 6$ con el que dejó su minimizador de la semana 4. Después
   comparen `kth6_min.dfa` con `kth6_wrong.dfa`: ¿qué cadena imprime su programa, y por qué tiene 7 símbolos y
   no menos?

Los seis archivos los escribe el programa `make_kth` de la carpeta de la semana (`make kth`): arma el NFA,
le aplica la construcción de subconjuntos de las dos maneras, escribe el autómata que recuerda los últimos
símbolos, lo minimiza, y en el mínimo fusiona el estado al que se llega con `11` con el estado al que se
llega con `10`.

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

## Los casos

| Casos | Qué prueban |
|---|---|
| 01 a 03 | Los ejemplos de los apuntes: distintos con una cadena de 4 símbolos, equivalentes con 3 y 7 estados, y distintos con $\varepsilon$ |
| 04 a 06 | El lenguaje vacío de dos maneras (sin estados de aceptación, y con uno inalcanzable), el vacío contra uno que no lo es, y $\Sigma^*$ con un estado inalcanzable |
| 07 | Los mismos nombres en los dos autómatas, el alfabeto en otro orden, comentarios y transiciones desordenadas |
| 08 y 09 | Un solo símbolo: ciclos de 7 y 11 estados, en los que se alcanzan los 77 pares, y ciclos de 91 y 7 |
| 10 y 11 | Los autómatas de `machines/` |
| 12 | 14 símbolos y 200 estados |
| 13 | 2000 estados cada uno: el producto completo tiene 4 000 000 de pares y se alcanzan 2000 |
| 14 y 15 | 194 686 pares alcanzables; en el 15, muchas cadenas de longitud mínima |
| 16 | 50 000 estados cada uno, equivalentes |
| 17 | 40 000 y 50 000 estados; la cadena más corta que los separa tiene 39 999 símbolos |

## Para seguir

Opcional, sin casos en el juez.

- Con este programa y el complemento se decide también si $L(A) \subseteq L(B)$. ¿Qué pares hay que buscar?
- Cuenten los pares que visita su programa en el caso 14 y expliquen el número: ¿por qué son exactamente
  $311 \cdot 313 \cdot 2$?
- Hay un algoritmo que decide la equivalencia sin cola ni distancias, uniendo en una misma clase los estados
  que tendrían que ser equivalentes (Hopcroft y Karp, con la estructura de conjuntos disjuntos de
  Algoritmos). Es casi lineal, pero la cadena que encuentra no es de las más cortas. ¿Por qué?
lab/dfa_equiv/solution.cppDescargar lab/dfa_equiv/solution.cpp
// ¿Son equivalentes dos DFA? Lee dos autómatas separados por una línea --- y responde
// equivalentes, o distintos y una cadena más corta que uno acepta y el otro no.
#include <iostream>
#include <string>
#include <vector>

// Los cinco componentes de M = (Q, Σ, δ, q0, F), con los nombres del formato.
// Los tipos son una propuesta: cada estado y cada símbolo se guarda por su posición en la
// lista, para que seguir una transición no dependa de buscar un nombre. Pueden cambiarlos.
struct Dfa {
    std::vector<std::string> states;      // Q: los nombres, en el orden de la entrada
    std::vector<char> alphabet;           // Σ
    std::vector<std::vector<int>> delta;  // δ: delta[i][j] es el estado al que va states[i] con alphabet[j]
    int start = 0;                        // q0, como posición en states
    std::vector<bool> accept;             // F: accept[i] dice si states[i] es de aceptación
};

// Por hacer: leer una descripción línea por línea con std::getline, hasta la línea --- o
// hasta el final de la entrada. Las líneas que empiezan con # son comentarios.
static Dfa read_dfa(std::istream& in) {
    Dfa m;
    std::string line;
    while (std::getline(in, line)) {
        if (line == "---") {
            break;
        }
    }
    return m;
}

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

    Dfa a = read_dfa(std::cin);
    Dfa b = read_dfa(std::cin);
    // Por hacer: buscar en anchura desde el par (a.start, b.start), generando solo los pares
    // a los que se llega. Si aparece un par en el que un estado es de aceptación y el otro no,
    // imprimir "distintos" y la cadena que llevó hasta él (eps si es la vacía).
    // Si la búsqueda termina sin encontrarlo, imprimir "equivalentes".
    // Este esqueleto no imprime nada, así que el juez da WA en todos los casos.
    return static_cast<int>(a.states.size() + b.states.size());
}
lab/dfa_equiv/verificador.cppDescargar lab/dfa_equiv/verificador.cpp
// Verificador de "¿Son equivalentes dos DFA?". Lo llama el juez: verificador NN.in NN.out salida
// Cuando los autómatas son distintos hay muchas respuestas correctas, así que no se compara el
// texto. Se comprueba que la cadena entregada tiene la longitud de la respuesta de referencia,
// que es la mínima, y que de verdad un autómata la acepta y el otro no.
#include <algorithm>
#include <cstddef>
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#include <unordered_map>
#include <vector>

struct Dfa {
    std::vector<std::string> states;
    std::vector<char> alphabet;
    std::vector<int> delta;  // delta[i * |Σ| + j]
    int start = 0;
    std::vector<bool> accept;
    int symbol_index[256];
};

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

static Dfa read_dfa(std::istream& in) {
    Dfa m;
    std::fill(m.symbol_index, m.symbol_index + 256, -1);
    std::unordered_map<std::string, int> index;
    bool in_delta = false;
    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()) {
            continue;
        }
        if (words.size() == 1 && words[0] == "---") {
            break;
        }
        if (in_delta) {
            int from = index.at(words[0]);
            int symbol = m.symbol_index[static_cast<unsigned char>(words[1][0])];
            m.delta[static_cast<std::size_t>(from) * m.alphabet.size() + static_cast<std::size_t>(symbol)] =
                index.at(words[2]);
        } else if (words[0] == "states:") {
            for (std::size_t i = 1; i < words.size(); i++) {
                index[words[i]] = static_cast<int>(m.states.size());
                m.states.push_back(words[i]);
            }
        } else if (words[0] == "alphabet:") {
            for (std::size_t i = 1; i < words.size(); i++) {
                m.symbol_index[static_cast<unsigned char>(words[i][0])] = static_cast<int>(m.alphabet.size());
                m.alphabet.push_back(words[i][0]);
            }
        } else if (words[0] == "start:") {
            m.start = index.at(words[1]);
        } else if (words[0] == "accept:") {
            m.accept.assign(m.states.size(), false);
            for (std::size_t i = 1; i < words.size(); i++) {
                m.accept[static_cast<std::size_t>(index.at(words[i]))] = true;
            }
        } else if (words[0] == "delta:") {
            m.delta.assign(m.states.size() * m.alphabet.size(), 0);
            in_delta = true;
        }
    }
    return m;
}

// ¿M acepta w? Devuelve false en ok si w tiene un símbolo que no es del alfabeto.
static bool accepts(const Dfa& m, const std::string& w, bool& ok) {
    std::size_t q = static_cast<std::size_t>(m.start);
    for (char c : w) {
        int symbol = m.symbol_index[static_cast<unsigned char>(c)];
        if (symbol < 0) {
            ok = false;
            return false;
        }
        q = static_cast<std::size_t>(m.delta[q * m.alphabet.size() + static_cast<std::size_t>(symbol)]);
    }
    return m.accept[q];
}

static std::vector<std::string> read_words(const char* path) {
    std::ifstream file(path);
    std::vector<std::string> words;
    std::string word;
    while (file >> word) {
        words.push_back(word);
    }
    return words;
}

static int wrong(const std::string& message) {
    std::cout << message << '\n';
    return 1;
}

int main(int argc, char** argv) {
    if (argc != 4) {
        std::cerr << "uso: verificador NN.in NN.out salida\n";
        return 2;
    }
    std::ifstream input(argv[1]);
    Dfa a = read_dfa(input);
    Dfa b = read_dfa(input);
    std::vector<std::string> expected = read_words(argv[2]);
    std::vector<std::string> got = read_words(argv[3]);

    if (got.empty()) {
        return wrong("la salida está vacía");
    }
    if (got[0] != "equivalentes" && got[0] != "distintos") {
        return wrong("la primera palabra debe ser equivalentes o distintos, salió " + got[0].substr(0, 30));
    }
    if (got[0] != expected[0]) {
        return wrong("esperaba " + expected[0] + ", salió " + got[0]);
    }
    if (got[0] == "equivalentes") {
        return got.size() == 1 ? 0 : wrong("después de equivalentes no va nada");
    }
    if (got.size() != 2) {
        return wrong("después de distintos va exactamente una cadena (eps si es la vacía)");
    }
    std::string w = got[1] == "eps" ? "" : got[1];
    std::string reference = expected[1] == "eps" ? "" : expected[1];
    bool ok = true;
    bool in_a = accepts(a, w, ok);
    bool in_b = accepts(b, w, ok);
    if (!ok) {
        return wrong("la cadena tiene símbolos que no son del alfabeto");
    }
    if (in_a == in_b) {
        return wrong(std::string("la cadena no separa a los autómatas: los dos la ") + (in_a ? "aceptan" : "rechazan"));
    }
    if (w.size() > reference.size()) {
        return wrong("la cadena separa a los autómatas pero no es de las más cortas: mide " +
                     std::to_string(w.size()) + " y hay una de " + std::to_string(reference.size()));
    }
    if (w.size() < reference.size()) {
        return wrong("la cadena es más corta que la de referencia: el caso está mal, avisen al docente");
    }
    return 0;
}
lab/dfa_equiv/machines/kth6_all.dfaDescargar lab/dfa_equiv/machines/kth6_all.dfa
# El símbolo número 6 desde el final es 1.
# Construcción de subconjuntos del NFA con todos los subconjuntos, alcanzables o no.
states: {} {q0} {q1} {q0,q1} {q2} {q0,q2} {q1,q2} {q0,q1,q2} {q3} {q0,q3} {q1,q3} {q0,q1,q3} {q2,q3} {q0,q2,q3} {q1,q2,q3} {q0,q1,q2,q3} {q4} {q0,q4} {q1,q4} {q0,q1,q4} {q2,q4} {q0,q2,q4} {q1,q2,q4} {q0,q1,q2,q4} {q3,q4} {q0,q3,q4} {q1,q3,q4} {q0,q1,q3,q4} {q2,q3,q4} {q0,q2,q3,q4} {q1,q2,q3,q4} {q0,q1,q2,q3,q4} {q5} {q0,q5} {q1,q5} {q0,q1,q5} {q2,q5} {q0,q2,q5} {q1,q2,q5} {q0,q1,q2,q5} {q3,q5} {q0,q3,q5} {q1,q3,q5} {q0,q1,q3,q5} {q2,q3,q5} {q0,q2,q3,q5} {q1,q2,q3,q5} {q0,q1,q2,q3,q5} {q4,q5} {q0,q4,q5} {q1,q4,q5} {q0,q1,q4,q5} {q2,q4,q5} {q0,q2,q4,q5} {q1,q2,q4,q5} {q0,q1,q2,q4,q5} {q3,q4,q5} {q0,q3,q4,q5} {q1,q3,q4,q5} {q0,q1,q3,q4,q5} {q2,q3,q4,q5} {q0,q2,q3,q4,q5} {q1,q2,q3,q4,q5} {q0,q1,q2,q3,q4,q5} {q6} {q0,q6} {q1,q6} {q0,q1,q6} {q2,q6} {q0,q2,q6} {q1,q2,q6} {q0,q1,q2,q6} {q3,q6} {q0,q3,q6} {q1,q3,q6} {q0,q1,q3,q6} {q2,q3,q6} {q0,q2,q3,q6} {q1,q2,q3,q6} {q0,q1,q2,q3,q6} {q4,q6} {q0,q4,q6} {q1,q4,q6} {q0,q1,q4,q6} {q2,q4,q6} {q0,q2,q4,q6} {q1,q2,q4,q6} {q0,q1,q2,q4,q6} {q3,q4,q6} {q0,q3,q4,q6} {q1,q3,q4,q6} {q0,q1,q3,q4,q6} {q2,q3,q4,q6} {q0,q2,q3,q4,q6} {q1,q2,q3,q4,q6} {q0,q1,q2,q3,q4,q6} {q5,q6} {q0,q5,q6} {q1,q5,q6} {q0,q1,q5,q6} {q2,q5,q6} {q0,q2,q5,q6} {q1,q2,q5,q6} {q0,q1,q2,q5,q6} {q3,q5,q6} {q0,q3,q5,q6} {q1,q3,q5,q6} {q0,q1,q3,q5,q6} {q2,q3,q5,q6} {q0,q2,q3,q5,q6} {q1,q2,q3,q5,q6} {q0,q1,q2,q3,q5,q6} {q4,q5,q6} {q0,q4,q5,q6} {q1,q4,q5,q6} {q0,q1,q4,q5,q6} {q2,q4,q5,q6} {q0,q2,q4,q5,q6} {q1,q2,q4,q5,q6} {q0,q1,q2,q4,q5,q6} {q3,q4,q5,q6} {q0,q3,q4,q5,q6} {q1,q3,q4,q5,q6} {q0,q1,q3,q4,q5,q6} {q2,q3,q4,q5,q6} {q0,q2,q3,q4,q5,q6} {q1,q2,q3,q4,q5,q6} {q0,q1,q2,q3,q4,q5,q6}
alphabet: 0 1
start: {q0}
accept: {q6} {q0,q6} {q1,q6} {q0,q1,q6} {q2,q6} {q0,q2,q6} {q1,q2,q6} {q0,q1,q2,q6} {q3,q6} {q0,q3,q6} {q1,q3,q6} {q0,q1,q3,q6} {q2,q3,q6} {q0,q2,q3,q6} {q1,q2,q3,q6} {q0,q1,q2,q3,q6} {q4,q6} {q0,q4,q6} {q1,q4,q6} {q0,q1,q4,q6} {q2,q4,q6} {q0,q2,q4,q6} {q1,q2,q4,q6} {q0,q1,q2,q4,q6} {q3,q4,q6} {q0,q3,q4,q6} {q1,q3,q4,q6} {q0,q1,q3,q4,q6} {q2,q3,q4,q6} {q0,q2,q3,q4,q6} {q1,q2,q3,q4,q6} {q0,q1,q2,q3,q4,q6} {q5,q6} {q0,q5,q6} {q1,q5,q6} {q0,q1,q5,q6} {q2,q5,q6} {q0,q2,q5,q6} {q1,q2,q5,q6} {q0,q1,q2,q5,q6} {q3,q5,q6} {q0,q3,q5,q6} {q1,q3,q5,q6} {q0,q1,q3,q5,q6} {q2,q3,q5,q6} {q0,q2,q3,q5,q6} {q1,q2,q3,q5,q6} {q0,q1,q2,q3,q5,q6} {q4,q5,q6} {q0,q4,q5,q6} {q1,q4,q5,q6} {q0,q1,q4,q5,q6} {q2,q4,q5,q6} {q0,q2,q4,q5,q6} {q1,q2,q4,q5,q6} {q0,q1,q2,q4,q5,q6} {q3,q4,q5,q6} {q0,q3,q4,q5,q6} {q1,q3,q4,q5,q6} {q0,q1,q3,q4,q5,q6} {q2,q3,q4,q5,q6} {q0,q2,q3,q4,q5,q6} {q1,q2,q3,q4,q5,q6} {q0,q1,q2,q3,q4,q5,q6}
delta:
{} 0 {}
{} 1 {}
{q0} 0 {q0}
{q0} 1 {q0,q1}
{q1} 0 {q2}
{q1} 1 {q2}
{q0,q1} 0 {q0,q2}
{q0,q1} 1 {q0,q1,q2}
{q2} 0 {q3}
{q2} 1 {q3}
{q0,q2} 0 {q0,q3}
{q0,q2} 1 {q0,q1,q3}
{q1,q2} 0 {q2,q3}
{q1,q2} 1 {q2,q3}
{q0,q1,q2} 0 {q0,q2,q3}
{q0,q1,q2} 1 {q0,q1,q2,q3}
{q3} 0 {q4}
{q3} 1 {q4}
{q0,q3} 0 {q0,q4}
{q0,q3} 1 {q0,q1,q4}
{q1,q3} 0 {q2,q4}
{q1,q3} 1 {q2,q4}
{q0,q1,q3} 0 {q0,q2,q4}
{q0,q1,q3} 1 {q0,q1,q2,q4}
{q2,q3} 0 {q3,q4}
{q2,q3} 1 {q3,q4}
{q0,q2,q3} 0 {q0,q3,q4}
{q0,q2,q3} 1 {q0,q1,q3,q4}
{q1,q2,q3} 0 {q2,q3,q4}
{q1,q2,q3} 1 {q2,q3,q4}
{q0,q1,q2,q3} 0 {q0,q2,q3,q4}
{q0,q1,q2,q3} 1 {q0,q1,q2,q3,q4}
{q4} 0 {q5}
{q4} 1 {q5}
{q0,q4} 0 {q0,q5}
{q0,q4} 1 {q0,q1,q5}
{q1,q4} 0 {q2,q5}
{q1,q4} 1 {q2,q5}
{q0,q1,q4} 0 {q0,q2,q5}
{q0,q1,q4} 1 {q0,q1,q2,q5}
{q2,q4} 0 {q3,q5}
{q2,q4} 1 {q3,q5}
{q0,q2,q4} 0 {q0,q3,q5}
{q0,q2,q4} 1 {q0,q1,q3,q5}
{q1,q2,q4} 0 {q2,q3,q5}
{q1,q2,q4} 1 {q2,q3,q5}
{q0,q1,q2,q4} 0 {q0,q2,q3,q5}
{q0,q1,q2,q4} 1 {q0,q1,q2,q3,q5}
{q3,q4} 0 {q4,q5}
{q3,q4} 1 {q4,q5}
{q0,q3,q4} 0 {q0,q4,q5}
{q0,q3,q4} 1 {q0,q1,q4,q5}
{q1,q3,q4} 0 {q2,q4,q5}
{q1,q3,q4} 1 {q2,q4,q5}
{q0,q1,q3,q4} 0 {q0,q2,q4,q5}
{q0,q1,q3,q4} 1 {q0,q1,q2,q4,q5}
{q2,q3,q4} 0 {q3,q4,q5}
{q2,q3,q4} 1 {q3,q4,q5}
{q0,q2,q3,q4} 0 {q0,q3,q4,q5}
{q0,q2,q3,q4} 1 {q0,q1,q3,q4,q5}
{q1,q2,q3,q4} 0 {q2,q3,q4,q5}
{q1,q2,q3,q4} 1 {q2,q3,q4,q5}
{q0,q1,q2,q3,q4} 0 {q0,q2,q3,q4,q5}
{q0,q1,q2,q3,q4} 1 {q0,q1,q2,q3,q4,q5}
{q5} 0 {q6}
{q5} 1 {q6}
{q0,q5} 0 {q0,q6}
{q0,q5} 1 {q0,q1,q6}
{q1,q5} 0 {q2,q6}
{q1,q5} 1 {q2,q6}
{q0,q1,q5} 0 {q0,q2,q6}
{q0,q1,q5} 1 {q0,q1,q2,q6}
{q2,q5} 0 {q3,q6}
{q2,q5} 1 {q3,q6}
{q0,q2,q5} 0 {q0,q3,q6}
{q0,q2,q5} 1 {q0,q1,q3,q6}
{q1,q2,q5} 0 {q2,q3,q6}
{q1,q2,q5} 1 {q2,q3,q6}
{q0,q1,q2,q5} 0 {q0,q2,q3,q6}
{q0,q1,q2,q5} 1 {q0,q1,q2,q3,q6}
{q3,q5} 0 {q4,q6}
{q3,q5} 1 {q4,q6}
{q0,q3,q5} 0 {q0,q4,q6}
{q0,q3,q5} 1 {q0,q1,q4,q6}
{q1,q3,q5} 0 {q2,q4,q6}
{q1,q3,q5} 1 {q2,q4,q6}
{q0,q1,q3,q5} 0 {q0,q2,q4,q6}
{q0,q1,q3,q5} 1 {q0,q1,q2,q4,q6}
{q2,q3,q5} 0 {q3,q4,q6}
{q2,q3,q5} 1 {q3,q4,q6}
{q0,q2,q3,q5} 0 {q0,q3,q4,q6}
{q0,q2,q3,q5} 1 {q0,q1,q3,q4,q6}
{q1,q2,q3,q5} 0 {q2,q3,q4,q6}
{q1,q2,q3,q5} 1 {q2,q3,q4,q6}
{q0,q1,q2,q3,q5} 0 {q0,q2,q3,q4,q6}
{q0,q1,q2,q3,q5} 1 {q0,q1,q2,q3,q4,q6}
{q4,q5} 0 {q5,q6}
{q4,q5} 1 {q5,q6}
{q0,q4,q5} 0 {q0,q5,q6}
{q0,q4,q5} 1 {q0,q1,q5,q6}
{q1,q4,q5} 0 {q2,q5,q6}
{q1,q4,q5} 1 {q2,q5,q6}
{q0,q1,q4,q5} 0 {q0,q2,q5,q6}
{q0,q1,q4,q5} 1 {q0,q1,q2,q5,q6}
{q2,q4,q5} 0 {q3,q5,q6}
{q2,q4,q5} 1 {q3,q5,q6}
{q0,q2,q4,q5} 0 {q0,q3,q5,q6}
{q0,q2,q4,q5} 1 {q0,q1,q3,q5,q6}
{q1,q2,q4,q5} 0 {q2,q3,q5,q6}
{q1,q2,q4,q5} 1 {q2,q3,q5,q6}
{q0,q1,q2,q4,q5} 0 {q0,q2,q3,q5,q6}
{q0,q1,q2,q4,q5} 1 {q0,q1,q2,q3,q5,q6}
{q3,q4,q5} 0 {q4,q5,q6}
{q3,q4,q5} 1 {q4,q5,q6}
{q0,q3,q4,q5} 0 {q0,q4,q5,q6}
{q0,q3,q4,q5} 1 {q0,q1,q4,q5,q6}
{q1,q3,q4,q5} 0 {q2,q4,q5,q6}
{q1,q3,q4,q5} 1 {q2,q4,q5,q6}
{q0,q1,q3,q4,q5} 0 {q0,q2,q4,q5,q6}
{q0,q1,q3,q4,q5} 1 {q0,q1,q2,q4,q5,q6}
{q2,q3,q4,q5} 0 {q3,q4,q5,q6}
{q2,q3,q4,q5} 1 {q3,q4,q5,q6}
{q0,q2,q3,q4,q5} 0 {q0,q3,q4,q5,q6}
{q0,q2,q3,q4,q5} 1 {q0,q1,q3,q4,q5,q6}
{q1,q2,q3,q4,q5} 0 {q2,q3,q4,q5,q6}
{q1,q2,q3,q4,q5} 1 {q2,q3,q4,q5,q6}
{q0,q1,q2,q3,q4,q5} 0 {q0,q2,q3,q4,q5,q6}
{q0,q1,q2,q3,q4,q5} 1 {q0,q1,q2,q3,q4,q5,q6}
{q6} 0 {}
{q6} 1 {}
{q0,q6} 0 {q0}
{q0,q6} 1 {q0,q1}
{q1,q6} 0 {q2}
{q1,q6} 1 {q2}
{q0,q1,q6} 0 {q0,q2}
{q0,q1,q6} 1 {q0,q1,q2}
{q2,q6} 0 {q3}
{q2,q6} 1 {q3}
{q0,q2,q6} 0 {q0,q3}
{q0,q2,q6} 1 {q0,q1,q3}
{q1,q2,q6} 0 {q2,q3}
{q1,q2,q6} 1 {q2,q3}
{q0,q1,q2,q6} 0 {q0,q2,q3}
{q0,q1,q2,q6} 1 {q0,q1,q2,q3}
{q3,q6} 0 {q4}
{q3,q6} 1 {q4}
{q0,q3,q6} 0 {q0,q4}
{q0,q3,q6} 1 {q0,q1,q4}
{q1,q3,q6} 0 {q2,q4}
{q1,q3,q6} 1 {q2,q4}
{q0,q1,q3,q6} 0 {q0,q2,q4}
{q0,q1,q3,q6} 1 {q0,q1,q2,q4}
{q2,q3,q6} 0 {q3,q4}
{q2,q3,q6} 1 {q3,q4}
{q0,q2,q3,q6} 0 {q0,q3,q4}
{q0,q2,q3,q6} 1 {q0,q1,q3,q4}
{q1,q2,q3,q6} 0 {q2,q3,q4}
{q1,q2,q3,q6} 1 {q2,q3,q4}
{q0,q1,q2,q3,q6} 0 {q0,q2,q3,q4}
{q0,q1,q2,q3,q6} 1 {q0,q1,q2,q3,q4}
{q4,q6} 0 {q5}
{q4,q6} 1 {q5}
{q0,q4,q6} 0 {q0,q5}
{q0,q4,q6} 1 {q0,q1,q5}
{q1,q4,q6} 0 {q2,q5}
{q1,q4,q6} 1 {q2,q5}
{q0,q1,q4,q6} 0 {q0,q2,q5}
{q0,q1,q4,q6} 1 {q0,q1,q2,q5}
{q2,q4,q6} 0 {q3,q5}
{q2,q4,q6} 1 {q3,q5}
{q0,q2,q4,q6} 0 {q0,q3,q5}
{q0,q2,q4,q6} 1 {q0,q1,q3,q5}
{q1,q2,q4,q6} 0 {q2,q3,q5}
{q1,q2,q4,q6} 1 {q2,q3,q5}
{q0,q1,q2,q4,q6} 0 {q0,q2,q3,q5}
{q0,q1,q2,q4,q6} 1 {q0,q1,q2,q3,q5}
{q3,q4,q6} 0 {q4,q5}
{q3,q4,q6} 1 {q4,q5}
{q0,q3,q4,q6} 0 {q0,q4,q5}
{q0,q3,q4,q6} 1 {q0,q1,q4,q5}
{q1,q3,q4,q6} 0 {q2,q4,q5}
{q1,q3,q4,q6} 1 {q2,q4,q5}
{q0,q1,q3,q4,q6} 0 {q0,q2,q4,q5}
{q0,q1,q3,q4,q6} 1 {q0,q1,q2,q4,q5}
{q2,q3,q4,q6} 0 {q3,q4,q5}
{q2,q3,q4,q6} 1 {q3,q4,q5}
{q0,q2,q3,q4,q6} 0 {q0,q3,q4,q5}
{q0,q2,q3,q4,q6} 1 {q0,q1,q3,q4,q5}
{q1,q2,q3,q4,q6} 0 {q2,q3,q4,q5}
{q1,q2,q3,q4,q6} 1 {q2,q3,q4,q5}
{q0,q1,q2,q3,q4,q6} 0 {q0,q2,q3,q4,q5}
{q0,q1,q2,q3,q4,q6} 1 {q0,q1,q2,q3,q4,q5}
{q5,q6} 0 {q6}
{q5,q6} 1 {q6}
{q0,q5,q6} 0 {q0,q6}
{q0,q5,q6} 1 {q0,q1,q6}
{q1,q5,q6} 0 {q2,q6}
{q1,q5,q6} 1 {q2,q6}
{q0,q1,q5,q6} 0 {q0,q2,q6}
{q0,q1,q5,q6} 1 {q0,q1,q2,q6}
{q2,q5,q6} 0 {q3,q6}
{q2,q5,q6} 1 {q3,q6}
{q0,q2,q5,q6} 0 {q0,q3,q6}
{q0,q2,q5,q6} 1 {q0,q1,q3,q6}
{q1,q2,q5,q6} 0 {q2,q3,q6}
{q1,q2,q5,q6} 1 {q2,q3,q6}
{q0,q1,q2,q5,q6} 0 {q0,q2,q3,q6}
{q0,q1,q2,q5,q6} 1 {q0,q1,q2,q3,q6}
{q3,q5,q6} 0 {q4,q6}
{q3,q5,q6} 1 {q4,q6}
{q0,q3,q5,q6} 0 {q0,q4,q6}
{q0,q3,q5,q6} 1 {q0,q1,q4,q6}
{q1,q3,q5,q6} 0 {q2,q4,q6}
{q1,q3,q5,q6} 1 {q2,q4,q6}
{q0,q1,q3,q5,q6} 0 {q0,q2,q4,q6}
{q0,q1,q3,q5,q6} 1 {q0,q1,q2,q4,q6}
{q2,q3,q5,q6} 0 {q3,q4,q6}
{q2,q3,q5,q6} 1 {q3,q4,q6}
{q0,q2,q3,q5,q6} 0 {q0,q3,q4,q6}
{q0,q2,q3,q5,q6} 1 {q0,q1,q3,q4,q6}
{q1,q2,q3,q5,q6} 0 {q2,q3,q4,q6}
{q1,q2,q3,q5,q6} 1 {q2,q3,q4,q6}
{q0,q1,q2,q3,q5,q6} 0 {q0,q2,q3,q4,q6}
{q0,q1,q2,q3,q5,q6} 1 {q0,q1,q2,q3,q4,q6}
{q4,q5,q6} 0 {q5,q6}
{q4,q5,q6} 1 {q5,q6}
{q0,q4,q5,q6} 0 {q0,q5,q6}
{q0,q4,q5,q6} 1 {q0,q1,q5,q6}
{q1,q4,q5,q6} 0 {q2,q5,q6}
{q1,q4,q5,q6} 1 {q2,q5,q6}
{q0,q1,q4,q5,q6} 0 {q0,q2,q5,q6}
{q0,q1,q4,q5,q6} 1 {q0,q1,q2,q5,q6}
{q2,q4,q5,q6} 0 {q3,q5,q6}
{q2,q4,q5,q6} 1 {q3,q5,q6}
{q0,q2,q4,q5,q6} 0 {q0,q3,q5,q6}
{q0,q2,q4,q5,q6} 1 {q0,q1,q3,q5,q6}
{q1,q2,q4,q5,q6} 0 {q2,q3,q5,q6}
{q1,q2,q4,q5,q6} 1 {q2,q3,q5,q6}
{q0,q1,q2,q4,q5,q6} 0 {q0,q2,q3,q5,q6}
{q0,q1,q2,q4,q5,q6} 1 {q0,q1,q2,q3,q5,q6}
{q3,q4,q5,q6} 0 {q4,q5,q6}
{q3,q4,q5,q6} 1 {q4,q5,q6}
{q0,q3,q4,q5,q6} 0 {q0,q4,q5,q6}
{q0,q3,q4,q5,q6} 1 {q0,q1,q4,q5,q6}
{q1,q3,q4,q5,q6} 0 {q2,q4,q5,q6}
{q1,q3,q4,q5,q6} 1 {q2,q4,q5,q6}
{q0,q1,q3,q4,q5,q6} 0 {q0,q2,q4,q5,q6}
{q0,q1,q3,q4,q5,q6} 1 {q0,q1,q2,q4,q5,q6}
{q2,q3,q4,q5,q6} 0 {q3,q4,q5,q6}
{q2,q3,q4,q5,q6} 1 {q3,q4,q5,q6}
{q0,q2,q3,q4,q5,q6} 0 {q0,q3,q4,q5,q6}
{q0,q2,q3,q4,q5,q6} 1 {q0,q1,q3,q4,q5,q6}
{q1,q2,q3,q4,q5,q6} 0 {q2,q3,q4,q5,q6}
{q1,q2,q3,q4,q5,q6} 1 {q2,q3,q4,q5,q6}
{q0,q1,q2,q3,q4,q5,q6} 0 {q0,q2,q3,q4,q5,q6}
{q0,q1,q2,q3,q4,q5,q6} 1 {q0,q1,q2,q3,q4,q5,q6}
lab/dfa_equiv/machines/kth6_history.dfaDescargar lab/dfa_equiv/machines/kth6_history.dfa
# El símbolo número 6 desde el final es 1.
# Recuerda los últimos símbolos leídos: un estado por cada cadena de longitud a lo sumo 6.
states: h h0 h1 h00 h01 h10 h11 h000 h001 h010 h011 h100 h101 h110 h111 h0000 h0001 h0010 h0011 h0100 h0101 h0110 h0111 h1000 h1001 h1010 h1011 h1100 h1101 h1110 h1111 h00000 h00001 h00010 h00011 h00100 h00101 h00110 h00111 h01000 h01001 h01010 h01011 h01100 h01101 h01110 h01111 h10000 h10001 h10010 h10011 h10100 h10101 h10110 h10111 h11000 h11001 h11010 h11011 h11100 h11101 h11110 h11111 h000000 h000001 h000010 h000011 h000100 h000101 h000110 h000111 h001000 h001001 h001010 h001011 h001100 h001101 h001110 h001111 h010000 h010001 h010010 h010011 h010100 h010101 h010110 h010111 h011000 h011001 h011010 h011011 h011100 h011101 h011110 h011111 h100000 h100001 h100010 h100011 h100100 h100101 h100110 h100111 h101000 h101001 h101010 h101011 h101100 h101101 h101110 h101111 h110000 h110001 h110010 h110011 h110100 h110101 h110110 h110111 h111000 h111001 h111010 h111011 h111100 h111101 h111110 h111111
alphabet: 0 1
start: h
accept: h100000 h100001 h100010 h100011 h100100 h100101 h100110 h100111 h101000 h101001 h101010 h101011 h101100 h101101 h101110 h101111 h110000 h110001 h110010 h110011 h110100 h110101 h110110 h110111 h111000 h111001 h111010 h111011 h111100 h111101 h111110 h111111
delta:
h 0 h0
h 1 h1
h0 0 h00
h0 1 h01
h1 0 h10
h1 1 h11
h00 0 h000
h00 1 h001
h01 0 h010
h01 1 h011
h10 0 h100
h10 1 h101
h11 0 h110
h11 1 h111
h000 0 h0000
h000 1 h0001
h001 0 h0010
h001 1 h0011
h010 0 h0100
h010 1 h0101
h011 0 h0110
h011 1 h0111
h100 0 h1000
h100 1 h1001
h101 0 h1010
h101 1 h1011
h110 0 h1100
h110 1 h1101
h111 0 h1110
h111 1 h1111
h0000 0 h00000
h0000 1 h00001
h0001 0 h00010
h0001 1 h00011
h0010 0 h00100
h0010 1 h00101
h0011 0 h00110
h0011 1 h00111
h0100 0 h01000
h0100 1 h01001
h0101 0 h01010
h0101 1 h01011
h0110 0 h01100
h0110 1 h01101
h0111 0 h01110
h0111 1 h01111
h1000 0 h10000
h1000 1 h10001
h1001 0 h10010
h1001 1 h10011
h1010 0 h10100
h1010 1 h10101
h1011 0 h10110
h1011 1 h10111
h1100 0 h11000
h1100 1 h11001
h1101 0 h11010
h1101 1 h11011
h1110 0 h11100
h1110 1 h11101
h1111 0 h11110
h1111 1 h11111
h00000 0 h000000
h00000 1 h000001
h00001 0 h000010
h00001 1 h000011
h00010 0 h000100
h00010 1 h000101
h00011 0 h000110
h00011 1 h000111
h00100 0 h001000
h00100 1 h001001
h00101 0 h001010
h00101 1 h001011
h00110 0 h001100
h00110 1 h001101
h00111 0 h001110
h00111 1 h001111
h01000 0 h010000
h01000 1 h010001
h01001 0 h010010
h01001 1 h010011
h01010 0 h010100
h01010 1 h010101
h01011 0 h010110
h01011 1 h010111
h01100 0 h011000
h01100 1 h011001
h01101 0 h011010
h01101 1 h011011
h01110 0 h011100
h01110 1 h011101
h01111 0 h011110
h01111 1 h011111
h10000 0 h100000
h10000 1 h100001
h10001 0 h100010
h10001 1 h100011
h10010 0 h100100
h10010 1 h100101
h10011 0 h100110
h10011 1 h100111
h10100 0 h101000
h10100 1 h101001
h10101 0 h101010
h10101 1 h101011
h10110 0 h101100
h10110 1 h101101
h10111 0 h101110
h10111 1 h101111
h11000 0 h110000
h11000 1 h110001
h11001 0 h110010
h11001 1 h110011
h11010 0 h110100
h11010 1 h110101
h11011 0 h110110
h11011 1 h110111
h11100 0 h111000
h11100 1 h111001
h11101 0 h111010
h11101 1 h111011
h11110 0 h111100
h11110 1 h111101
h11111 0 h111110
h11111 1 h111111
h000000 0 h000000
h000000 1 h000001
h000001 0 h000010
h000001 1 h000011
h000010 0 h000100
h000010 1 h000101
h000011 0 h000110
h000011 1 h000111
h000100 0 h001000
h000100 1 h001001
h000101 0 h001010
h000101 1 h001011
h000110 0 h001100
h000110 1 h001101
h000111 0 h001110
h000111 1 h001111
h001000 0 h010000
h001000 1 h010001
h001001 0 h010010
h001001 1 h010011
h001010 0 h010100
h001010 1 h010101
h001011 0 h010110
h001011 1 h010111
h001100 0 h011000
h001100 1 h011001
h001101 0 h011010
h001101 1 h011011
h001110 0 h011100
h001110 1 h011101
h001111 0 h011110
h001111 1 h011111
h010000 0 h100000
h010000 1 h100001
h010001 0 h100010
h010001 1 h100011
h010010 0 h100100
h010010 1 h100101
h010011 0 h100110
h010011 1 h100111
h010100 0 h101000
h010100 1 h101001
h010101 0 h101010
h010101 1 h101011
h010110 0 h101100
h010110 1 h101101
h010111 0 h101110
h010111 1 h101111
h011000 0 h110000
h011000 1 h110001
h011001 0 h110010
h011001 1 h110011
h011010 0 h110100
h011010 1 h110101
h011011 0 h110110
h011011 1 h110111
h011100 0 h111000
h011100 1 h111001
h011101 0 h111010
h011101 1 h111011
h011110 0 h111100
h011110 1 h111101
h011111 0 h111110
h011111 1 h111111
h100000 0 h000000
h100000 1 h000001
h100001 0 h000010
h100001 1 h000011
h100010 0 h000100
h100010 1 h000101
h100011 0 h000110
h100011 1 h000111
h100100 0 h001000
h100100 1 h001001
h100101 0 h001010
h100101 1 h001011
h100110 0 h001100
h100110 1 h001101
h100111 0 h001110
h100111 1 h001111
h101000 0 h010000
h101000 1 h010001
h101001 0 h010010
h101001 1 h010011
h101010 0 h010100
h101010 1 h010101
h101011 0 h010110
h101011 1 h010111
h101100 0 h011000
h101100 1 h011001
h101101 0 h011010
h101101 1 h011011
h101110 0 h011100
h101110 1 h011101
h101111 0 h011110
h101111 1 h011111
h110000 0 h100000
h110000 1 h100001
h110001 0 h100010
h110001 1 h100011
h110010 0 h100100
h110010 1 h100101
h110011 0 h100110
h110011 1 h100111
h110100 0 h101000
h110100 1 h101001
h110101 0 h101010
h110101 1 h101011
h110110 0 h101100
h110110 1 h101101
h110111 0 h101110
h110111 1 h101111
h111000 0 h110000
h111000 1 h110001
h111001 0 h110010
h111001 1 h110011
h111010 0 h110100
h111010 1 h110101
h111011 0 h110110
h111011 1 h110111
h111100 0 h111000
h111100 1 h111001
h111101 0 h111010
h111101 1 h111011
h111110 0 h111100
h111110 1 h111101
h111111 0 h111110
h111111 1 h111111
lab/dfa_equiv/machines/kth6_min.dfaDescargar lab/dfa_equiv/machines/kth6_min.dfa
# El símbolo número 6 desde el final es 1.
# El DFA mínimo: sale de minimizar el que recuerda los últimos símbolos.
states: s0 s1 s2 s3 s4 s5 s6 s7 s8 s9 s10 s11 s12 s13 s14 s15 s16 s17 s18 s19 s20 s21 s22 s23 s24 s25 s26 s27 s28 s29 s30 s31 s32 s33 s34 s35 s36 s37 s38 s39 s40 s41 s42 s43 s44 s45 s46 s47 s48 s49 s50 s51 s52 s53 s54 s55 s56 s57 s58 s59 s60 s61 s62 s63
alphabet: 0 1
start: s0
accept: s32 s33 s34 s35 s36 s37 s38 s39 s40 s41 s42 s43 s44 s45 s46 s47 s48 s49 s50 s51 s52 s53 s54 s55 s56 s57 s58 s59 s60 s61 s62 s63
delta:
s0 0 s0
s0 1 s1
s1 0 s2
s1 1 s3
s2 0 s4
s2 1 s5
s3 0 s6
s3 1 s7
s4 0 s8
s4 1 s9
s5 0 s10
s5 1 s11
s6 0 s12
s6 1 s13
s7 0 s14
s7 1 s15
s8 0 s16
s8 1 s17
s9 0 s18
s9 1 s19
s10 0 s20
s10 1 s21
s11 0 s22
s11 1 s23
s12 0 s24
s12 1 s25
s13 0 s26
s13 1 s27
s14 0 s28
s14 1 s29
s15 0 s30
s15 1 s31
s16 0 s32
s16 1 s33
s17 0 s34
s17 1 s35
s18 0 s36
s18 1 s37
s19 0 s38
s19 1 s39
s20 0 s40
s20 1 s41
s21 0 s42
s21 1 s43
s22 0 s44
s22 1 s45
s23 0 s46
s23 1 s47
s24 0 s48
s24 1 s49
s25 0 s50
s25 1 s51
s26 0 s52
s26 1 s53
s27 0 s54
s27 1 s55
s28 0 s56
s28 1 s57
s29 0 s58
s29 1 s59
s30 0 s60
s30 1 s61
s31 0 s62
s31 1 s63
s32 0 s0
s32 1 s1
s33 0 s2
s33 1 s3
s34 0 s4
s34 1 s5
s35 0 s6
s35 1 s7
s36 0 s8
s36 1 s9
s37 0 s10
s37 1 s11
s38 0 s12
s38 1 s13
s39 0 s14
s39 1 s15
s40 0 s16
s40 1 s17
s41 0 s18
s41 1 s19
s42 0 s20
s42 1 s21
s43 0 s22
s43 1 s23
s44 0 s24
s44 1 s25
s45 0 s26
s45 1 s27
s46 0 s28
s46 1 s29
s47 0 s30
s47 1 s31
s48 0 s32
s48 1 s33
s49 0 s34
s49 1 s35
s50 0 s36
s50 1 s37
s51 0 s38
s51 1 s39
s52 0 s40
s52 1 s41
s53 0 s42
s53 1 s43
s54 0 s44
s54 1 s45
s55 0 s46
s55 1 s47
s56 0 s48
s56 1 s49
s57 0 s50
s57 1 s51
s58 0 s52
s58 1 s53
s59 0 s54
s59 1 s55
s60 0 s56
s60 1 s57
s61 0 s58
s61 1 s59
s62 0 s60
s62 1 s61
s63 0 s62
s63 1 s63
lab/dfa_equiv/machines/kth6_subsets.dfaDescargar lab/dfa_equiv/machines/kth6_subsets.dfa
# El símbolo número 6 desde el final es 1.
# Construcción de subconjuntos del NFA: solo los subconjuntos alcanzables.
states: {q0} {q0,q1} {q0,q2} {q0,q1,q2} {q0,q3} {q0,q1,q3} {q0,q2,q3} {q0,q1,q2,q3} {q0,q4} {q0,q1,q4} {q0,q2,q4} {q0,q1,q2,q4} {q0,q3,q4} {q0,q1,q3,q4} {q0,q2,q3,q4} {q0,q1,q2,q3,q4} {q0,q5} {q0,q1,q5} {q0,q2,q5} {q0,q1,q2,q5} {q0,q3,q5} {q0,q1,q3,q5} {q0,q2,q3,q5} {q0,q1,q2,q3,q5} {q0,q4,q5} {q0,q1,q4,q5} {q0,q2,q4,q5} {q0,q1,q2,q4,q5} {q0,q3,q4,q5} {q0,q1,q3,q4,q5} {q0,q2,q3,q4,q5} {q0,q1,q2,q3,q4,q5} {q0,q6} {q0,q1,q6} {q0,q2,q6} {q0,q1,q2,q6} {q0,q3,q6} {q0,q1,q3,q6} {q0,q2,q3,q6} {q0,q1,q2,q3,q6} {q0,q4,q6} {q0,q1,q4,q6} {q0,q2,q4,q6} {q0,q1,q2,q4,q6} {q0,q3,q4,q6} {q0,q1,q3,q4,q6} {q0,q2,q3,q4,q6} {q0,q1,q2,q3,q4,q6} {q0,q5,q6} {q0,q1,q5,q6} {q0,q2,q5,q6} {q0,q1,q2,q5,q6} {q0,q3,q5,q6} {q0,q1,q3,q5,q6} {q0,q2,q3,q5,q6} {q0,q1,q2,q3,q5,q6} {q0,q4,q5,q6} {q0,q1,q4,q5,q6} {q0,q2,q4,q5,q6} {q0,q1,q2,q4,q5,q6} {q0,q3,q4,q5,q6} {q0,q1,q3,q4,q5,q6} {q0,q2,q3,q4,q5,q6} {q0,q1,q2,q3,q4,q5,q6}
alphabet: 0 1
start: {q0}
accept: {q0,q6} {q0,q1,q6} {q0,q2,q6} {q0,q1,q2,q6} {q0,q3,q6} {q0,q1,q3,q6} {q0,q2,q3,q6} {q0,q1,q2,q3,q6} {q0,q4,q6} {q0,q1,q4,q6} {q0,q2,q4,q6} {q0,q1,q2,q4,q6} {q0,q3,q4,q6} {q0,q1,q3,q4,q6} {q0,q2,q3,q4,q6} {q0,q1,q2,q3,q4,q6} {q0,q5,q6} {q0,q1,q5,q6} {q0,q2,q5,q6} {q0,q1,q2,q5,q6} {q0,q3,q5,q6} {q0,q1,q3,q5,q6} {q0,q2,q3,q5,q6} {q0,q1,q2,q3,q5,q6} {q0,q4,q5,q6} {q0,q1,q4,q5,q6} {q0,q2,q4,q5,q6} {q0,q1,q2,q4,q5,q6} {q0,q3,q4,q5,q6} {q0,q1,q3,q4,q5,q6} {q0,q2,q3,q4,q5,q6} {q0,q1,q2,q3,q4,q5,q6}
delta:
{q0} 0 {q0}
{q0} 1 {q0,q1}
{q0,q1} 0 {q0,q2}
{q0,q1} 1 {q0,q1,q2}
{q0,q2} 0 {q0,q3}
{q0,q2} 1 {q0,q1,q3}
{q0,q1,q2} 0 {q0,q2,q3}
{q0,q1,q2} 1 {q0,q1,q2,q3}
{q0,q3} 0 {q0,q4}
{q0,q3} 1 {q0,q1,q4}
{q0,q1,q3} 0 {q0,q2,q4}
{q0,q1,q3} 1 {q0,q1,q2,q4}
{q0,q2,q3} 0 {q0,q3,q4}
{q0,q2,q3} 1 {q0,q1,q3,q4}
{q0,q1,q2,q3} 0 {q0,q2,q3,q4}
{q0,q1,q2,q3} 1 {q0,q1,q2,q3,q4}
{q0,q4} 0 {q0,q5}
{q0,q4} 1 {q0,q1,q5}
{q0,q1,q4} 0 {q0,q2,q5}
{q0,q1,q4} 1 {q0,q1,q2,q5}
{q0,q2,q4} 0 {q0,q3,q5}
{q0,q2,q4} 1 {q0,q1,q3,q5}
{q0,q1,q2,q4} 0 {q0,q2,q3,q5}
{q0,q1,q2,q4} 1 {q0,q1,q2,q3,q5}
{q0,q3,q4} 0 {q0,q4,q5}
{q0,q3,q4} 1 {q0,q1,q4,q5}
{q0,q1,q3,q4} 0 {q0,q2,q4,q5}
{q0,q1,q3,q4} 1 {q0,q1,q2,q4,q5}
{q0,q2,q3,q4} 0 {q0,q3,q4,q5}
{q0,q2,q3,q4} 1 {q0,q1,q3,q4,q5}
{q0,q1,q2,q3,q4} 0 {q0,q2,q3,q4,q5}
{q0,q1,q2,q3,q4} 1 {q0,q1,q2,q3,q4,q5}
{q0,q5} 0 {q0,q6}
{q0,q5} 1 {q0,q1,q6}
{q0,q1,q5} 0 {q0,q2,q6}
{q0,q1,q5} 1 {q0,q1,q2,q6}
{q0,q2,q5} 0 {q0,q3,q6}
{q0,q2,q5} 1 {q0,q1,q3,q6}
{q0,q1,q2,q5} 0 {q0,q2,q3,q6}
{q0,q1,q2,q5} 1 {q0,q1,q2,q3,q6}
{q0,q3,q5} 0 {q0,q4,q6}
{q0,q3,q5} 1 {q0,q1,q4,q6}
{q0,q1,q3,q5} 0 {q0,q2,q4,q6}
{q0,q1,q3,q5} 1 {q0,q1,q2,q4,q6}
{q0,q2,q3,q5} 0 {q0,q3,q4,q6}
{q0,q2,q3,q5} 1 {q0,q1,q3,q4,q6}
{q0,q1,q2,q3,q5} 0 {q0,q2,q3,q4,q6}
{q0,q1,q2,q3,q5} 1 {q0,q1,q2,q3,q4,q6}
{q0,q4,q5} 0 {q0,q5,q6}
{q0,q4,q5} 1 {q0,q1,q5,q6}
{q0,q1,q4,q5} 0 {q0,q2,q5,q6}
{q0,q1,q4,q5} 1 {q0,q1,q2,q5,q6}
{q0,q2,q4,q5} 0 {q0,q3,q5,q6}
{q0,q2,q4,q5} 1 {q0,q1,q3,q5,q6}
{q0,q1,q2,q4,q5} 0 {q0,q2,q3,q5,q6}
{q0,q1,q2,q4,q5} 1 {q0,q1,q2,q3,q5,q6}
{q0,q3,q4,q5} 0 {q0,q4,q5,q6}
{q0,q3,q4,q5} 1 {q0,q1,q4,q5,q6}
{q0,q1,q3,q4,q5} 0 {q0,q2,q4,q5,q6}
{q0,q1,q3,q4,q5} 1 {q0,q1,q2,q4,q5,q6}
{q0,q2,q3,q4,q5} 0 {q0,q3,q4,q5,q6}
{q0,q2,q3,q4,q5} 1 {q0,q1,q3,q4,q5,q6}
{q0,q1,q2,q3,q4,q5} 0 {q0,q2,q3,q4,q5,q6}
{q0,q1,q2,q3,q4,q5} 1 {q0,q1,q2,q3,q4,q5,q6}
{q0,q6} 0 {q0}
{q0,q6} 1 {q0,q1}
{q0,q1,q6} 0 {q0,q2}
{q0,q1,q6} 1 {q0,q1,q2}
{q0,q2,q6} 0 {q0,q3}
{q0,q2,q6} 1 {q0,q1,q3}
{q0,q1,q2,q6} 0 {q0,q2,q3}
{q0,q1,q2,q6} 1 {q0,q1,q2,q3}
{q0,q3,q6} 0 {q0,q4}
{q0,q3,q6} 1 {q0,q1,q4}
{q0,q1,q3,q6} 0 {q0,q2,q4}
{q0,q1,q3,q6} 1 {q0,q1,q2,q4}
{q0,q2,q3,q6} 0 {q0,q3,q4}
{q0,q2,q3,q6} 1 {q0,q1,q3,q4}
{q0,q1,q2,q3,q6} 0 {q0,q2,q3,q4}
{q0,q1,q2,q3,q6} 1 {q0,q1,q2,q3,q4}
{q0,q4,q6} 0 {q0,q5}
{q0,q4,q6} 1 {q0,q1,q5}
{q0,q1,q4,q6} 0 {q0,q2,q5}
{q0,q1,q4,q6} 1 {q0,q1,q2,q5}
{q0,q2,q4,q6} 0 {q0,q3,q5}
{q0,q2,q4,q6} 1 {q0,q1,q3,q5}
{q0,q1,q2,q4,q6} 0 {q0,q2,q3,q5}
{q0,q1,q2,q4,q6} 1 {q0,q1,q2,q3,q5}
{q0,q3,q4,q6} 0 {q0,q4,q5}
{q0,q3,q4,q6} 1 {q0,q1,q4,q5}
{q0,q1,q3,q4,q6} 0 {q0,q2,q4,q5}
{q0,q1,q3,q4,q6} 1 {q0,q1,q2,q4,q5}
{q0,q2,q3,q4,q6} 0 {q0,q3,q4,q5}
{q0,q2,q3,q4,q6} 1 {q0,q1,q3,q4,q5}
{q0,q1,q2,q3,q4,q6} 0 {q0,q2,q3,q4,q5}
{q0,q1,q2,q3,q4,q6} 1 {q0,q1,q2,q3,q4,q5}
{q0,q5,q6} 0 {q0,q6}
{q0,q5,q6} 1 {q0,q1,q6}
{q0,q1,q5,q6} 0 {q0,q2,q6}
{q0,q1,q5,q6} 1 {q0,q1,q2,q6}
{q0,q2,q5,q6} 0 {q0,q3,q6}
{q0,q2,q5,q6} 1 {q0,q1,q3,q6}
{q0,q1,q2,q5,q6} 0 {q0,q2,q3,q6}
{q0,q1,q2,q5,q6} 1 {q0,q1,q2,q3,q6}
{q0,q3,q5,q6} 0 {q0,q4,q6}
{q0,q3,q5,q6} 1 {q0,q1,q4,q6}
{q0,q1,q3,q5,q6} 0 {q0,q2,q4,q6}
{q0,q1,q3,q5,q6} 1 {q0,q1,q2,q4,q6}
{q0,q2,q3,q5,q6} 0 {q0,q3,q4,q6}
{q0,q2,q3,q5,q6} 1 {q0,q1,q3,q4,q6}
{q0,q1,q2,q3,q5,q6} 0 {q0,q2,q3,q4,q6}
{q0,q1,q2,q3,q5,q6} 1 {q0,q1,q2,q3,q4,q6}
{q0,q4,q5,q6} 0 {q0,q5,q6}
{q0,q4,q5,q6} 1 {q0,q1,q5,q6}
{q0,q1,q4,q5,q6} 0 {q0,q2,q5,q6}
{q0,q1,q4,q5,q6} 1 {q0,q1,q2,q5,q6}
{q0,q2,q4,q5,q6} 0 {q0,q3,q5,q6}
{q0,q2,q4,q5,q6} 1 {q0,q1,q3,q5,q6}
{q0,q1,q2,q4,q5,q6} 0 {q0,q2,q3,q5,q6}
{q0,q1,q2,q4,q5,q6} 1 {q0,q1,q2,q3,q5,q6}
{q0,q3,q4,q5,q6} 0 {q0,q4,q5,q6}
{q0,q3,q4,q5,q6} 1 {q0,q1,q4,q5,q6}
{q0,q1,q3,q4,q5,q6} 0 {q0,q2,q4,q5,q6}
{q0,q1,q3,q4,q5,q6} 1 {q0,q1,q2,q4,q5,q6}
{q0,q2,q3,q4,q5,q6} 0 {q0,q3,q4,q5,q6}
{q0,q2,q3,q4,q5,q6} 1 {q0,q1,q3,q4,q5,q6}
{q0,q1,q2,q3,q4,q5,q6} 0 {q0,q2,q3,q4,q5,q6}
{q0,q1,q2,q3,q4,q5,q6} 1 {q0,q1,q2,q3,q4,q5,q6}
lab/dfa_equiv/machines/kth6_wrong.dfaDescargar lab/dfa_equiv/machines/kth6_wrong.dfa
# El símbolo número 6 desde el final es 1.
# El DFA mínimo con dos estados fusionados por error. No es equivalente a los otros.
states: s0 s1 s2 s4 s5 s6 s7 s8 s9 s10 s11 s12 s13 s14 s15 s16 s17 s18 s19 s20 s21 s22 s23 s24 s25 s26 s27 s28 s29 s30 s31 s32 s33 s34 s35 s36 s37 s38 s39 s40 s41 s42 s43 s44 s45 s46 s47 s48 s49 s50 s51 s52 s53 s54 s55 s56 s57 s58 s59 s60 s61 s62 s63
alphabet: 0 1
start: s0
accept: s32 s33 s34 s35 s36 s37 s38 s39 s40 s41 s42 s43 s44 s45 s46 s47 s48 s49 s50 s51 s52 s53 s54 s55 s56 s57 s58 s59 s60 s61 s62 s63
delta:
s0 0 s0
s0 1 s1
s1 0 s2
s1 1 s2
s2 0 s4
s2 1 s5
s4 0 s8
s4 1 s9
s5 0 s10
s5 1 s11
s6 0 s12
s6 1 s13
s7 0 s14
s7 1 s15
s8 0 s16
s8 1 s17
s9 0 s18
s9 1 s19
s10 0 s20
s10 1 s21
s11 0 s22
s11 1 s23
s12 0 s24
s12 1 s25
s13 0 s26
s13 1 s27
s14 0 s28
s14 1 s29
s15 0 s30
s15 1 s31
s16 0 s32
s16 1 s33
s17 0 s34
s17 1 s35
s18 0 s36
s18 1 s37
s19 0 s38
s19 1 s39
s20 0 s40
s20 1 s41
s21 0 s42
s21 1 s43
s22 0 s44
s22 1 s45
s23 0 s46
s23 1 s47
s24 0 s48
s24 1 s49
s25 0 s50
s25 1 s51
s26 0 s52
s26 1 s53
s27 0 s54
s27 1 s55
s28 0 s56
s28 1 s57
s29 0 s58
s29 1 s59
s30 0 s60
s30 1 s61
s31 0 s62
s31 1 s63
s32 0 s0
s32 1 s1
s33 0 s2
s33 1 s2
s34 0 s4
s34 1 s5
s35 0 s6
s35 1 s7
s36 0 s8
s36 1 s9
s37 0 s10
s37 1 s11
s38 0 s12
s38 1 s13
s39 0 s14
s39 1 s15
s40 0 s16
s40 1 s17
s41 0 s18
s41 1 s19
s42 0 s20
s42 1 s21
s43 0 s22
s43 1 s23
s44 0 s24
s44 1 s25
s45 0 s26
s45 1 s27
s46 0 s28
s46 1 s29
s47 0 s30
s47 1 s31
s48 0 s32
s48 1 s33
s49 0 s34
s49 1 s35
s50 0 s36
s50 1 s37
s51 0 s38
s51 1 s39
s52 0 s40
s52 1 s41
s53 0 s42
s53 1 s43
s54 0 s44
s54 1 s45
s55 0 s46
s55 1 s47
s56 0 s48
s56 1 s49
s57 0 s50
s57 1 s51
s58 0 s52
s58 1 s53
s59 0 s54
s59 1 s55
s60 0 s56
s60 1 s57
s61 0 s58
s61 1 s59
s62 0 s60
s62 1 s61
s63 0 s62
s63 1 s63
lab/dfa_equiv/machines/kth6.nfaDescargar lab/dfa_equiv/machines/kth6.nfa
# El símbolo número 6 desde el final es 1.
# El NFA de 7 estados.
states: q0 q1 q2 q3 q4 q5 q6
alphabet: 0 1
start: q0
accept: q6
delta:
q0 0 q0
q0 1 q0 q1
q1 0 q2
q1 1 q2
q2 0 q3
q2 1 q3
q3 0 q4
q3 1 q4
q4 0 q5
q4 1 q5
q5 0 q6
q5 1 q6

Compilación

Cómo se compilan y ejecutan los ejemplos.

MakefileDescargar Makefile
# Semana 9: lo decidible y lo indecidible.
# 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 kth       vuelve a escribir los autómatas de lab/dfa_equiv/machines
#   make clean     borra lo generado
#
# Las pruebas leen las máquinas de machines/ y de lab/dfa_equiv/machines/, así que se corren
# desde esta carpeta. El laboratorio está en lab/dfa_equiv 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 = a_dfa a_nfa e_dfa eq_dfa a_cfg e_cfg universal alternate make_kth
TESTS = test_dfa test_cfg test_tm
HEADERS = dfa.h nfa.h decide.h minimize.h cfg.h tm.h

.PHONY: all test kth 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."

kth: $(BUILD)/make_kth
	$(BUILD)/make_kth 6 lab/dfa_equiv/machines

clean:
	rm -rf $(BUILD)