Semana 4 — Lo que un autómata finito no puede hacer
Objetivos
- Demostrar que un lenguaje no es regular con el lema de bombeo, eligiendo bien la cadena.
- Demostrar lo mismo con cadenas distinguibles, y contar cuántos estados necesita un DFA.
- Enunciar el teorema de Myhill-Nerode y minimizar un DFA.
- Convertir una cota de estados en una cota de memoria para un algoritmo de streaming.
Sesión A — Lenguajes no regulares: el lema de bombeo
Lectura: Apuntes, semana 4.
Apoyo: Sipser, sec. 1.4 (Nonregular Languages).
Temas:
- Un lenguaje que pide contar sin límite: . Por qué “no se me ocurre un DFA” no es una demostración.
- La idea: con más símbolos que estados, algún estado se repite, y el ciclo se puede recorrer cualquier número de veces.
- Enunciado del lema de bombeo, con sus tres condiciones: , , .
- Demostración del lema con el principio del palomar.
- Usarlo como un juego contra un adversario: él elige , nosotros la cadena, él la división, nosotros .
- Ejemplos: , cadenas con igual número de ceros y unos, , , y , donde hay que bombear hacia abajo.
- Combinar con cierre: si fuera regular, también lo sería.
- Error común: elegir uno mismo la división , , , o usar una cadena que no depende de . El lema no sirve para demostrar que un lenguaje sí es regular.
Sesión B — Myhill-Nerode y minimización de DFA · ✂️ Una cota inferior de memoria en streaming
Lectura: Apuntes, semana 4.
Apoyo: Sipser deja Myhill-Nerode y la minimización como problemas del capítulo 1, sin desarrollarlos. Erickson, Models of Computation, nota 3, sección sobre conjuntos distinguidores (fooling sets). Los apuntes son el texto principal de esta sesión.
Temas:
- Cadenas distinguibles: e lo son si algún sufijo separa a de . Dos cadenas distinguibles no pueden terminar en el mismo estado.
- Un conjunto de cadenas distinguibles dos a dos obliga a tener estados. Si hay infinitas, el lenguaje no es regular: otra vez, en tres líneas.
- La deuda de la semana 2: “el -ésimo símbolo desde el final es ” necesita estados.
- Teorema de Myhill-Nerode: regular si y solo si hay un número finito de clases, y ese número es el de estados del DFA mínimo.
- Minimización: quitar los estados inalcanzables y fusionar los indistinguibles, refinando una partición. Ejemplo paso a paso.
- El DFA mínimo es único salvo los nombres. Consecuencia: se puede decidir si dos DFA son equivalentes.
- ✂️ Streaming: un algoritmo que lee los datos una vez con bits de memoria es un DFA con estados. Contar cadenas distinguibles da una cota inferior de memoria.
- Error común: fusionar dos estados porque “se parecen”, sin comprobar que ningún sufijo los separa.
Laboratorio — Práctica 1 · Opcional: minimizar un DFA
La sesión es para la Práctica 1 (semanas 1 a 3). Como ejercicio opcional:
- Leer un DFA y escribir el DFA mínimo equivalente.
- Eliminar primero los estados inalcanzables.
- Refinar la partición hasta que no cambie.
- Comprobar con el verificador que el resultado es equivalente y que no se puede reducir más.
- Minimizar el DFA que su programa de la semana 2 produjo para y comparar el número de estados.
Preguntas de repaso
- Demuestren con el lema de bombeo que no es regular. ¿Qué cadena eligen y por qué?
- Demuestren lo mismo con un conjunto infinito de cadenas distinguibles.
- ¿Por qué el lema de bombeo no demuestra que un lenguaje es regular? Den la forma lógica del enunciado.
- Minimicen a mano un DFA de seis estados, mostrando cada refinamiento de la partición.
- ¿Cuántos estados tiene el DFA mínimo de las cadenas binarias cuyo valor es múltiplo de 5? Justifiquen con cadenas distinguibles.
Código de la semana
Compilar y probar dentro del contenedor del curso con make y make test.
Ejemplos (23)Pruebas (3)Laboratorio (4)Compilación (1)
Ejemplos
Los programas que usan los apuntes y la clase.
// Las clases de equivalencia de Myhill-Nerode del lenguaje de un DFA: classes ARCHIVO.dfa [LONGITUD]
// Muestra un representante de cada clase, las cadenas de longitud a lo sumo LONGITUD (3 si no
// se dice) que caen en ella, y el autómata de las clases.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include "dfa.h"
#include "distinguish.h"
int main(int argc, char** argv) {
if (argc != 2 && argc != 3) {
std::cerr << "uso: classes ARCHIVO.dfa [LONGITUD]\n";
return 2;
}
try {
Dfa m = load_dfa(argv[1]);
std::size_t max_len = (argc == 3) ? std::stoul(argv[2]) : 3;
Classes classes = nerode_classes(m);
std::vector<std::string> strings = all_strings(m.alphabet, max_len);
std::cout << "clases de equivalencia: " << classes.representatives.size() << '\n';
for (const std::string& x : classes.representatives) {
std::cout << " " << class_name(x) << (accepts(m, x) ? " (en L):" : " (fuera de L):");
for (const std::string& w : strings) {
if (*class_of(m, classes, w) == x) {
std::cout << ' ' << (w.empty() ? "ε" : w);
}
}
std::cout << '\n';
}
std::cout << "el autómata de las clases:\n";
write_dfa(std::cout, nerode_dfa(m));
} catch (const std::exception& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// 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 pueda usar sola:
// leer y escribir el formato, la función de transición extendida, los estados alcanzables, la
// construcción del producto y el complemento. Lo nuevo de la semana 4 está en minimize.h,
// distinguish.h y pumping.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// ¿Dos cadenas son distinguibles respecto del lenguaje de un DFA?
// distinguish ARCHIVO.dfa X Y
// Por fuerza bruta: prueba los sufijos del más corto al más largo, hasta la longitud |Q| − 1.
// Si dos estados se pueden separar, algún sufijo de esa longitud o menos los separa.
// La cadena vacía se pasa como '' en la terminal.
#include <cstddef>
#include <iostream>
#include <optional>
#include <stdexcept>
#include <string>
#include "dfa.h"
#include "distinguish.h"
static std::string shown(const std::string& w) {
return w.empty() ? "ε" : w;
}
int main(int argc, char** argv) {
if (argc != 4) {
std::cerr << "uso: distinguish ARCHIVO.dfa X Y\n";
return 2;
}
try {
Dfa m = load_dfa(argv[1]);
std::string x = argv[2];
std::string y = argv[3];
std::cout << "x = " << shown(x) << " llega a " << delta_star(m, m.start, x) << ", y = " << shown(y)
<< " llega a " << delta_star(m, m.start, y) << '\n';
std::size_t max_len = m.states.size() - 1;
std::size_t tried = 0;
std::optional<std::string> z = brute_distinguishing_suffix(m, x, y, max_len, tried);
if (z) {
bool first = accepts(m, x + *z);
std::cout << "sufijos probados, del más corto al más largo: " << tried << '\n';
std::cout << "z = " << shown(*z) << " las distingue: xz = " << shown(x + *z)
<< (first ? " se acepta" : " se rechaza") << ", yz = " << shown(y + *z)
<< (first ? " se rechaza" : " se acepta") << '\n';
} else {
std::cout << "ningún sufijo de longitud a lo sumo |Q| - 1 = " << max_len << " las distingue (" << tried
<< " probados): son indistinguibles\n";
}
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Cadenas distinguibles. Dos cadenas x, y son distinguibles respecto de un lenguaje L si
// algún sufijo z deja a xz y a yz en lados distintos de L. Con un DFA de L en la mano, eso se
// puede comprobar: basta mirar los estados a los que llegan x e y.
#ifndef DISTINGUISH_H
#define DISTINGUISH_H
#include <cstddef>
#include <map>
#include <optional>
#include <queue>
#include <string>
#include <utility>
#include <vector>
#include "dfa.h"
// Todas las cadenas sobre el alfabeto con longitud a lo sumo max_len, primero las más cortas
// y, entre las de igual longitud, en el orden del alfabeto. (Es la de languages.h, semana 1.)
inline std::vector<std::string> all_strings(const std::vector<char>& alphabet, std::size_t max_len) {
std::vector<std::string> result = {""};
std::size_t first = 0; // dónde empiezan las cadenas de la longitud anterior
for (std::size_t len = 1; len <= max_len; len++) {
std::size_t last = result.size();
for (std::size_t i = first; i < last; i++) {
for (char a : alphabet) {
result.push_back(result[i] + a);
}
}
first = last;
}
return result;
}
// ¿El sufijo z distingue a x de y? Es decir: ¿M acepta exactamente una de xz, yz?
inline bool separates(const Dfa& m, const std::string& x, const std::string& y, const std::string& z) {
return accepts(m, x + z) != accepts(m, y + z);
}
// Fuerza bruta, tal como dice la definición: prueba los sufijos de longitud a lo sumo max_len,
// del más corto al más largo, y devuelve el primero que distingue. tried cuenta cuántos probó.
// Si no encuentra ninguno, eso solo demuestra algo cuando max_len ≥ |Q| − 1 (ver los apuntes).
inline std::optional<std::string> brute_distinguishing_suffix(const Dfa& m, const std::string& x,
const std::string& y, std::size_t max_len,
std::size_t& tried) {
tried = 0;
for (const std::string& z : all_strings(m.alphabet, max_len)) {
tried++;
if (separates(m, x, y, z)) {
return z;
}
}
return std::nullopt;
}
// Lo mismo sin probar cadenas: el sufijo más corto z tal que exactamente uno de δ*(p, z) y
// δ*(q, z) está en F, o nada si los estados p y q son indistinguibles. Recorre a lo ancho los
// pares de estados a los que se llega desde (p, q) leyendo lo mismo; hay a lo sumo |Q|² pares.
inline std::optional<std::string> state_distinguishing_suffix(const Dfa& m, const std::string& p,
const std::string& q) {
using Pair = std::pair<std::string, std::string>;
std::map<Pair, std::string> reached = {{{p, q}, ""}};
std::queue<Pair> pending;
pending.push({p, q});
while (!pending.empty()) {
Pair current = pending.front();
pending.pop();
std::string z = reached.at(current);
if ((m.accept.count(current.first) > 0) != (m.accept.count(current.second) > 0)) {
return z;
}
for (char a : m.alphabet) {
Pair next = {step(m, current.first, a), step(m, current.second, a)};
if (reached.count(next) == 0) {
reached[next] = z + a;
pending.push(next);
}
}
}
return std::nullopt;
}
// Para dos cadenas: x e y son distinguibles respecto de L(M) si y solo si lo son los estados
// δ*(q0, x) y δ*(q0, y), y con los mismos sufijos.
inline std::optional<std::string> distinguishing_suffix(const Dfa& m, const std::string& x,
const std::string& y) {
return state_distinguishing_suffix(m, delta_star(m, m.start, x), delta_star(m, m.start, y));
}
// ¿Las cadenas dadas son distinguibles dos a dos respecto de L(M)? Si lo son, todo DFA que
// reconozca L(M) tiene al menos strings.size() estados.
inline bool pairwise_distinguishable(const Dfa& m, const std::vector<std::string>& strings) {
for (std::size_t i = 0; i < strings.size(); i++) {
for (std::size_t j = i + 1; j < strings.size(); j++) {
if (!distinguishing_suffix(m, strings[i], strings[j])) {
return false;
}
}
}
return true;
}
// ------------------------------------------------------------
// El autómata de las clases (Myhill-Nerode)
// ------------------------------------------------------------
// Un representante por cada clase de equivalencia de L(M), y a qué clase pertenece cada
// cadena que se pregunte. Los representantes se buscan del más corto al más largo: ε primero,
// y después xa para cada representante x ya encontrado y cada símbolo a.
struct Classes {
std::vector<std::string> representatives;
};
// El representante de la clase de w, o nada si w no es equivalente a ninguno.
inline std::optional<std::string> class_of(const Dfa& m, const Classes& classes, const std::string& w) {
for (const std::string& r : classes.representatives) {
if (!distinguishing_suffix(m, w, r)) {
return r;
}
}
return std::nullopt;
}
inline Classes nerode_classes(const Dfa& m) {
Classes classes;
classes.representatives.push_back("");
for (std::size_t i = 0; i < classes.representatives.size(); i++) {
for (char a : m.alphabet) {
std::string candidate = classes.representatives[i] + a;
if (!class_of(m, classes, candidate)) {
classes.representatives.push_back(candidate);
}
}
}
return classes;
}
// El nombre del estado [x]. La cadena vacía se escribe ε.
inline std::string class_name(const std::string& x) {
return "[" + (x.empty() ? std::string("ε") : x) + "]";
}
// El DFA de la demostración de Myhill-Nerode: un estado por clase, δ([x], a) = [xa], el
// inicial es [ε] y [x] es de aceptación si x ∈ L. Aquí L es L(M), y M solo se usa para
// responder dos preguntas: si una cadena está en L y si dos cadenas son distinguibles.
inline Dfa nerode_dfa(const Dfa& m) {
Classes classes = nerode_classes(m);
Dfa result;
result.alphabet = m.alphabet;
result.start = class_name("");
for (const std::string& x : classes.representatives) {
result.states.push_back(class_name(x));
if (accepts(m, x)) {
result.accept.insert(class_name(x));
}
for (char a : m.alphabet) {
result.delta[{class_name(x), a}] = class_name(*class_of(m, classes, x + a));
}
}
check_dfa(result);
return result;
}
#endif// ¿Dos DFA reconocen el mismo lenguaje? equivalent A.dfa B.dfa
// Minimiza los dos y compara los mínimos, que son únicos salvo los nombres de los estados.
// Si son distintos, muestra la cadena más corta que uno acepta y el otro no.
#include <iostream>
#include <optional>
#include <stdexcept>
#include <string>
#include "dfa.h"
#include "minimize.h"
int main(int argc, char** argv) {
if (argc != 3) {
std::cerr << "uso: equivalent A.dfa B.dfa\n";
return 2;
}
try {
Dfa a = load_dfa(argv[1]);
Dfa b = load_dfa(argv[2]);
Dfa min_a = minimize(a);
Dfa min_b = minimize(b);
std::cout << argv[1] << ": " << a.states.size() << " estados, mínimo de " << min_a.states.size() << '\n';
std::cout << argv[2] << ": " << b.states.size() << " estados, mínimo de " << min_b.states.size() << '\n';
std::optional<std::string> witness = difference_witness(a, b);
if (isomorphic(min_a, min_b)) {
std::cout << "los dos mínimos son el mismo autómata salvo los nombres: reconocen el mismo lenguaje\n";
return witness ? 1 : 0; // no puede haber una cadena que los separe
}
std::cout << "los mínimos son distintos: no reconocen el mismo lenguaje\n";
if (witness) {
std::cout << "la cadena más corta que los separa: " << (witness->empty() ? "ε" : *witness) << " ("
<< (accepts(a, *witness) ? "la acepta el primero" : "la acepta el segundo") << ")\n";
}
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Comprueba que un conjunto de cadenas es distinguible dos a dos respecto del lenguaje de un DFA:
// fooling_set ARCHIVO.dfa CADENA CADENA...
// Imprime, para cada par, el sufijo más corto que lo distingue. Si todos los pares tienen
// uno, ningún DFA del mismo lenguaje tiene menos estados que cadenas hay en el conjunto.
// La cadena vacía se pasa como '' en la terminal.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <optional>
#include <stdexcept>
#include <string>
#include <vector>
#include "dfa.h"
#include "distinguish.h"
static std::string shown(const std::string& w) {
return w.empty() ? "ε" : w;
}
// ε ocupa dos bytes y una columna.
static std::string padded(const std::string& text, std::size_t width) {
std::size_t columns = (text == "ε") ? 1 : text.size();
return text + std::string(width > columns ? width - columns : 0, ' ');
}
int main(int argc, char** argv) {
if (argc < 4) {
std::cerr << "uso: fooling_set ARCHIVO.dfa CADENA CADENA...\n";
return 2;
}
try {
Dfa m = load_dfa(argv[1]);
std::vector<std::string> strings(argv + 2, argv + argc);
std::size_t n = strings.size();
std::vector<std::vector<std::string>> cell(n, std::vector<std::string>(n, "."));
std::size_t width = 1;
std::size_t failures = 0;
for (std::size_t i = 0; i < n; i++) {
width = std::max(width, strings[i].size());
for (std::size_t j = i + 1; j < n; j++) {
std::optional<std::string> z = distinguishing_suffix(m, strings[i], strings[j]);
cell[i][j] = z ? shown(*z) : "NO";
width = std::max(width, z ? z->size() : 2);
if (!z) {
failures++;
std::cout << shown(strings[i]) << " y " << shown(strings[j]) << " no son distinguibles: las dos llegan a "
<< "estados que ningún sufijo separa\n";
}
}
}
std::cout << "sufijo más corto que distingue a cada par (fila, columna):\n";
std::cout << " " << padded("", width);
for (std::size_t j = 1; j < n; j++) {
std::cout << " " << (j + 1 < n ? padded(shown(strings[j]), width) : shown(strings[j]));
}
std::cout << '\n';
for (std::size_t i = 0; i + 1 < n; i++) {
std::cout << " " << padded(shown(strings[i]), width);
for (std::size_t j = 1; j < n; j++) {
std::cout << " " << (j + 1 < n ? padded(cell[i][j], width) : cell[i][j]);
}
std::cout << '\n';
}
if (failures > 0) {
std::cout << failures << (failures == 1 ? " par" : " pares") << " sin sufijo: el conjunto no sirve\n";
return 1;
}
std::cout << n << " cadenas distinguibles dos a dos: todo DFA de este lenguaje tiene al menos " << n
<< " estados (este tiene " << m.states.size() << ")\n";
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// El DFA de "el k-ésimo símbolo desde el final es 1": kth_from_end K
// Escribe en formato .dfa el autómata de 2^K estados que recuerda los últimos K símbolos.
// kth_from_end --tabla K compara, para k de 1 a K, los estados antes y después de minimizar
#include <cstddef>
#include <cstdio>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include "dfa.h"
#include "minimize.h"
int main(int argc, char** argv) {
try {
if (argc == 3 && std::string(argv[1]) == "--tabla") {
int top = std::stoi(argv[2]);
std::cout << " k estados del NFA estados del DFA después de minimizar rondas con cambios\n";
for (int k = 1; k <= top; k++) {
Dfa m = last_k_dfa(k);
std::vector<Partition> rounds = moore_rounds(m);
Dfa minimal = quotient(m, rounds.back());
std::printf("%2d %15d %15zu %20zu %18zu\n", k, k + 1, m.states.size(), minimal.states.size(),
rounds.size() - 1);
}
return 0;
}
if (argc != 2) {
std::cerr << "uso: kth_from_end K o kth_from_end --tabla K\n";
return 2;
}
int k = std::stoi(argv[1]);
Dfa m = last_k_dfa(k);
std::cout << "# El símbolo número " << k << " desde el final es 1. El estado es lo último que se leyó:\n"
<< "# " << k << " símbolos, contando como 0 los que todavía no llegaron.\n";
write_dfa(std::cout, m);
} catch (const std::exception& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Minimiza un DFA y muestra la partición después de cada ronda: minimize ARCHIVO.dfa [opciones]
// --dfa escribe solo el DFA mínimo, en formato .dfa
// --todos no quita los estados inalcanzables antes de refinar (para ver qué pasa)
// Con - en lugar del archivo, lee la descripción de la entrada estándar.
// El detalle de cada ronda se imprime si el autómata tiene a lo sumo 26 estados.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <set>
#include <stdexcept>
#include <string>
#include <vector>
#include "dfa.h"
#include "minimize.h"
// Los bloques se muestran con letras: A, B, C, ...
static std::string letter(int block) {
return std::string(1, static_cast<char>('A' + block));
}
static std::string padded(const std::string& text, std::size_t width) {
return text + std::string(width > text.size() ? width - text.size() : 0, ' ');
}
static void print_partition(const Dfa& m, const Partition& p, std::size_t number, bool detail) {
std::cout << "P" << number << ": " << p.count << (p.count == 1 ? " bloque" : " bloques") << '\n';
if (!detail) {
return;
}
std::vector<std::vector<std::string>> blocks = blocks_of(m, p);
for (std::size_t i = 0; i < blocks.size(); i++) {
std::cout << " " << letter(static_cast<int>(i)) << " = {";
for (std::size_t k = 0; k < blocks[i].size(); k++) {
std::cout << (k > 0 ? ", " : "") << blocks[i][k];
}
std::cout << "}\n";
}
}
// La tabla de una ronda: a qué bloque de p va cada estado con cada símbolo. Dentro de un
// bloque, los estados cuya fila es distinta de la del primero se separan de él.
static void print_round(const Dfa& m, const Partition& p, std::size_t number) {
std::size_t width = 6;
for (const std::string& state : m.states) {
width = std::max(width, state.size());
}
std::cout << "ronda " << number << ": a qué bloque de P" << number - 1 << " va cada estado\n";
std::cout << " " << padded("estado", width) << " está en";
for (char a : m.alphabet) {
std::cout << " con " << a;
}
std::cout << '\n';
for (const std::vector<std::string>& block : blocks_of(m, p)) {
for (const std::string& state : block) {
bool differs = false;
std::string row = " " + padded(state, width) + " " + padded(letter(p.block.at(state)), 7);
for (char a : m.alphabet) {
int target = p.block.at(step(m, state, a));
differs = differs || target != p.block.at(step(m, block[0], a));
row += " " + padded(letter(target), 5);
}
if (differs) {
row += " <- se separa";
}
while (row.back() == ' ') {
row.pop_back();
}
std::cout << row << '\n';
}
}
}
int main(int argc, char** argv) {
std::string path;
bool only_dfa = false;
bool keep_all = false;
for (int i = 1; i < argc; i++) {
std::string arg = argv[i];
if (arg == "--dfa") {
only_dfa = true;
} else if (arg == "--todos") {
keep_all = true;
} else if (path.empty()) {
path = arg;
} else {
path.clear();
break;
}
}
if (path.empty()) {
std::cerr << "uso: minimize ARCHIVO.dfa [--dfa] [--todos]\n";
return 2;
}
try {
Dfa original = (path == "-") ? read_dfa(std::cin) : load_dfa(path);
Dfa m = keep_all ? original : remove_unreachable(original);
std::vector<Partition> rounds = moore_rounds(m);
Dfa minimal = quotient(m, rounds.back());
if (only_dfa) {
std::cout << "# DFA mínimo de " << path << ": " << minimal.states.size() << " estados.\n";
write_dfa(std::cout, minimal);
return 0;
}
std::cout << "estados: " << original.states.size() << ", alcanzables: " << reachable(original).size();
if (keep_all) {
std::cout << ". No se quita ninguno (--todos)\n";
} else if (m.states.size() == original.states.size()) {
std::cout << ". No hay nada que quitar\n";
} else {
std::cout << ". Se quitan:";
std::set<std::string> kept(m.states.begin(), m.states.end());
for (const std::string& state : original.states) {
if (kept.count(state) == 0) {
std::cout << ' ' << state;
}
}
std::cout << '\n';
}
bool detail = m.states.size() <= 26;
std::cout << '\n';
print_partition(m, rounds[0], 0, detail);
for (std::size_t k = 1; k <= rounds.size(); k++) {
if (detail) {
std::cout << '\n';
print_round(m, rounds[k - 1], k);
}
if (k < rounds.size()) {
print_partition(m, rounds[k], k, detail);
}
}
std::cout << "P" << rounds.size() << " = P" << rounds.size() - 1 << ": la partición ya no cambia\n";
std::cout << "\nDFA mínimo: " << minimal.states.size()
<< (minimal.states.size() == 1 ? " estado" : " estados") << '\n';
if (detail) {
write_dfa(std::cout, minimal);
}
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Minimización de un DFA por refinamiento de particiones (algoritmo de Moore), el DFA de
// "el k-ésimo símbolo desde el final es 1" y la comparación de dos DFA.
#ifndef MINIMIZE_H
#define MINIMIZE_H
#include <cstddef>
#include <map>
#include <optional>
#include <queue>
#include <set>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
#include "dfa.h"
// Una partición de Q: a cada estado, el número de su bloque. Los bloques se numeran desde 0
// en el orden en que aparece su primer estado en m.states.
struct Partition {
std::map<std::string, int> block;
int count = 0; // cuántos bloques hay
};
inline bool operator==(const Partition& a, const Partition& b) {
return a.count == b.count && a.block == b.block;
}
// Los bloques como listas de estados, cada una en el orden de m.states.
inline std::vector<std::vector<std::string>> blocks_of(const Dfa& m, const Partition& p) {
std::vector<std::vector<std::string>> blocks(static_cast<std::size_t>(p.count));
for (const std::string& state : m.states) {
blocks[static_cast<std::size_t>(p.block.at(state))].push_back(state);
}
return blocks;
}
// Agrupa los estados que tienen la misma firma. Es el único lugar donde se numeran bloques.
inline Partition group_by(const Dfa& m, const std::map<std::string, std::vector<int>>& signature) {
Partition result;
std::map<std::vector<int>, int> number; // firma → bloque
for (const std::string& state : m.states) {
const std::vector<int>& key = signature.at(state);
auto found = number.find(key);
if (found == number.end()) {
found = number.insert({key, result.count}).first;
result.count++;
}
result.block[state] = found->second;
}
return result;
}
// La partición de partida: los estados de aceptación por un lado y los demás por otro.
// Son los estados que la cadena vacía ya separa. Si F = ∅ o F = Q sale un solo bloque.
inline Partition initial_partition(const Dfa& m) {
std::map<std::string, std::vector<int>> signature;
for (const std::string& state : m.states) {
signature[state] = {m.accept.count(state) > 0 ? 1 : 0};
}
return group_by(m, signature);
}
// Una ronda. Dos estados siguen juntos si estaban en el mismo bloque y, con cada símbolo,
// van a parar al mismo bloque. La firma de un estado es la lista
// (su bloque, el bloque de δ(q, a1), el bloque de δ(q, a2), ...).
inline Partition refine(const Dfa& m, const Partition& p) {
std::map<std::string, std::vector<int>> signature;
for (const std::string& state : m.states) {
std::vector<int> key = {p.block.at(state)};
for (char a : m.alphabet) {
key.push_back(p.block.at(step(m, state, a)));
}
signature[state] = key;
}
return group_by(m, signature);
}
// Todas las particiones del algoritmo: P0 = {F, Q − F}, P1, P2, ... La última es la primera
// que una ronda ya no cambia. Como cada ronda solo parte bloques, basta comparar cuántos hay.
inline std::vector<Partition> moore_rounds(const Dfa& m) {
std::vector<Partition> rounds = {initial_partition(m)};
while (true) {
Partition next = refine(m, rounds.back());
if (next.count == rounds.back().count) {
return rounds;
}
rounds.push_back(next);
}
}
// El nombre de un bloque: el del estado si está solo, o {q0,q4} si son varios.
inline std::string block_name(const std::vector<std::string>& states) {
if (states.size() == 1) {
return states[0];
}
std::string name = "{";
for (std::size_t i = 0; i < states.size(); i++) {
name += (i > 0 ? "," : "") + states[i];
}
return name + "}";
}
// El autómata cociente: un estado por bloque. δ'([q], a) = [δ(q, a)], el inicial es el bloque
// de q0 y un bloque es de aceptación si sus estados lo son. Solo está bien definido si la
// partición es estable (refine ya no la cambia) y no mezcla estados de F con estados de Q − F.
inline Dfa quotient(const Dfa& m, const Partition& p) {
std::vector<std::vector<std::string>> blocks = blocks_of(m, p);
std::vector<std::string> names;
for (const std::vector<std::string>& block : blocks) {
names.push_back(block_name(block));
}
Dfa result;
result.states = names;
result.alphabet = m.alphabet;
result.start = names[static_cast<std::size_t>(p.block.at(m.start))];
for (std::size_t i = 0; i < blocks.size(); i++) {
const std::string& representative = blocks[i][0];
if (m.accept.count(representative) > 0) {
result.accept.insert(names[i]);
}
for (char a : m.alphabet) {
int target = p.block.at(step(m, representative, a));
result.delta[{names[i], a}] = names[static_cast<std::size_t>(target)];
}
}
check_dfa(result);
return result;
}
// El DFA mínimo de L(m): quitar los inalcanzables, refinar hasta que no cambie, y fusionar.
inline Dfa minimize(const Dfa& m) {
Dfa trimmed = remove_unreachable(m);
return quotient(trimmed, moore_rounds(trimmed).back());
}
// ------------------------------------------------------------
// Comparar dos DFA
// ------------------------------------------------------------
// ¿Son la misma máquina salvo los nombres de los estados? Si lo son, la correspondencia está
// forzada: el inicial va al inicial y, si p va a q, entonces δ1(p, a) va a δ2(q, a). Se
// recorre desde los iniciales y se comprueba que no haya contradicciones.
// Se asume que todos los estados de las dos máquinas son alcanzables.
inline bool isomorphic(const Dfa& m1, const Dfa& m2) {
std::set<char> sigma1(m1.alphabet.begin(), m1.alphabet.end());
std::set<char> sigma2(m2.alphabet.begin(), m2.alphabet.end());
if (sigma1 != sigma2 || m1.states.size() != m2.states.size()) {
return false;
}
std::map<std::string, std::string> to2 = {{m1.start, m2.start}};
std::map<std::string, std::string> to1 = {{m2.start, m1.start}};
std::queue<std::string> pending;
pending.push(m1.start);
while (!pending.empty()) {
std::string p = pending.front();
pending.pop();
const std::string& q = to2.at(p);
if ((m1.accept.count(p) > 0) != (m2.accept.count(q) > 0)) {
return false;
}
for (char a : m1.alphabet) {
const std::string& p_next = step(m1, p, a);
const std::string& q_next = step(m2, q, a);
auto seen1 = to2.find(p_next);
auto seen2 = to1.find(q_next);
if (seen1 == to2.end() && seen2 == to1.end()) {
to2[p_next] = q_next;
to1[q_next] = p_next;
pending.push(p_next);
} else if (seen1 == to2.end() || seen2 == to1.end() || seen1->second != q_next) {
return false;
}
}
}
return to2.size() == m1.states.size();
}
// ¿L(m1) = L(m2)? Se minimizan los dos y se comparan: el DFA mínimo es único salvo nombres.
inline bool equivalent(const Dfa& m1, const Dfa& m2) {
return isomorphic(minimize(m1), minimize(m2));
}
// La cadena más corta que uno acepta y el otro no, o nada si reconocen el mismo lenguaje.
// Recorre a lo ancho los pares (p, q) a los que se llega leyendo lo mismo en las dos máquinas.
inline std::optional<std::string> difference_witness(const Dfa& m1, const Dfa& m2) {
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("para comparar dos DFA hace falta el mismo alfabeto");
}
using Pair = std::pair<std::string, std::string>;
std::map<Pair, std::string> reached = {{{m1.start, m2.start}, ""}};
std::queue<Pair> pending;
pending.push({m1.start, m2.start});
while (!pending.empty()) {
Pair current = pending.front();
pending.pop();
std::string w = reached.at(current);
if ((m1.accept.count(current.first) > 0) != (m2.accept.count(current.second) > 0)) {
return w;
}
for (char a : m1.alphabet) {
Pair next = {step(m1, current.first, a), step(m2, current.second, a)};
if (reached.count(next) == 0) {
reached[next] = w + a;
pending.push(next);
}
}
}
return std::nullopt;
}
// ------------------------------------------------------------
// El k-ésimo símbolo desde el final es 1
// ------------------------------------------------------------
// El DFA que recuerda los últimos k símbolos leídos: 2^k estados, que se llaman como esos k
// símbolos. Antes de leer k símbolos, los que faltan cuentan como 0, así que el inicial es
// 0^k. Acepta si el más antiguo de los k es un 1. Es el autómata que da la construcción de
// subconjuntos de la semana 2 con otros nombres; aquí se construye directamente.
inline Dfa last_k_dfa(int k) {
if (k < 1 || k > 16) {
throw std::runtime_error("k debe estar entre 1 y 16");
}
Dfa m;
m.alphabet = {'0', '1'};
std::size_t width = static_cast<std::size_t>(k);
m.start = std::string(width, '0');
for (unsigned value = 0; value < (1u << k); value++) {
std::string name(width, '0');
for (std::size_t i = 0; i < width; i++) {
if ((value >> (width - 1 - i)) & 1u) {
name[i] = '1';
}
}
m.states.push_back(name);
if (name[0] == '1') {
m.accept.insert(name);
}
for (char a : m.alphabet) {
m.delta[{name, a}] = name.substr(1) + a; // se olvida el más antiguo y entra a
}
}
check_dfa(m);
return m;
}
#endif// La división del lema de bombeo, sacada de un DFA: pump ARCHIVO.dfa CADENA [VECES]
// La cadena debe tener al menos |Q| símbolos. Busca el primer estado que se repite en la
// ejecución, parte la cadena en x, y, z y sigue x y^i z para i = 0, 1, ..., VECES (4 si no se dice).
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include "dfa.h"
#include "pumping.h"
static std::string shown(const std::string& w) {
return w.empty() ? "ε" : w;
}
int main(int argc, char** argv) {
if (argc != 3 && argc != 4) {
std::cerr << "uso: pump ARCHIVO.dfa CADENA [VECES]\n";
return 2;
}
try {
Dfa m = load_dfa(argv[1]);
std::string w = argv[2];
std::size_t times = (argc == 4) ? std::stoul(argv[3]) : 4;
std::size_t p = m.states.size();
PumpSplit found = pump_split(m, w);
const Split& split = found.split;
std::vector<std::string> sequence = run(m, w);
std::cout << "p = |Q| = " << p << ", w = " << w << ", |w| = " << w.size() << "\n " << sequence[0];
for (std::size_t k = 0; k < w.size(); k++) {
std::cout << " -" << w[k] << "-> " << sequence[k + 1];
}
std::cout << "\nprimer estado que se repite: " << found.state << ", después de leer " << found.first << " y "
<< found.second << " símbolos\n";
std::cout << "x = " << shown(split.x) << ", y = " << shown(split.y) << ", z = " << shown(split.z)
<< " |y| = " << split.y.size() << " > 0, |xy| = " << split.x.size() + split.y.size()
<< " ≤ " << p << '\n';
bool original = accepts(m, w);
bool all_same = true;
for (std::size_t i = 0; i <= times; i++) {
std::string s = pumped(split, i);
std::string last = delta_star(m, m.start, s);
bool ok = m.accept.count(last) > 0;
all_same = all_same && ok == original;
std::cout << " i = " << i << ": " << shown(s) << " termina en " << last << (ok ? ", acepta" : ", rechaza")
<< '\n';
}
std::cout << (all_same ? "todas terminan igual que w" : "ERROR: alguna termina distinto que w") << '\n';
return all_same ? 0 : 1;
} catch (const std::exception& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// El juego del lema de bombeo, jugado completo para un p concreto: pumping_game PARTIDA P
// Nosotros elegimos la cadena s (que depende de p) y el exponente i. El programa recorre
// todas las divisiones que el adversario puede elegir, con |xy| ≤ p y |y| > 0, y dice en cuáles
// x y^i z quedó fuera del lenguaje. Sin argumentos, lista las partidas.
// Jugar con un p no demuestra nada: la demostración tiene que valer para todo p. Sirve para
// encontrar el error en una demostración antes de escribirla.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include "pumping.h"
static std::string shown(const std::string& w) {
return w.empty() ? "ε" : w;
}
static std::string padded(const std::string& text, std::size_t width) {
std::size_t columns = (text == "ε") ? 1 : text.size();
return text + std::string(width > columns ? width - columns : 0, ' ');
}
int main(int argc, char** argv) {
std::vector<Game> games = chapter_games();
if (argc != 3) {
std::cerr << "uso: pumping_game PARTIDA P\npartidas:";
for (const Game& game : games) {
std::cerr << ' ' << game.name;
}
std::cerr << '\n';
return 2;
}
try {
std::string name = argv[1];
std::size_t p = std::stoul(argv[2]);
for (const Game& game : games) {
if (game.name != name) {
continue;
}
std::string s = game.choose_string(p);
std::vector<Split> splits = legal_splits(s, p);
std::cout << "L = " << game.language << "\nel adversario elige p = " << p << "\nnosotros elegimos s = "
<< shown(s) << ", con |s| = " << s.size() << (game.in_language(s) ? " y s ∈ L" : " y s ∉ L")
<< "\nnuestro exponente: i = " << game.exponent << "\ndivisiones posibles con |xy| ≤ " << p
<< " y |y| > 0: " << splits.size() << '\n';
std::size_t wx = 1, wy = 1, wz = 1, wr = 7;
for (const Split& split : splits) {
wr = std::max(wr, pumped(split, game.exponent).size());
wx = std::max(wx, split.x.size());
wy = std::max(wy, split.y.size());
wz = std::max(wz, split.z.size());
}
std::cout << " " << padded("x", wx) << " " << padded("y", wy) << " " << padded("z", wz)
<< " x y^i z\n";
std::size_t survive = 0;
for (const Split& split : splits) {
std::string result = pumped(split, game.exponent);
bool inside = game.in_language(result);
survive += inside ? 1 : 0;
std::cout << " " << padded(shown(split.x), wx) << " " << padded(split.y, wy) << " "
<< padded(shown(split.z), wz) << " " << padded(shown(result), wr)
<< (inside ? " ∈ L: el adversario resiste" : " ∉ L") << '\n';
}
if (survive == 0) {
std::cout << "en las " << splits.size() << " divisiones la cadena bombeada sale de L\n";
} else {
std::cout << "el adversario tiene " << survive << (survive == 1 ? " división" : " divisiones")
<< " que resiste" << (survive == 1 ? "" : "n") << ": con esta jugada no se demuestra nada\n";
}
return 0;
}
std::cerr << "no hay una partida llamada " << name << '\n';
return 2;
} catch (const std::exception& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// El lema de bombeo, de los dos lados.
// Con un DFA: dada una cadena aceptada de longitud al menos |Q|, encontrar la división x, y, z
// que promete el lema, buscando el primer estado que se repite en la ejecución.
// Sin DFA: el juego contra el adversario para un lenguaje dado por una función que decide.
#ifndef PUMPING_H
#define PUMPING_H
#include <cstddef>
#include <functional>
#include <map>
#include <stdexcept>
#include <string>
#include <vector>
#include "dfa.h"
// Una división s = xyz.
struct Split {
std::string x, y, z;
};
// y repetida i veces.
inline std::string repeat(const std::string& y, std::size_t i) {
std::string result;
for (std::size_t k = 0; k < i; k++) {
result += y;
}
return result;
}
// x y^i z
inline std::string pumped(const Split& split, std::size_t i) {
return split.x + repeat(split.y, i) + split.z;
}
// ------------------------------------------------------------
// Con un DFA: de dónde sale la división
// ------------------------------------------------------------
struct PumpSplit {
Split split;
std::string state; // el estado que se repite
std::size_t first = 0; // se visita después de leer first símbolos...
std::size_t second = 0; // ...y otra vez después de leer second, con first < second ≤ |Q|
};
// La demostración del lema, ejecutada. La ejecución de M con w empieza con los estados
// r0, r1, ..., rp, donde p = |Q|: son p + 1 estados y solo hay p distintos, así que dos
// coinciden. Se toma la primera repetición: x es lo leído hasta la primera visita, y lo leído
// entre las dos visitas, z el resto. Pide |w| ≥ |Q|; no pide que M acepte w.
inline PumpSplit pump_split(const Dfa& m, const std::string& w) {
std::size_t p = m.states.size();
if (w.size() < p) {
throw std::runtime_error("la cadena debe tener al menos |Q| = " + std::to_string(p) + " símbolos");
}
std::vector<std::string> sequence = run(m, w);
std::map<std::string, std::size_t> seen; // estado → después de cuántos símbolos se visitó
for (std::size_t j = 0; j <= p; j++) {
auto earlier = seen.find(sequence[j]);
if (earlier != seen.end()) {
std::size_t i = earlier->second;
PumpSplit result;
result.split = {w.substr(0, i), w.substr(i, j - i), w.substr(j)};
result.state = sequence[j];
result.first = i;
result.second = j;
return result;
}
seen[sequence[j]] = j;
}
throw std::logic_error("imposible: p + 1 estados sin repetición"); // principio del palomar
}
// ------------------------------------------------------------
// Sin DFA: el juego
// ------------------------------------------------------------
// Todas las divisiones s = xyz que el adversario puede elegir: |y| > 0 y |xy| ≤ p.
// Si |s| ≥ p son p(p + 1)/2.
inline std::vector<Split> legal_splits(const std::string& s, std::size_t p) {
std::vector<Split> result;
for (std::size_t x_len = 0; x_len < s.size() && x_len < p; x_len++) {
for (std::size_t y_len = 1; x_len + y_len <= p && x_len + y_len <= s.size(); y_len++) {
result.push_back({s.substr(0, x_len), s.substr(x_len, y_len), s.substr(x_len + y_len)});
}
}
return result;
}
// Una partida: el lenguaje, y nuestras dos jugadas. La cadena depende de p. El exponente
// puede depender de p y de la división, aunque en los ejemplos del capítulo es fijo.
struct Game {
std::string name; // para la línea de comandos
std::string language; // cómo se muestra L
std::function<bool(const std::string&)> in_language;
std::function<std::string(std::size_t)> choose_string;
std::size_t exponent = 2;
};
// ¿Cuántos unos y ceros?
inline std::size_t count_symbol(const std::string& w, char a) {
std::size_t total = 0;
for (char c : w) {
total += (c == a) ? 1 : 0;
}
return total;
}
// ¿w es de la forma a^i b^j, con a antes que b?
inline bool is_block_pair(const std::string& w, char a, char b) {
std::size_t i = 0;
while (i < w.size() && w[i] == a) {
i++;
}
while (i < w.size() && w[i] == b) {
i++;
}
return i == w.size();
}
inline bool in_zeros_ones(const std::string& w) { // { 0^n 1^n }
return is_block_pair(w, '0', '1') && count_symbol(w, '0') == count_symbol(w, '1');
}
inline bool in_equal(const std::string& w) { // tantos ceros como unos, en cualquier orden
return count_symbol(w, '0') + count_symbol(w, '1') == w.size() &&
count_symbol(w, '0') == count_symbol(w, '1');
}
inline bool in_ww(const std::string& s) { // { ww }
std::size_t half = s.size() / 2;
return s.size() % 2 == 0 && s.substr(0, half) == s.substr(half);
}
inline bool in_squares(const std::string& w) { // { 0^(n²) }
if (count_symbol(w, '0') != w.size()) {
return false;
}
std::size_t n = 0;
while (n * n < w.size()) {
n++;
}
return n * n == w.size();
}
inline bool in_more_zeros(const std::string& w) { // { 0^i 1^j : i > j }
return is_block_pair(w, '0', '1') && count_symbol(w, '0') > count_symbol(w, '1');
}
// { a^i b^j c^k : si i = 1 entonces j = k }. No es regular y aun así cumple el lema con p = 2.
inline bool in_trap(const std::string& w) {
std::size_t pos = 0;
std::size_t counts[3] = {0, 0, 0};
for (int letter = 0; letter < 3; letter++) {
while (pos < w.size() && w[pos] == static_cast<char>('a' + letter)) {
counts[letter]++;
pos++;
}
}
return pos == w.size() && (counts[0] != 1 || counts[1] == counts[2]);
}
// La división con la que el adversario gana siempre en el lenguaje anterior, para |s| ≥ 2:
// y es la primera letra, salvo si s empieza con exactamente dos a, en cuyo caso y = aa.
inline Split trap_split(const std::string& s) {
bool two_a = s.size() >= 2 && s[0] == 'a' && s[1] == 'a' && (s.size() == 2 || s[2] != 'a');
std::size_t y_len = two_a ? 2 : 1;
return {"", s.substr(0, y_len), s.substr(y_len)};
}
// Las partidas del capítulo. Las que terminan en -mal usan una cadena o un exponente mal
// elegidos: el adversario tiene una división que resiste.
inline std::vector<Game> chapter_games() {
auto zeros_ones = [](std::size_t p) { return std::string(p, '0') + std::string(p, '1'); };
return {
{"0n1n", "{ 0^n 1^n : n ≥ 0 }", in_zeros_ones, zeros_ones, 2},
{"iguales", "{ w : w tiene tantos 0 como 1 }", in_equal, zeros_ones, 2},
{"iguales-mal", "{ w : w tiene tantos 0 como 1 }", in_equal,
[](std::size_t p) { return repeat("01", p); }, 2},
{"ww", "{ ww : w ∈ {0,1}* }", in_ww,
[](std::size_t p) { return std::string(p, '0') + "1" + std::string(p, '0') + "1"; }, 2},
{"ww-mal", "{ ww : w ∈ {0,1}* }", in_ww, [](std::size_t p) { return std::string(2 * p, '0'); }, 2},
{"cuadrados", "{ 0^(n²) : n ≥ 0 }", in_squares, [](std::size_t p) { return std::string(p * p, '0'); }, 2},
{"mas-ceros", "{ 0^i 1^j : i > j }", in_more_zeros,
[](std::size_t p) { return std::string(p + 1, '0') + std::string(p, '1'); }, 0},
{"mas-ceros-mal", "{ 0^i 1^j : i > j }", in_more_zeros,
[](std::size_t p) { return std::string(p + 1, '0') + std::string(p, '1'); }, 2},
};
}
// Las divisiones con las que el adversario resiste nuestro exponente: x y^i z sigue en L.
inline std::vector<Split> surviving_splits(const Game& game, std::size_t p) {
std::vector<Split> result;
for (const Split& split : legal_splits(game.choose_string(p), p)) {
if (game.in_language(pumped(split, game.exponent))) {
result.push_back(split);
}
}
return result;
}
#endif// Sigue un DFA con una o más cadenas: run_dfa ARCHIVO.dfa CADENA...
// Con - en lugar del archivo, lee la descripción de la entrada estándar.
// La cadena vacía se pasa como '' en la terminal.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include "dfa.h"
int main(int argc, char** argv) {
if (argc < 3) {
std::cerr << "uso: run_dfa ARCHIVO.dfa CADENA...\n";
return 2;
}
try {
std::string path = argv[1];
Dfa m = (path == "-") ? read_dfa(std::cin) : load_dfa(path);
for (int i = 2; i < argc; i++) {
std::string w = argv[i];
std::vector<std::string> sequence = run(m, w);
std::cout << "w = " << (w.empty() ? "ε" : w) << "\n " << sequence[0];
for (std::size_t k = 0; k < w.size(); k++) {
std::cout << " -" << w[k] << "-> " << sequence[k + 1];
}
const std::string& last = sequence.back();
bool ok = m.accept.count(last) > 0;
std::cout << "\n termina en " << last << (ok ? ", que está en F: acepta" : ", que no está en F: rechaza")
<< '\n';
}
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Muestra un DFA como quíntupla y como tabla de transiciones: show_dfa ARCHIVO.dfa
// En la tabla, -> marca el estado inicial y * los estados de aceptación.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include "dfa.h"
static std::string padded(const std::string& text, std::size_t width) {
return text + std::string(width > text.size() ? width - text.size() : 0, ' ');
}
int main(int argc, char** argv) {
if (argc != 2) {
std::cerr << "uso: show_dfa ARCHIVO.dfa\n";
return 2;
}
try {
Dfa m = load_dfa(argv[1]);
std::cout << "Q = {";
for (std::size_t i = 0; i < m.states.size(); i++) {
std::cout << (i > 0 ? ", " : "") << m.states[i];
}
std::cout << "}\nΣ = {";
for (std::size_t i = 0; i < m.alphabet.size(); i++) {
std::cout << (i > 0 ? ", " : "") << m.alphabet[i];
}
std::cout << "}\nq0 = " << m.start << "\nF = {";
bool first = true;
for (const std::string& state : m.states) {
if (m.accept.count(state) > 0) {
std::cout << (first ? "" : ", ") << state;
first = false;
}
}
std::cout << "}\n\n";
std::size_t width = 1;
for (const std::string& state : m.states) {
width = std::max(width, state.size());
}
// La última columna va sin relleno, para no dejar espacios al final de la línea.
std::cout << " " << padded("δ", width + 1); // δ ocupa dos bytes y una columna
for (std::size_t i = 0; i < m.alphabet.size(); i++) {
std::string symbol(1, m.alphabet[i]);
std::cout << " " << (i + 1 < m.alphabet.size() ? padded(symbol, width) : symbol);
}
std::cout << '\n';
for (const std::string& state : m.states) {
std::cout << (state == m.start ? "-> " : " ") << (m.accept.count(state) > 0 ? "* " : " ")
<< padded(state, width);
for (std::size_t i = 0; i < m.alphabet.size(); i++) {
const std::string& target = step(m, state, m.alphabet[i]);
std::cout << " " << (i + 1 < m.alphabet.size() ? padded(target, width) : target);
}
std::cout << '\n';
}
std::cout << "\nestados alcanzables desde " << m.start << ": " << reachable(m).size() << " de "
<< m.states.size() << '\n';
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Dos algoritmos de streaming: leen los datos una sola vez, símbolo por símbolo, y al final
// responden. Toda su memoria está a la vista, para poder contar sus bits.
#ifndef STREAMING_H
#define STREAMING_H
#include <cstdint>
// ¿El k-ésimo símbolo desde el final es 1? Guarda los últimos k bits en un registro: k bits
// de memoria, ni uno más. La cota inferior de los apuntes dice que tampoco puede ser uno menos.
struct Window {
int k = 1; // parámetro del problema, no cuenta como memoria (1 ≤ k ≤ 32)
std::uint32_t bits = 0; // los últimos k símbolos; el más reciente es el bit 0
void read(char a) {
std::uint32_t mask = (k == 32) ? 0xffffffffu : ((1u << k) - 1u);
bits = ((bits << 1) | (a == '1' ? 1u : 0u)) & mask;
}
bool answer() const {
return ((bits >> (k - 1)) & 1u) != 0;
}
};
// ¿Hubo tantos ceros como unos? Guarda la diferencia. Con entradas de longitud a lo sumo n,
// la diferencia está entre -n y n: unos log2(2n + 1) bits. No hay un tope que sirva para toda n.
struct Balance {
std::int64_t difference = 0; // ceros menos unos
void read(char a) {
difference += (a == '0') ? 1 : -1;
}
bool answer() const {
return difference == 0;
}
};
#endif# Cadenas binarias que contienen 1001, escrito con descuido: 8 estados para un lenguaje
# que necesita 5.
# q0: todavía no se leyó nada. q4: no hay avance, y ya se leyó algo.
# q1: lo leído termina en 1. q2: termina en 10. q3: termina en 100.
# q5, q6: ya apareció 1001 (q5 si lo último fue 1, q6 si fue 0).
# q7: quedó de una versión anterior. Ninguna transición llega a él.
states: q0 q1 q2 q3 q4 q5 q6 q7
alphabet: 0 1
start: q0
accept: q5 q6 q7
delta:
q0 0 q4
q0 1 q1
q1 0 q2
q1 1 q1
q2 0 q3
q2 1 q1
q3 0 q4
q3 1 q5
q4 0 q4
q4 1 q1
q5 0 q6
q5 1 q5
q6 0 q6
q6 1 q5
q7 0 q3
q7 1 q7# 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# Un intento de reconocer { 0^n 1^n }: cuenta los ceros hasta 3 y después "muchos".
# z0..z3: se leyeron 0, 1, 2 o "3 o más" ceros y ningún uno.
# u2, u1, u0: faltan 2, 1 o 0 unos. x: estado trampa.
states: z0 z1 z2 z3 u2 u1 u0 x
alphabet: 0 1
start: z0
accept: z0 u0
delta:
z0 0 z1
z0 1 x
z1 0 z2
z1 1 u0
z2 0 z3
z2 1 u1
z3 0 z3
z3 1 u2
u2 0 x
u2 1 u1
u1 0 x
u1 1 u0
u0 0 x
u0 1 x
x 0 x
x 1 x# Cadenas binarias que terminan en 01, recordando de más: el estado es lo leído si tiene
# menos de dos símbolos (e es la cadena vacía), o sus dos últimos símbolos.
states: e 0 1 00 01 10 11
alphabet: 0 1
start: e
accept: 01
delta:
e 0 0
e 1 1
0 0 00
0 1 01
1 0 10
1 1 11
00 0 00
00 1 01
01 0 10
01 1 11
10 0 00
10 1 01
11 0 10
11 1 11# 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# El símbolo número 3 desde el final es 1. El estado es lo último que se leyó:
# 3 símbolos, contando como 0 los que todavía no llegaron.
states: 000 001 010 011 100 101 110 111
alphabet: 0 1
start: 000
accept: 100 101 110 111
delta:
000 0 000
000 1 001
001 0 010
001 1 011
010 0 100
010 1 101
011 0 110
011 1 111
100 0 000
100 1 001
101 0 010
101 1 011
110 0 100
110 1 101
111 0 110
111 1 111# Múltiplos de 3 en binario, llevando el resto entre 6 en vez del resto entre 3.
# El estado sK dice que el valor de lo leído deja resto K al dividirlo entre 6.
states: s0 s1 s2 s3 s4 s5
alphabet: 0 1
start: s0
accept: s0 s3
delta:
s0 0 s0
s0 1 s1
s1 0 s2
s1 1 s3
s2 0 s4
s2 1 s5
s3 0 s0
s3 1 s1
s4 0 s2
s4 1 s3
s5 0 s4
s5 1 s5# Cadenas binarias que, leídas como un número en base 2, dan un múltiplo de 3.
# La cadena vacía vale 0. El estado rK dice que el valor de lo leído deja resto K al dividir entre 3.
states: r0 r1 r2
alphabet: 0 1
start: r0
accept: r0
delta:
r0 0 r0
r0 1 r1
r1 0 r2
r1 1 r0
r2 0 r1
r2 1 r2Pruebas
Comprueban lo que afirman los apuntes; se ejecutan con make test.
// Pruebas de las cadenas distinguibles, de la cota 2^k y del autómata de las clases.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <optional>
#include <string>
#include <vector>
#include "dfa.h"
#include "distinguish.h"
#include "minimize.h"
#include "pumping.h"
#include "streaming.h"
// ¿El k-ésimo símbolo desde el final de w es 1? Mirando la cadena completa.
static bool kth_from_end_is_one(const std::string& w, std::size_t k) {
return w.size() >= k && w[w.size() - k] == '1';
}
// { 0^n 1^n } en tres líneas: 0^i y 0^j se distinguen con 1^i.
static void test_zeros_ones() {
for (std::size_t i = 0; i < 20; i++) {
for (std::size_t j = 0; j < 20; j++) {
std::string x(i, '0'), y(j, '0'), z(i, '1');
assert(in_zeros_ones(x + z));
assert(in_zeros_ones(y + z) == (i == j));
}
}
}
// La deuda de la semana 2: las 2^k cadenas de longitud k son distinguibles dos a dos.
static void test_last_k() {
for (int k = 1; k <= 6; k++) {
std::size_t width = static_cast<std::size_t>(k);
Dfa m = last_k_dfa(k);
assert(m.states.size() == (std::size_t{1} << k));
// El autómata reconoce el lenguaje.
for (const std::string& w : all_strings({'0', '1'}, 10)) {
assert(accepts(m, w) == kth_from_end_is_one(w, width));
}
std::vector<std::string> strings;
for (const std::string& w : all_strings({'0', '1'}, width)) {
if (w.size() == width) {
strings.push_back(w);
}
}
assert(strings.size() == (std::size_t{1} << k));
// El sufijo de los apuntes: si x e y difieren en la posición i (desde 1), z = 0^(i-1).
for (const std::string& x : strings) {
for (const std::string& y : strings) {
for (std::size_t i = 1; i <= width; i++) {
if (x[i - 1] == y[i - 1]) {
continue;
}
std::string z(i - 1, '0');
assert(kth_from_end_is_one(x + z, width) == (x[i - 1] == '1'));
assert(kth_from_end_is_one(y + z, width) == (y[i - 1] == '1'));
assert(separates(m, x, y, z));
}
}
}
assert(pairwise_distinguishable(m, strings));
// Y entonces ningún estado sobra: el mínimo tiene 2^k.
assert(minimize(m).states.size() == (std::size_t{1} << k));
}
// El archivo de machines/ es el autómata de k = 3, y la tabla de los apuntes.
Dfa three = load_dfa("machines/last_3.dfa");
assert(isomorphic(three, last_k_dfa(3)));
assert(*distinguishing_suffix(three, "000", "001") == "00");
assert(*distinguishing_suffix(three, "000", "010") == "0");
assert(*distinguishing_suffix(three, "011", "100") == "");
assert(*distinguishing_suffix(three, "110", "111") == "00");
}
// La fuerza bruta y el recorrido de pares de estados dan lo mismo.
static void test_brute_force() {
for (const char* path : {"machines/ends_01.dfa", "machines/contains_101.dfa", "machines/multiple_of_3.dfa",
"machines/ends_01_seven.dfa", "machines/contains_1001.dfa",
"machines/count_attempt.dfa", "machines/last_3.dfa"}) {
Dfa m = load_dfa(path);
std::vector<std::string> strings = all_strings(m.alphabet, 3);
for (const std::string& x : strings) {
for (const std::string& y : strings) {
std::size_t tried = 0;
std::optional<std::string> brute = brute_distinguishing_suffix(m, x, y, m.states.size() - 1, tried);
std::optional<std::string> fast = distinguishing_suffix(m, x, y);
assert(brute.has_value() == fast.has_value());
if (brute) {
assert(brute->size() == fast->size()); // los dos son de longitud mínima
assert(separates(m, x, y, *brute) && separates(m, x, y, *fast));
}
// Dos cadenas que llegan al mismo estado no se pueden distinguir.
if (delta_star(m, m.start, x) == delta_star(m, m.start, y)) {
assert(!fast);
}
}
}
}
// Las salidas copiadas en los apuntes.
Dfa m = load_dfa("machines/contains_1001.dfa");
std::size_t tried = 0;
assert(!brute_distinguishing_suffix(m, "", "0", 7, tried) && tried == 255);
assert(*brute_distinguishing_suffix(m, "", "1", 7, tried) == "001" && tried == 9);
Dfa three = load_dfa("machines/last_3.dfa");
assert(*brute_distinguishing_suffix(three, "011", "001", 7, tried) == "0" && tried == 2);
}
// Myhill-Nerode: el autómata de las clases es el DFA mínimo, salvo los nombres.
static void test_nerode() {
for (const char* path : {"machines/ends_01.dfa", "machines/contains_101.dfa", "machines/multiple_of_3.dfa",
"machines/ends_01_seven.dfa", "machines/contains_1001.dfa",
"machines/count_attempt.dfa", "machines/last_3.dfa",
"machines/multiple_of_3_mod6.dfa"}) {
Dfa m = load_dfa(path);
Classes classes = nerode_classes(m);
Dfa by_classes = nerode_dfa(m);
assert(by_classes.states.size() == classes.representatives.size());
// Los representantes son distinguibles dos a dos, y toda cadena cae en una clase.
assert(pairwise_distinguishable(m, classes.representatives));
for (const std::string& w : all_strings(m.alphabet, 7)) {
std::optional<std::string> r = class_of(m, classes, w);
assert(r.has_value());
// δ*([ε], w) = [w]
assert(delta_star(by_classes, by_classes.start, w) == class_name(*r));
assert(accepts(by_classes, w) == accepts(m, w));
}
assert(isomorphic(by_classes, minimize(m)));
}
Dfa seven = load_dfa("machines/ends_01_seven.dfa");
assert(nerode_classes(seven).representatives == (std::vector<std::string>{"", "0", "01"}));
assert(isomorphic(nerode_dfa(seven), load_dfa("machines/ends_01.dfa")));
}
// Streaming: el registro de k bits responde lo mismo que el DFA de 2^k estados, y sus 2^k
// contenidos posibles son exactamente los estados.
static void test_streaming() {
for (int k = 1; k <= 6; k++) {
Dfa m = last_k_dfa(k);
for (const std::string& w : all_strings({'0', '1'}, 10)) {
Window window;
window.k = k;
Balance balance;
for (char a : w) {
window.read(a);
balance.read(a);
}
assert(window.answer() == accepts(m, w));
assert(balance.answer() == in_equal(w));
// El contenido del registro, escrito con k dígitos, es el nombre del estado.
std::string name(static_cast<std::size_t>(k), '0');
for (int i = 0; i < k; i++) {
if ((window.bits >> (k - 1 - i)) & 1u) {
name[static_cast<std::size_t>(i)] = '1';
}
}
assert(name == delta_star(m, m.start, w));
}
}
// Con entradas de longitud a lo sumo n, las cadenas 0^0, ..., 0^(n/2) son distinguibles
// dos a dos con sufijos que no pasan de la longitud n: 0^i 1^i mide 2i ≤ n.
std::size_t n = 20;
for (std::size_t i = 0; i <= n / 2; i++) {
for (std::size_t j = 0; j < i; j++) {
std::string z(j, '1'); // el sufijo es el del más corto de los dos
assert(std::string(i, '0').size() + z.size() <= n);
assert(in_equal(std::string(j, '0') + z) && !in_equal(std::string(i, '0') + z));
}
}
}
int main() {
test_zeros_ones();
test_last_k();
test_brute_force();
test_nerode();
test_streaming();
std::printf("test_distinguish: ok\n");
}// Pruebas de la minimización: las particiones de los apuntes, que el resultado es equivalente
// al original y que no se puede reducir más.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <optional>
#include <random>
#include <set>
#include <string>
#include <vector>
#include "dfa.h"
#include "distinguish.h"
#include "minimize.h"
using Blocks = std::vector<std::vector<std::string>>;
static bool same_up_to(const Dfa& m1, const Dfa& m2, std::size_t max_len) {
for (const std::string& w : all_strings(m1.alphabet, max_len)) {
if (accepts(m1, w) != accepts(m2, w)) {
return false;
}
}
return true;
}
// Lo que tiene que cumplir el resultado de minimize, sea cual sea la máquina.
static void check_minimal(const Dfa& m, std::size_t expected_states, std::size_t max_len) {
Dfa minimal = minimize(m);
assert(minimal.states.size() == expected_states);
// Equivalente: con todas las cadenas hasta max_len, y sin límite con el recorrido de pares.
assert(same_up_to(m, minimal, max_len));
assert(!difference_witness(m, minimal));
// Mínimo: todos sus estados son alcanzables y distinguibles dos a dos.
assert(reachable(minimal).size() == minimal.states.size());
for (const std::string& p : minimal.states) {
for (const std::string& q : minimal.states) {
assert((p == q) == !state_distinguishing_suffix(minimal, p, q));
}
}
// Minimizar otra vez no cambia nada, y coincide con el autómata de las clases.
assert(isomorphic(minimal, minimize(minimal)));
assert(isomorphic(minimal, nerode_dfa(m)));
assert(equivalent(m, minimal));
}
// El ejemplo paso a paso de los apuntes.
static void test_contains_1001() {
Dfa m = load_dfa("machines/contains_1001.dfa");
assert(m.states.size() == 8 && reachable(m).size() == 7 && reachable(m).count("q7") == 0);
Dfa trimmed = remove_unreachable(m);
std::vector<Partition> rounds = moore_rounds(trimmed);
assert(rounds.size() == 4); // P0, P1, P2, P3; la ronda 4 ya no cambia nada
assert(blocks_of(trimmed, rounds[0]) == (Blocks{{"q0", "q1", "q2", "q3", "q4"}, {"q5", "q6"}}));
assert(blocks_of(trimmed, rounds[1]) == (Blocks{{"q0", "q1", "q2", "q4"}, {"q3"}, {"q5", "q6"}}));
assert(blocks_of(trimmed, rounds[2]) == (Blocks{{"q0", "q1", "q4"}, {"q2"}, {"q3"}, {"q5", "q6"}}));
assert(blocks_of(trimmed, rounds[3]) == (Blocks{{"q0", "q4"}, {"q1"}, {"q2"}, {"q3"}, {"q5", "q6"}}));
assert(refine(trimmed, rounds[3]) == rounds[3]);
// P_k junta exactamente a los estados que ningún sufijo de longitud ≤ k separa.
for (std::size_t k = 0; k < rounds.size(); k++) {
for (const std::string& p : trimmed.states) {
for (const std::string& q : trimmed.states) {
std::optional<std::string> z = state_distinguishing_suffix(trimmed, p, q);
bool separated_by_short = z.has_value() && z->size() <= k;
assert((rounds[k].block.at(p) == rounds[k].block.at(q)) == !separated_by_short);
}
}
}
check_minimal(m, 5, 12);
Dfa minimal = minimize(m);
assert(minimal.states == (std::vector<std::string>{"{q0,q4}", "q1", "q2", "q3", "{q5,q6}"}));
assert(minimal.start == "{q0,q4}" && minimal.accept == (std::set<std::string>{"{q5,q6}"}));
for (const std::string& w : all_strings({'0', '1'}, 12)) {
assert(accepts(minimal, w) == (w.find("1001") != std::string::npos));
}
// q0 y q1 "se parecen" y no son equivalentes: el sufijo más corto que los separa mide 3.
assert(*state_distinguishing_suffix(m, "q0", "q1") == "001");
assert(!state_distinguishing_suffix(m, "q0", "q4"));
assert(!state_distinguishing_suffix(m, "q5", "q6"));
// Sin quitar q7 primero, el resultado tiene un estado de más: 6.
std::vector<Partition> with_all = moore_rounds(m);
assert(with_all.back().count == 6);
Dfa six = quotient(m, with_all.back());
assert(six.states.size() == 6 && same_up_to(six, m, 12) && reachable(six).size() == 5);
}
// Los otros autómatas de machines/.
static void test_machines() {
// El de 7 estados de la semana 1 se reduce al de 3, que es el mismo salvo nombres.
Dfa seven = load_dfa("machines/ends_01_seven.dfa");
Dfa three = load_dfa("machines/ends_01.dfa");
check_minimal(seven, 3, 12);
std::vector<Partition> rounds = moore_rounds(seven);
assert(rounds.size() == 2);
assert(blocks_of(seven, rounds[0]) == (Blocks{{"e", "0", "1", "00", "10", "11"}, {"01"}}));
assert(blocks_of(seven, rounds[1]) == (Blocks{{"e", "1", "11"}, {"0", "00", "10"}, {"01"}}));
assert(isomorphic(minimize(seven), three));
assert(equivalent(seven, three));
Dfa mod6 = load_dfa("machines/multiple_of_3_mod6.dfa");
check_minimal(mod6, 3, 12);
assert(isomorphic(minimize(mod6), load_dfa("machines/multiple_of_3.dfa")));
// Ya eran mínimos.
check_minimal(three, 3, 12);
check_minimal(load_dfa("machines/contains_101.dfa"), 4, 12);
check_minimal(load_dfa("machines/multiple_of_3.dfa"), 3, 12);
check_minimal(load_dfa("machines/count_attempt.dfa"), 8, 12);
check_minimal(load_dfa("machines/last_3.dfa"), 8, 12);
// Dos lenguajes distintos, y la cadena más corta que los separa.
Dfa a = load_dfa("machines/contains_101.dfa");
Dfa b = load_dfa("machines/contains_1001.dfa");
assert(!equivalent(a, b));
assert(*difference_witness(a, b) == "101");
}
// El k-ésimo símbolo desde el final: 2^k estados antes y después, y k − 1 rondas que cambian algo.
static void test_last_k() {
for (int k = 1; k <= 8; k++) {
Dfa m = last_k_dfa(k);
std::vector<Partition> rounds = moore_rounds(m);
assert(rounds.size() == static_cast<std::size_t>(k));
assert(rounds.back().count == (1 << k));
assert(minimize(m).states.size() == (std::size_t{1} << k));
}
check_minimal(last_k_dfa(4), 16, 10);
// El de k = 6, que es el del laboratorio: 64 estados, y el mínimo también.
Dfa six = last_k_dfa(6);
Dfa minimal = minimize(six);
assert(minimal.states.size() == 64 && isomorphic(minimal, six) && !difference_witness(six, minimal));
}
// Casos de borde: F = ∅ y F = Q dan un solo estado.
static void test_edges() {
Dfa m = load_dfa("machines/contains_1001.dfa");
Dfa none = m;
none.accept.clear();
check_minimal(none, 1, 10);
assert(initial_partition(none).count == 1);
Dfa all = m;
all.accept = std::set<std::string>(m.states.begin(), m.states.end());
check_minimal(all, 1, 10);
assert(minimize(all).accept.size() == 1 && minimize(none).accept.empty());
}
// DFA al azar, con semilla fija: el número de estados del mínimo coincide con el número de
// comportamientos distintos, contados por fuerza bruta con todas las cadenas hasta |Q|.
static void test_random() {
std::mt19937 rng(40404);
for (int round = 0; round < 120; round++) {
std::size_t n = 1 + rng() % 7;
std::size_t symbols = 1 + rng() % 3;
Dfa m;
for (std::size_t i = 0; i < n; i++) {
m.states.push_back("s" + std::to_string(i));
}
for (std::size_t a = 0; a < symbols; a++) {
m.alphabet.push_back(static_cast<char>('a' + a));
}
m.start = m.states[rng() % n];
for (const std::string& state : m.states) {
if (rng() % 3 == 0) {
m.accept.insert(state);
}
for (char a : m.alphabet) {
m.delta[{state, a}] = m.states[rng() % n];
}
}
std::vector<std::string> suffixes = all_strings(m.alphabet, n);
std::set<std::vector<bool>> behaviours;
for (const std::string& state : reachable(m)) {
std::vector<bool> behaviour;
for (const std::string& z : suffixes) {
behaviour.push_back(m.accept.count(delta_star(m, state, z)) > 0);
}
behaviours.insert(behaviour);
}
check_minimal(m, behaviours.size(), 7);
// El sufijo más corto que separa dos estados mide a lo sumo |Q| − 1.
for (const std::string& p : m.states) {
for (const std::string& q : m.states) {
std::optional<std::string> z = state_distinguishing_suffix(m, p, q);
assert(!z || z->size() + 1 <= n);
}
}
}
}
int main() {
test_contains_1001();
test_machines();
test_last_k();
test_edges();
test_random();
std::printf("test_minimize: ok\n");
}// Pruebas de la sesión A: la división del lema sacada de un DFA, y las partidas del capítulo.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <string>
#include <vector>
#include "dfa.h"
#include "distinguish.h"
#include "pumping.h"
// El lema, comprobado en un DFA: para toda cadena w con |Q| ≤ |w| ≤ max_len, la división que
// sale del primer estado repetido cumple las tres condiciones con p = |Q|.
static std::size_t check_lemma(const Dfa& m, std::size_t max_len) {
std::size_t p = m.states.size();
std::size_t checked = 0;
for (const std::string& w : all_strings(m.alphabet, max_len)) {
if (w.size() < p) {
continue;
}
PumpSplit found = pump_split(m, w);
const Split& s = found.split;
assert(s.x + s.y + s.z == w);
assert(!s.y.empty()); // |y| > 0
assert(s.x.size() + s.y.size() <= p); // |xy| ≤ p
// El ciclo: x lleva al estado repetido, e y vuelve a él.
assert(delta_star(m, m.start, s.x) == found.state);
assert(delta_star(m, found.state, s.y) == found.state);
// Por eso x y^i z termina donde termina w: si w ∈ L, todas están en L.
for (std::size_t i = 0; i <= 5; i++) {
assert(delta_star(m, m.start, pumped(s, i)) == delta_star(m, m.start, w));
}
checked++;
}
return checked;
}
static void test_lemma_on_machines() {
std::size_t total = 0;
for (const char* path : {"machines/ends_01.dfa", "machines/contains_101.dfa", "machines/multiple_of_3.dfa",
"machines/ends_01_seven.dfa", "machines/contains_1001.dfa",
"machines/count_attempt.dfa", "machines/last_3.dfa"}) {
total += check_lemma(load_dfa(path), 11);
}
assert(total > 20000);
// Las dos ejecuciones copiadas en los apuntes.
Dfa three = load_dfa("machines/multiple_of_3.dfa");
PumpSplit a = pump_split(three, "10101");
assert(a.split.x == "10" && a.split.y == "1" && a.split.z == "01");
assert(a.state == "r2" && a.first == 2 && a.second == 3);
for (const char* w : {"1001", "10101", "101101", "1011101", "10111101"}) {
assert(accepts(three, w)); // 9, 21, 45, 93, 189: múltiplos de 3
}
Dfa attempt = load_dfa("machines/count_attempt.dfa");
PumpSplit b = pump_split(attempt, "00000000111");
assert(b.split.x == "000" && b.split.y == "0" && b.split.z == "0000111");
assert(b.state == "z3" && b.first == 3 && b.second == 4);
}
// El intento de la introducción: acierta con 0^n 1^n hasta n = 3 y después acepta de más.
static void test_count_attempt() {
Dfa attempt = load_dfa("machines/count_attempt.dfa");
assert(attempt.states.size() == 8);
for (const char* w : {"", "01", "0011", "000111"}) {
assert(accepts(attempt, w));
}
assert(accepts(attempt, "00000111") && !in_zeros_ones("00000111")); // acepta de más
assert(!accepts(attempt, "00001111") && in_zeros_ones("00001111")); // y de menos
for (const std::string& w : all_strings({'0', '1'}, 12)) {
std::size_t zeros = count_symbol(w, '0');
std::size_t ones = count_symbol(w, '1');
bool expected = is_block_pair(w, '0', '1') && ((zeros <= 3 && ones == zeros) || (zeros >= 3 && ones == 3));
assert(accepts(attempt, w) == expected);
}
}
static const Game& game_named(const std::vector<Game>& games, const char* name) {
for (const Game& game : games) {
if (game.name == name) {
return game;
}
}
assert(false);
return games[0];
}
// Las partidas bien jugadas: para cada p, la cadena está en L, mide al menos p, y en TODAS las
// divisiones permitidas el exponente del capítulo saca la cadena de L.
static void test_games() {
std::vector<Game> games = chapter_games();
for (const char* name : {"0n1n", "iguales", "ww", "cuadrados", "mas-ceros"}) {
const Game& game = game_named(games, name);
for (std::size_t p = 1; p <= 12; p++) {
std::string s = game.choose_string(p);
assert(game.in_language(s) && s.size() >= p);
std::vector<Split> splits = legal_splits(s, p);
assert(splits.size() == p * (p + 1) / 2);
for (const Split& split : splits) {
// En las cinco, |xy| ≤ p obliga a que y sea solo ceros.
assert(count_symbol(split.y, '0') == split.y.size());
assert(!game.in_language(pumped(split, game.exponent)));
}
assert(surviving_splits(game, p).empty());
}
}
// Lo que dicen las demostraciones sobre la cadena bombeada, con y = 0^k.
for (std::size_t p = 1; p <= 10; p++) {
for (const Split& split : legal_splits(game_named(games, "ww").choose_string(p), p)) {
std::size_t k = split.y.size();
assert(pumped(split, 2) == std::string(p + k, '0') + "1" + std::string(p, '0') + "1");
}
for (const Split& split : legal_splits(game_named(games, "cuadrados").choose_string(p), p)) {
std::size_t length = pumped(split, 2).size();
assert(p * p < length && length < (p + 1) * (p + 1)); // entre dos cuadrados seguidos
}
for (const Split& split : legal_splits(game_named(games, "mas-ceros").choose_string(p), p)) {
std::size_t k = split.y.size();
assert(pumped(split, 0) == std::string(p + 1 - k, '0') + std::string(p, '1'));
for (std::size_t i = 1; i <= 6; i++) {
assert(in_more_zeros(pumped(split, i))); // hacia arriba no se sale nunca
}
}
}
}
// Las partidas mal jugadas: el adversario tiene una división que resiste todos los exponentes.
static void test_bad_games() {
std::vector<Game> games = chapter_games();
for (std::size_t p = 2; p <= 10; p++) {
// (01)^p con y = 01: x y^i z = (01)^(p-1+i).
std::string s = game_named(games, "iguales-mal").choose_string(p);
Split split = {"", "01", s.substr(2)};
assert(in_equal(s) && s.size() >= p);
// 0^(2p) con y = 00.
std::string t = game_named(games, "ww-mal").choose_string(p);
Split even = {"", "00", t.substr(2)};
assert(in_ww(t) && t.size() >= p);
for (std::size_t i = 0; i <= 8; i++) {
assert(in_equal(pumped(split, i)));
assert(in_ww(pumped(even, i)));
}
assert(!surviving_splits(game_named(games, "iguales-mal"), p).empty());
assert(!surviving_splits(game_named(games, "ww-mal"), p).empty());
// Bombear hacia arriba en { 0^i 1^j : i > j }: resisten todas las divisiones.
assert(surviving_splits(game_named(games, "mas-ceros-mal"), p).size() == p * (p + 1) / 2);
}
// Las salidas copiadas en los apuntes.
assert(surviving_splits(game_named(games, "iguales-mal"), 3).size() == 2);
}
// Cierre: (tantos 0 como 1) ∩ 0*1* = { 0^n 1^n }.
static void test_closure() {
for (const std::string& w : all_strings({'0', '1'}, 12)) {
assert((in_equal(w) && is_block_pair(w, '0', '1')) == in_zeros_ones(w));
}
}
// El lenguaje que cumple el lema sin ser regular: { a^i b^j c^k : si i = 1 entonces j = k }.
static void test_trap_language() {
std::size_t checked = 0;
for (const std::string& s : all_strings({'a', 'b', 'c'}, 8)) {
if (s.size() < 2 || !in_trap(s)) {
continue;
}
Split split = trap_split(s);
assert(split.x + split.y + split.z == s);
assert(!split.y.empty() && split.x.size() + split.y.size() <= 2); // p = 2
for (std::size_t i = 0; i <= 6; i++) {
assert(in_trap(pumped(split, i)));
}
checked++;
}
assert(checked > 100);
// Y no es regular: a b^i y a b^j, con i ≠ j, se distinguen con c^i.
for (std::size_t i = 0; i < 12; i++) {
for (std::size_t j = 0; j < 12; j++) {
std::string x = "a" + std::string(i, 'b');
std::string y = "a" + std::string(j, 'b');
std::string z(i, 'c');
assert(in_trap(x + z));
assert(in_trap(y + z) == (i == j));
}
}
}
int main() {
test_lemma_on_machines();
test_count_attempt();
test_games();
test_bad_games();
test_closure();
test_trap_language();
std::printf("test_pumping: ok\n");
}Laboratorio
Archivos de partida del laboratorio de la semana.
TIEMPO = 2
VERIFICADOR = verificador.cpp
include ../../../lab.mk# Minimizar un DFA
Ejercicio opcional de la semana 4: la sesión de laboratorio de esta semana es para la Práctica 1.
Dos autómatas finitos deterministas (DFA) pueden reconocer el mismo lenguaje con distinta cantidad de estados.
Entre todos los que reconocen un lenguaje hay uno con el menor número posible, el **DFA mínimo**, y es único
salvo los nombres de sus estados. Su programa recibe un DFA y escribe el DFA mínimo que reconoce el mismo
lenguaje.
El algoritmo está en los apuntes de la semana 4, sección *Minimizar un DFA*: quitar los estados inalcanzables,
partir de la partición $\{F, Q - F\}$ y refinarla hasta que no cambie.
## Entrada
La descripción de un DFA en el formato `.dfa` de [`code/formats.md`](../../../formats.md):
```text
$ cat casos/01.in
# Cadenas binarias que contienen 1001, escrito con descuido: 8 estados para un lenguaje
# que necesita 5.
# q0: todavía no se leyó nada. q4: no hay avance, y ya se leyó algo.
# q1: lo leído termina en 1. q2: termina en 10. q3: termina en 100.
# q5, q6: ya apareció 1001 (q5 si lo último fue 1, q6 si fue 0).
# q7: quedó de una versión anterior. Ninguna transición llega a él.
states: q0 q1 q2 q3 q4 q5 q6 q7
alphabet: 0 1
start: q0
accept: q5 q6 q7
delta:
q0 0 q4
q0 1 q1
q1 0 q2
q1 1 q1
q2 0 q3
q2 1 q1
q3 0 q4
q3 1 q5
q4 0 q4
q4 1 q1
q5 0 q6
q5 1 q5
q6 0 q6
q6 1 q5
q7 0 q3
q7 1 q7
```
- Una línea que empieza con `#` es un comentario. Puede haber comentarios en cualquier línea, también entre
las transiciones.
- Puede haber líneas vacías antes de `delta:`. Después de `delta:` no hay líneas vacías.
- `states:`, `alphabet:`, `start:`, `accept:` y `delta:` vienen siempre en ese orden. `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.
- No hay bloque `strings:`. La entrada termina con la última transición.
## Salida
Un DFA en el mismo formato, que reconozca el mismo lenguaje que el de la entrada y tenga el menor número
posible de estados.
- El alfabeto es el de la entrada. Sus símbolos pueden ir en cualquier orden.
- Los estados pueden llamarse como quieran y escribirse en cualquier orden. Un nombre tiene entre 1 y 20
caracteres visibles, sin espacios, no empieza con `#` y no termina con `:`. Lo más simple es numerarlos. No
armen el nombre de un bloque pegando los nombres de sus estados: puede pasar de 20 caracteres.
- La función de transición es total: una línea por cada par de estado y símbolo, sin repetir.
- Pueden escribir comentarios.
Para la entrada de arriba, esta es una salida correcta:
```text
$ cat casos/01.out
states: m0 m1 m2 m3 m4
alphabet: 0 1
start: m0
accept: m4
delta:
m0 0 m0
m0 1 m1
m1 0 m2
m1 1 m1
m2 0 m3
m2 1 m1
m3 0 m0
m3 1 m4
m4 0 m4
m4 1 m4
```
No es la única. Otra salida con cinco estados que reconozca el mismo lenguaje también es correcta, se llamen
como se llamen.
## Límites
- $1 \leq |Q| \leq 2000$ y $1 \leq |\Sigma| \leq 26$.
- El nombre de un estado de la entrada tiene entre 1 y 20 caracteres visibles, sin espacios. No empieza con `#`
ni termina con `:`. Un nombre puede ser prefijo de otro (`q1` y `q10`), y puede ser igual a un símbolo (un
estado `0` y un símbolo `0`).
- Un símbolo es un solo carácter visible, distinto de `#`.
- La entrada siempre describe un DFA válido: no tienen que detectar errores en la descripción.
## El verificador
Como hay muchas respuestas correctas, el juez no compara su salida con `casos/NN.out`. Usa
`verificador.cpp`, que pueden leer, y que comprueba tres cosas:
1. La salida es un DFA bien formado y completo, con el alfabeto de la entrada.
2. Tiene tantos estados como el DFA de `casos/NN.out`, que es el mínimo.
3. Reconoce el mismo lenguaje que el DFA de la entrada. Para eso recorre los pares de estados a los que se
llega leyendo la misma cadena en los dos autómatas, y busca un par en el que uno acepte y el otro no.
Por el teorema de unicidad de los apuntes, un DFA equivalente con el número mínimo de estados es el DFA
mínimo, así que con eso basta. Cuando la salida es incorrecta, el juez muestra el motivo al lado del veredicto
`WA`: qué línea está mal formada, cuántos estados tiene la salida y cuántos el mínimo, o una cadena, de las más
cortas, en la que la salida y la entrada no coinciden.
## Tiempo
2 segundos por caso. Se compila con `g++ -Wall -Wextra -std=c++20 -O2`.
Los cuatro casos grandes tienen 2000 estados. Hay unos dos millones de pares de estados, y decidir cada par por
separado, buscando un sufijo que lo distinga, es demasiado: una solución así pasa los diez casos pequeños y da
`TLE` en los cuatro grandes. El refinamiento decide todos los pares a la vez: en cada ronda calcula una firma
por estado, y agrupa.
Dos de los casos grandes necesitan cerca de mil y cerca de dos mil rondas. Para que cada ronda sea rápida,
numeren los estados y los símbolos al leer la entrada, y guarden $\delta$ y la partición en vectores de
enteros. Agrupar las firmas con un `std::map<std::vector<int>, int>` alcanza.
## Qué se practica aquí
En `code/week-04/minimize.h` hay una minimización que pueden leer: es la de los apuntes, escrita para que se
parezca a las definiciones, con los nombres de los estados como cadenas, y no para autómatas grandes.
`solution.cpp` se escribe sin incluir los encabezados de la semana: el juez compila ese único archivo.
Los casos traen, entre otros: estados inalcanzables, algunos de ellos de aceptación; un autómata sin estados de
aceptación y uno con todos de aceptación, cuyo mínimo tiene un solo estado; uno que ya es mínimo; un estado
inicial que se fusiona con otros; comentarios entre las transiciones y nombres iguales a los símbolos.
## Cómo avanzar
```sh
make # compila solution.cpp en build/
make test # corre el juez con todos los casos
```
Los cuatro casos grandes no están guardados: `make test` los genera con los programas `casos/gen_NN.cpp`.
1. Lean el DFA y escríbanlo de nuevo tal cual, con sus propios nombres para los estados. Con eso ya pasa
`casos/02.in`, que es mínimo, y saben que leen y escriben bien el formato.
2. Eliminen los estados inalcanzables, con un recorrido desde el estado inicial. Antes de correr el juez,
respondan a mano: ¿cuántos estados tiene el mínimo de un DFA sin estados de aceptación? ¿Y el de `casos/05.in`,
que tiene estados de aceptación pero todos inalcanzables?
3. Refinen la partición $\{F, Q - F\}$ hasta que una ronda no cambie el número de bloques, y escriban un
estado por bloque. Para depurar, comparen sus particiones con las que imprime el programa de la clase:
```sh
../../build/minimize casos/01.in
```
4. Corran `make test`. Si un caso da `WA`, el mensaje del verificador dice por dónde empezar: si sobran
estados, alguna ronda dejó juntos a dos que debía separar o quedaron inalcanzables; si aparece una cadena,
síganla a mano en la entrada y en su salida.
## El autómata de k = 6
En el laboratorio de la semana 2 midieron cuántos estados da la construcción de subconjuntos para "el
$k$-ésimo símbolo desde el final es $\mathtt{1}$". Para $k = 6$, el NFA tiene 7 estados y el DFA debió salirles
con 64. Pasen ese DFA por su programa de esta semana y cuenten los estados del resultado. Si no lo tienen a la
mano, el programa `kth_from_end` de `code/week-04` escribe uno igual salvo los nombres: lo construye
directamente, con un estado por cada combinación de los últimos 6 símbolos. El mismo autómata es `casos/09.in`.
```sh
../../build/kth_from_end 6 > k6.dfa
build/solution < k6.dfa | head -1 | wc -w # los estados, más la palabra states:
```
Con la minimización de la clase, el resultado es este:
```text
$ ../../build/kth_from_end 6 | ../../build/minimize - | grep -E '^(estados|P[0-9]|DFA)'
estados: 64, alcanzables: 64. No hay nada que quitar
P0: 2 bloques
P1: 4 bloques
P2: 8 bloques
P3: 16 bloques
P4: 32 bloques
P5: 64 bloques
P6 = P5: la partición ya no cambia
DFA mínimo: 64 estados
```
Entran 64 estados y salen 64: no se fusiona ninguno. La construcción de subconjuntos no desperdició nada, y es
lo que dice el teorema de los apuntes: todo DFA de ese lenguaje tiene al menos $2^6 = 64$ estados, porque las
64 cadenas de longitud 6 son distinguibles dos a dos. Las 5 rondas que cambian algo corresponden a los
sufijos $\mathtt{0}, \mathtt{00}, \ldots, \mathtt{00000}$ de esa demostración.
Comparen con un autómata que sí tenía estados de más, el de `casos/07.in`:
```text
$ ../../build/minimize casos/07.in | grep -E '^(estados|P[0-9]|DFA)'
estados: 7, alcanzables: 7. No hay nada que quitar
P0: 2 bloques
P1: 3 bloques
P2 = P1: la partición ya no cambia
DFA mínimo: 3 estados
```
## Para seguir
Opcional, sin casos en el juez.
- Escriban un segundo programa que lea **dos** DFA con el mismo alfabeto y diga si reconocen el mismo
lenguaje: minimicen los dos y comprueben si son iguales salvo los nombres, recorriéndolos a la vez desde los
estados iniciales. Les servirá en el laboratorio de la semana 9.
- Midan cuántas rondas hace su programa en cada caso grande. ¿Por qué el caso 12, con 2000 estados al azar,
necesita tan pocas, y el caso 14 tantas?// Minimizar un DFA. Lee la descripción de un autómata y escribe, en el mismo formato, el DFA
// mínimo que reconoce el mismo lenguaje.
#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
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Dfa m;
std::string line;
// Por hacer:
// 1. Leer la descripción línea por línea, con std::getline, hasta el final de la entrada.
// 2. Marcar los estados alcanzables desde el inicial y olvidarse de los demás.
// 3. Partir de la partición {F, Q − F} y refinarla hasta que una ronda no la cambie.
// 4. Escribir el autómata con un estado por bloque, en formato .dfa.
while (std::getline(std::cin, line)) {
}
// Este esqueleto no escribe nada, así que el juez da WA en todos los casos.
return static_cast<int>(m.states.size());
}// Verificador de minimize_dfa. El juez lo llama así: verificador NN.in NN.out salida
// Termina con 0 si la salida es correcta. Si no, escribe el motivo y termina con 1.
// Una salida es correcta si:
// 1. es un DFA bien formado y completo, en formato .dfa, sobre el alfabeto de la entrada;
// 2. tiene tantos estados como el DFA de NN.out, que es el mínimo;
// 3. reconoce el mismo lenguaje que el DFA de la entrada.
// Los nombres y el orden de los estados no importan. Como el mínimo es único salvo los
// nombres, un DFA equivalente con ese número de estados es el mínimo.
#include <cstddef>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
struct Dfa {
std::vector<std::string> states; // Q
std::vector<char> alphabet; // Σ
std::vector<std::vector<int>> delta; // δ, por posiciones
int start = 0; // q0
std::vector<bool> accept; // F
};
static std::vector<std::string> split_words(const std::string& text) {
std::istringstream in(text);
std::vector<std::string> words;
std::string word;
while (in >> word) {
words.push_back(word);
}
return words;
}
static bool valid_name(const std::string& name) {
if (name.empty() || name.size() > 20 || name[0] == '#' || name.back() == ':') {
return false;
}
for (char c : name) {
if (static_cast<unsigned char>(c) <= ' ' || static_cast<unsigned char>(c) == 127) {
return false;
}
}
return true;
}
// Lee un DFA comprobando todo lo que el formato exige. Lanza std::runtime_error con el motivo.
static Dfa read_dfa(const std::string& path) {
std::ifstream in(path);
if (!in) {
throw std::runtime_error("no se pudo abrir " + path);
}
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;
};
Dfa m;
std::map<std::string, int> index;
m.states = field("states");
if (m.states.empty()) {
fail("un DFA tiene al menos un estado");
}
for (const std::string& state : m.states) {
if (!valid_name(state)) {
fail("nombre de estado no válido: " + state);
}
if (!index.insert({state, static_cast<int>(index.size())}).second) {
fail("estado repetido en states: " + state);
}
}
std::map<char, int> symbol_index;
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);
}
if (!symbol_index.insert({symbol[0], static_cast<int>(symbol_index.size())}).second) {
fail("símbolo repetido en alphabet: " + symbol);
}
m.alphabet.push_back(symbol[0]);
}
std::vector<std::string> start = field("start");
if (start.size() != 1 || index.count(start[0]) == 0) {
fail("start: lleva exactamente un estado de states");
}
m.start = index.at(start[0]);
m.accept.assign(m.states.size(), false);
for (const std::string& state : field("accept")) {
if (index.count(state) == 0) {
fail("el estado de aceptación " + state + " no está en states");
}
m.accept[static_cast<std::size_t>(index.at(state))] = true;
}
if (!field("delta").empty()) {
fail("después de delta: las transiciones van una por línea");
}
m.delta.assign(m.states.size(), std::vector<int>(m.alphabet.size(), -1));
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");
}
if (index.count(words[0]) == 0 || index.count(words[2]) == 0) {
fail("transición con un estado que no está en states");
}
if (symbol_index.count(words[1][0]) == 0) {
fail("transición con un símbolo que no está en alphabet: " + words[1]);
}
int& target = m.delta[static_cast<std::size_t>(index.at(words[0]))]
[static_cast<std::size_t>(symbol_index.at(words[1][0]))];
if (target != -1) {
fail("transición repetida para (" + words[0] + ", " + words[1] + ")");
}
target = index.at(words[2]);
}
for (std::size_t i = 0; i < m.states.size(); i++) {
for (std::size_t a = 0; a < m.alphabet.size(); a++) {
if (m.delta[i][a] == -1) {
throw std::runtime_error("falta la transición de " + m.states[i] + " con " +
std::string(1, m.alphabet[a]) + ": la función de transición es total");
}
}
}
return m;
}
int main(int argc, char** argv) {
if (argc != 4) {
std::cerr << "uso: verificador NN.in NN.out salida\n";
return 2;
}
Dfa original, expected, answer;
try {
original = read_dfa(argv[1]);
expected = read_dfa(argv[2]);
} catch (const std::runtime_error& error) {
std::cout << "error en los archivos del caso: " << error.what() << '\n';
return 2;
}
try {
answer = read_dfa(argv[3]);
} catch (const std::runtime_error& error) {
std::cout << "la salida no es un DFA: " << error.what() << '\n';
return 1;
}
// 1. El mismo alfabeto, en cualquier orden.
std::set<char> sigma_in(original.alphabet.begin(), original.alphabet.end());
std::set<char> sigma_out(answer.alphabet.begin(), answer.alphabet.end());
if (sigma_in != sigma_out) {
std::cout << "el alfabeto de la salida no es el de la entrada\n";
return 1;
}
// 2. El número de estados del mínimo.
if (answer.states.size() != expected.states.size()) {
std::cout << "la salida tiene " << answer.states.size() << " estados y el DFA mínimo tiene "
<< expected.states.size() << '\n';
return 1;
}
// 3. El mismo lenguaje. Se recorren a lo ancho los pares (p, q) a los que se llega leyendo
// la misma cadena en los dos autómatas. Si en algún par uno acepta y el otro no, esa cadena
// los separa, y es de las más cortas.
std::size_t n1 = original.states.size();
std::size_t n2 = answer.states.size();
std::vector<int> column(original.alphabet.size()); // símbolo de la entrada → columna de la salida
for (std::size_t a = 0; a < original.alphabet.size(); a++) {
for (std::size_t b = 0; b < answer.alphabet.size(); b++) {
if (answer.alphabet[b] == original.alphabet[a]) {
column[a] = static_cast<int>(b);
}
}
}
const int unseen = -2;
std::vector<int> parent(n1 * n2, unseen); // de qué par se llegó, o -1 para el inicial
std::vector<char> by(n1 * n2, 0); // y con qué símbolo
std::vector<std::size_t> order;
std::size_t first = static_cast<std::size_t>(original.start) * n2 + static_cast<std::size_t>(answer.start);
parent[first] = -1;
order.push_back(first);
for (std::size_t head = 0; head < order.size(); head++) {
std::size_t p = order[head] / n2;
std::size_t q = order[head] % n2;
if (original.accept[p] != answer.accept[q]) {
std::string w;
for (std::size_t at = order[head]; parent[at] != -1; at = static_cast<std::size_t>(parent[at])) {
w += by[at];
}
w = std::string(w.rbegin(), w.rend());
std::cout << "no reconoce el mismo lenguaje: la cadena " << (w.empty() ? "vacía" : w)
<< (original.accept[p] ? " está en el lenguaje y la salida la rechaza"
: " no está en el lenguaje y la salida la acepta")
<< '\n';
return 1;
}
for (std::size_t a = 0; a < original.alphabet.size(); a++) {
std::size_t next = static_cast<std::size_t>(original.delta[p][a]) * n2 +
static_cast<std::size_t>(answer.delta[q][static_cast<std::size_t>(column[a])]);
if (parent[next] == unseen) {
parent[next] = static_cast<int>(order[head]);
by[next] = original.alphabet[a];
order.push_back(next);
}
}
}
return 0;
}Compilación
Cómo se compilan y ejecutan los ejemplos.
# Semana 4: lema de bombeo, cadenas distinguibles, Myhill-Nerode y minimización de DFA.
# Se usa dentro del entorno del curso.
#
# make compila los programas de la clase en build/
# make test corre las pruebas de los ejemplos, con sanitizers
# make clean borra lo generado
#
# Las pruebas leen los autómatas de machines/, así que se corren desde esta carpeta.
# El laboratorio está en lab/minimize_dfa y tiene su propio Makefile: estas reglas no lo tocan.
CXX = g++
CXXFLAGS = -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined
BUILD = build
PROGRAMS = show_dfa run_dfa pump pumping_game distinguish fooling_set classes kth_from_end minimize equivalent
TESTS = test_pumping test_distinguish test_minimize
HEADERS = dfa.h pumping.h distinguish.h minimize.h streaming.h
.PHONY: all test clean
all: $(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%)
$(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(HEADERS) | $(BUILD)
$(CXX) $(CXXFLAGS) $< -o $@
$(BUILD):
mkdir -p $@
test: $(TESTS:%=$(BUILD)/%) $(PROGRAMS:%=$(BUILD)/%)
@for t in $(TESTS); do $(BUILD)/$$t || exit 1; done
@echo "Todas las pruebas pasaron."
clean:
rm -rf $(BUILD)