Semana 2 — No determinismo
Objetivos
- Definir un NFA, con transiciones , y explicar qué significa que acepte una cadena.
- Convertir un NFA en un DFA con la construcción de subconjuntos, y demostrar que son equivalentes.
- Usar NFA para demostrar que los lenguajes regulares son cerrados bajo unión, concatenación y estrella.
- Dar un lenguaje en el que el DFA necesita exponencialmente más estados que el NFA.
Sesión A — No determinismo: NFA y transiciones ε
Lectura: Apuntes, semana 2.
Apoyo: Sipser, sec. 1.2 (Nondeterminism), hasta la definición formal. Erickson, Models of Computation, nota 4 (Nondeterministic automata).
Temas:
- Un diseño que con DFA cuesta: “el tercer símbolo desde el final es ”. Con un NFA sale en cuatro estados.
- Qué cambia: varias transiciones con el mismo símbolo, ninguna, o transiciones .
- Tres maneras de pensar el no determinismo: adivinar bien, explorar todos los caminos a la vez, o un árbol de ejecuciones. Acepta si algún camino termina en aceptación.
- Definición formal: devuelve un conjunto de estados, .
- Seguir un NFA a mano: el conjunto de estados activos después de cada símbolo.
- Clausura de un conjunto de estados.
- Todo DFA es un NFA. La pregunta de la sesión B: ¿los NFA reconocen algo más?
- Error común: creer que el NFA acepta si todos los caminos aceptan, o que “elige al azar”.
Sesión B — Construcción de subconjuntos · Propiedades de cierre
Lectura: Apuntes, semana 2.
Apoyo: Sipser, sec. 1.2 (Equivalence of NFAs and DFAs y Closure under the regular operations). Erickson, Models of Computation, nota 4.
Temas:
- La idea: el conjunto de estados activos es un solo estado de un DFA.
- Construcción de subconjuntos, con clausura , sobre el ejemplo de la sesión A. Solo se construyen los subconjuntos alcanzables.
- Demostración de la equivalencia, por inducción sobre la longitud de la cadena.
- El costo: hasta estados. Para “el -ésimo símbolo desde el final es ”, el DFA necesita estados; se justifica con intuición y se demuestra en la semana 4.
- Cierre bajo unión, concatenación y estrella, con construcciones sobre NFA y transiciones .
- El detalle de la estrella: hace falta un estado inicial nuevo, y por qué no basta con marcar el anterior como de aceptación.
- Cierre bajo reverso, como ejercicio de construcción.
- Error común: para el complemento, intercambiar los estados de aceptación de un NFA. Solo funciona en un DFA.
Laboratorio — De NFA a DFA
- Leer un NFA con transiciones y escribir un DFA equivalente.
- Calcular la clausura con una búsqueda en el grafo de transiciones .
- Generar solo los subconjuntos alcanzables, con una cola, y darles nombres nuevos.
- Comprobar la salida con el verificador del problema, que compara lenguajes y no nombres de estados.
- Medir cuántos estados sale para “el -ésimo símbolo desde el final es ” con de 1 a 12, y anotar la tabla.
Preguntas de repaso
- Sigan a mano un NFA con transiciones con una cadena de cinco símbolos, anotando el conjunto de estados activos.
- ¿Por qué el estado de aceptación del DFA construido es “cualquier subconjunto que contenga un estado de aceptación”?
- Apliquen la construcción de subconjuntos a un NFA de tres estados y dibujen solo los estados alcanzables.
- Den un NFA para el que intercambiar los estados de aceptación no da el complemento.
- Con la construcción de la estrella, ¿por qué siempre queda aceptada? Muestren qué falla en la construcción sin estado inicial nuevo.
Código de la semana
Compilar y probar dentro del contenedor del curso con make y make test.
Ejemplos (23)Errores (3)Pruebas (4)Laboratorio (4)Compilación (1)
Ejemplos
Los programas que usan los apuntes y la clase.
// Construcciones de cierre sobre NFA:
// combine union A.nfa B.nfa combine concat A.nfa B.nfa
// combine star A.nfa combine reverse A.nfa
// Escribe el NFA resultante en formato .nfa. Los archivos .dfa también sirven de entrada.
#include <iostream>
#include <stdexcept>
#include <string>
#include "nfa.h"
int main(int argc, char** argv) {
std::string mode = argc >= 2 ? argv[1] : "";
bool two = (mode == "union" || mode == "concat");
bool one = (mode == "star" || mode == "reverse");
if (!(two && argc == 4) && !(one && argc == 3)) {
std::cerr << "uso: combine (union|concat) A.nfa B.nfa\n combine (star|reverse) A.nfa\n";
return 2;
}
try {
Nfa a = load_nfa(argv[2]);
Nfa result;
if (mode == "union") {
result = nfa_union(a, load_nfa(argv[3]));
std::cout << "# Unión de " << argv[2] << " y " << argv[3] << ".\n";
} else if (mode == "concat") {
result = nfa_concat(a, load_nfa(argv[3]));
std::cout << "# Concatenación de " << argv[2] << " y " << argv[3] << ".\n";
} else if (mode == "star") {
result = nfa_star(a);
std::cout << "# Estrella de " << argv[2] << ".\n";
} else {
result = nfa_reverse(a);
std::cout << "# Reverso de " << argv[2] << ".\n";
}
write_nfa(std::cout, result);
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Autómata finito determinista. El struct tiene los cinco componentes de la definición
// M = (Q, Σ, δ, q0, F), con los nombres del formato .dfa de code/formats.md.
// Además: leer y escribir ese formato, la función de transición extendida, la construcción
// del producto y el complemento.
// Es el dfa.h de la semana 1, sin cambios: la construcción de subconjuntos de nfa.h produce un Dfa.
#ifndef DFA_H
#define DFA_H
#include <cstddef>
#include <fstream>
#include <istream>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
struct Dfa {
std::vector<std::string> states; // Q, en el orden del archivo
std::vector<char> alphabet; // Σ
std::map<std::pair<std::string, char>, std::string> delta; // δ : Q × Σ → Q
std::string start; // q0
std::set<std::string> accept; // F ⊆ Q
};
// ------------------------------------------------------------
// Comprobar que la quíntupla es un DFA
// ------------------------------------------------------------
// Lanza std::runtime_error si m no cumple la definición. Lo más importante: δ es total.
inline void check_dfa(const Dfa& m) {
std::set<std::string> q(m.states.begin(), m.states.end());
std::set<char> sigma(m.alphabet.begin(), m.alphabet.end());
if (m.states.empty()) {
throw std::runtime_error("Q no puede ser vacío");
}
if (q.size() != m.states.size()) {
throw std::runtime_error("hay un estado repetido en states");
}
if (m.alphabet.empty()) {
throw std::runtime_error("el alfabeto no puede ser vacío");
}
if (sigma.size() != m.alphabet.size()) {
throw std::runtime_error("hay un símbolo repetido en alphabet");
}
if (q.count(m.start) == 0) {
throw std::runtime_error("el estado inicial " + m.start + " no está en states");
}
for (const std::string& f : m.accept) {
if (q.count(f) == 0) {
throw std::runtime_error("el estado de aceptación " + f + " no está en states");
}
}
for (const auto& [key, target] : m.delta) {
if (q.count(key.first) == 0) {
throw std::runtime_error("transición desde " + key.first + ", que no está en states");
}
if (sigma.count(key.second) == 0) {
throw std::runtime_error(std::string("transición con ") + key.second + ", que no está en alphabet");
}
if (q.count(target) == 0) {
throw std::runtime_error("transición hacia " + target + ", que no está en states");
}
}
for (const std::string& state : m.states) {
for (char a : m.alphabet) {
if (m.delta.count({state, a}) == 0) {
throw std::runtime_error("falta la transición δ(" + state + ", " + a + "): en un DFA, δ es total");
}
}
}
}
// ------------------------------------------------------------
// Leer y escribir el formato .dfa
// ------------------------------------------------------------
inline std::vector<std::string> split_words(const std::string& text) {
std::istringstream in(text);
std::vector<std::string> words;
std::string word;
while (in >> word) {
words.push_back(word);
}
return words;
}
// Lee una descripción completa, hasta el final de la entrada.
inline Dfa read_dfa(std::istream& in) {
int number = 0;
auto fail = [&number](const std::string& message) {
throw std::runtime_error("línea " + std::to_string(number) + ": " + message);
};
// Siguiente línea que no es comentario ni está vacía. Devuelve false al final.
auto next_line = [&in, &number](std::vector<std::string>& words) {
std::string line;
while (std::getline(in, line)) {
number++;
if (!line.empty() && line[0] == '#') {
continue;
}
words = split_words(line);
if (!words.empty()) {
return true;
}
}
return false;
};
// Un campo: "nombre: valor valor ...". Devuelve los valores.
auto field = [&next_line, &fail](const std::string& name) {
std::vector<std::string> words;
if (!next_line(words) || words[0] != name + ":") {
fail("se esperaba el campo " + name + ":");
}
words.erase(words.begin());
return words;
};
Dfa m;
m.states = field("states");
for (const std::string& symbol : field("alphabet")) {
if (symbol.size() != 1 || symbol[0] == '#') {
fail("un símbolo es un solo carácter distinto de #: " + symbol);
}
m.alphabet.push_back(symbol[0]);
}
std::vector<std::string> start = field("start");
if (start.size() != 1) {
fail("start: lleva exactamente un estado");
}
m.start = start[0];
for (const std::string& state : field("accept")) {
m.accept.insert(state);
}
if (!field("delta").empty()) {
fail("después de delta: las transiciones van una por línea");
}
std::vector<std::string> words;
while (next_line(words)) {
if (words.size() != 3 || words[1].size() != 1) {
fail("una transición se escribe: estado símbolo destino");
}
std::pair<std::string, char> key = {words[0], words[1][0]};
if (m.delta.count(key) > 0) {
fail("transición repetida para δ(" + words[0] + ", " + words[1] + "): en un DFA hay una sola");
}
m.delta[key] = words[2];
}
check_dfa(m);
return m;
}
inline Dfa load_dfa(const std::string& path) {
std::ifstream file(path);
if (!file) {
throw std::runtime_error("no se pudo abrir " + path);
}
try {
return read_dfa(file);
} catch (const std::runtime_error& error) {
throw std::runtime_error(path + ": " + error.what());
}
}
// Escribe m en el formato .dfa: lo que escribe se puede volver a leer con read_dfa.
inline void write_dfa(std::ostream& out, const Dfa& m) {
out << "states:";
for (const std::string& state : m.states) {
out << ' ' << state;
}
out << "\nalphabet:";
for (char a : m.alphabet) {
out << ' ' << a;
}
out << "\nstart: " << m.start << "\naccept:";
for (const std::string& state : m.states) {
if (m.accept.count(state) > 0) {
out << ' ' << state;
}
}
out << "\ndelta:\n";
for (const std::string& state : m.states) {
for (char a : m.alphabet) {
out << state << ' ' << a << ' ' << m.delta.at({state, a}) << '\n';
}
}
}
// ------------------------------------------------------------
// Ejecutar
// ------------------------------------------------------------
// Un paso: δ(q, a).
inline const std::string& step(const Dfa& m, const std::string& q, char a) {
auto it = m.delta.find({q, a});
if (it == m.delta.end()) {
throw std::runtime_error("δ(" + q + ", " + a + ") no está definida");
}
return it->second;
}
// La función de transición extendida: δ*(q, ε) = q y δ*(q, wa) = δ(δ*(q, w), a).
// El ciclo aplica la segunda línea de la definición una vez por símbolo, de izquierda a derecha.
inline std::string delta_star(const Dfa& m, std::string q, const std::string& w) {
for (char a : w) {
q = step(m, q, a);
}
return q;
}
// M acepta w si δ*(q0, w) ∈ F.
inline bool accepts(const Dfa& m, const std::string& w) {
return m.accept.count(delta_star(m, m.start, w)) > 0;
}
// La ejecución de M con w: los estados r0, r1, …, rn, con r0 = q0 y r(i+1) = δ(r(i), w(i+1)).
inline std::vector<std::string> run(const Dfa& m, const std::string& w) {
std::vector<std::string> sequence = {m.start};
for (char a : w) {
sequence.push_back(step(m, sequence.back(), a));
}
return sequence;
}
// Los estados a los que se llega desde q0 con alguna cadena.
inline std::set<std::string> reachable(const Dfa& m) {
std::set<std::string> seen = {m.start};
std::queue<std::string> pending;
pending.push(m.start);
while (!pending.empty()) {
std::string q = pending.front();
pending.pop();
for (char a : m.alphabet) {
const std::string& next = step(m, q, a);
if (seen.insert(next).second) {
pending.push(next);
}
}
}
return seen;
}
// ------------------------------------------------------------
// Construcciones
// ------------------------------------------------------------
enum class Combine { Intersection, Union };
// El nombre del estado (p, q) del producto. Los nombres del formato no llevan espacios.
inline std::string pair_name(const std::string& p, const std::string& q) {
return "(" + p + "," + q + ")";
}
// Construcción del producto: Q = Q1 × Q2, δ((p, q), a) = (δ1(p, a), δ2(q, a)), q0 = (q1, q2).
// Para la intersección, F = F1 × F2. Para la unión, F = (F1 × Q2) ∪ (Q1 × F2).
inline Dfa product(const Dfa& m1, const Dfa& m2, Combine mode) {
std::set<char> sigma1(m1.alphabet.begin(), m1.alphabet.end());
std::set<char> sigma2(m2.alphabet.begin(), m2.alphabet.end());
if (sigma1 != sigma2) {
throw std::runtime_error("el producto necesita dos DFA con el mismo alfabeto");
}
Dfa m;
m.alphabet = m1.alphabet;
m.start = pair_name(m1.start, m2.start);
for (const std::string& p : m1.states) {
for (const std::string& q : m2.states) {
std::string name = pair_name(p, q);
m.states.push_back(name);
bool in1 = m1.accept.count(p) > 0;
bool in2 = m2.accept.count(q) > 0;
bool accepting = (mode == Combine::Intersection) ? (in1 && in2) : (in1 || in2);
if (accepting) {
m.accept.insert(name);
}
for (char a : m.alphabet) {
m.delta[{name, a}] = pair_name(step(m1, p, a), step(m2, q, a));
}
}
}
check_dfa(m); // también detecta dos pares con el mismo nombre, si los nombres traían comas
return m;
}
// Complemento: la misma máquina con F cambiado por Q − F.
inline Dfa complement(const Dfa& m) {
Dfa result = m;
result.accept.clear();
for (const std::string& state : m.states) {
if (m.accept.count(state) == 0) {
result.accept.insert(state);
}
}
return result;
}
// La misma máquina sin los estados inalcanzables. Reconoce el mismo lenguaje.
inline Dfa remove_unreachable(const Dfa& m) {
std::set<std::string> keep = reachable(m);
Dfa result;
result.alphabet = m.alphabet;
result.start = m.start;
for (const std::string& state : m.states) {
if (keep.count(state) == 0) {
continue;
}
result.states.push_back(state);
if (m.accept.count(state) > 0) {
result.accept.insert(state);
}
for (char a : m.alphabet) {
result.delta[{state, a}] = step(m, state, a);
}
}
return result;
}
#endif// Escribe el NFA de "el k-ésimo símbolo desde el final es 1": kth_nfa K
#include <cstdlib>
#include <iostream>
#include "kth.h"
int main(int argc, char** argv) {
int k = argc == 2 ? std::atoi(argv[1]) : 0;
if (k < 1 || k > 30) {
std::cerr << "uso: kth_nfa K, con K entre 1 y 30\n";
return 2;
}
std::cout << "# El símbolo número " << k << " desde el final es 1.\n";
write_nfa(std::cout, kth_from_end(k));
}// Cuántos estados da la construcción de subconjuntos para "el k-ésimo símbolo desde el final
// es 1", con k de 1 a K: kth_table [K]. Por defecto, K = 12.
#include <cstdio>
#include <cstdlib>
#include "kth.h"
int main(int argc, char** argv) {
int max_k = argc == 2 ? std::atoi(argv[1]) : 12;
if (max_k < 1 || max_k > 16) {
std::fprintf(stderr, "uso: kth_table [K], con K entre 1 y 16\n");
return 2;
}
std::printf(" k estados del NFA subconjuntos posibles estados del DFA (alcanzables)\n");
for (int k = 1; k <= max_k; k++) {
Nfa n = kth_from_end(k);
Dfa d = subset_construction(n);
std::printf("%2d %15zu %21lu %29zu\n", k, n.states.size(), 1UL << n.states.size(), d.states.size());
}
}// El NFA de "el k-ésimo símbolo desde el final es 1", con k + 1 estados.
#ifndef KTH_H
#define KTH_H
#include <string>
#include "nfa.h"
// q0 espera y, al leer un 1, puede adivinar que ese es el k-ésimo desde el final y pasar a q1.
// De q1 a qk se avanza con cualquier símbolo, y de qk no sale nada.
// Con k = 3 es la máquina de machines/third_from_end.nfa.
inline Nfa kth_from_end(int k) {
Nfa n;
n.alphabet = {'0', '1'};
for (int i = 0; i <= k; i++) {
n.states.push_back("q" + std::to_string(i));
}
n.start = "q0";
n.accept = {"q" + std::to_string(k)};
n.delta[{"q0", '0'}] = {"q0"};
n.delta[{"q0", '1'}] = {"q0", "q1"};
for (int i = 1; i < k; i++) {
n.delta[{n.states[i], '0'}] = {n.states[i + 1]};
n.delta[{n.states[i], '1'}] = {n.states[i + 1]};
}
return n;
}
#endif// Construcción de subconjuntos: nfa_to_dfa ARCHIVO.nfa
// Escribe en la salida estándar, en formato .dfa, un DFA equivalente con solo los subconjuntos
// alcanzables. Con - en lugar del archivo, lee la descripción de la entrada estándar.
#include <iostream>
#include <stdexcept>
#include <string>
#include "nfa.h"
int main(int argc, char** argv) {
if (argc != 2) {
std::cerr << "uso: nfa_to_dfa ARCHIVO.nfa\n";
return 2;
}
try {
std::string path = argv[1];
Nfa n = (path == "-") ? read_nfa(std::cin) : load_nfa(path);
Dfa d = subset_construction(n);
std::cout << "# Construcción de subconjuntos de " << (path == "-" ? "la entrada" : path) << ": "
<< n.states.size() << " estados en el NFA, " << d.states.size() << " en el DFA.\n";
write_dfa(std::cout, d);
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Autómata finito no determinista, con transiciones ε. El struct tiene los cinco componentes de
// la definición N = (Q, Σ, δ, q0, F), con los nombres del formato .nfa de code/formats.md.
// La diferencia con el Dfa está en un solo tipo: δ devuelve un conjunto de estados.
// Además: leer y escribir el formato, la clausura ε, la simulación con el conjunto de estados
// activos, la construcción de subconjuntos y las construcciones de cierre (unión,
// concatenación, estrella y reverso).
#ifndef NFA_H
#define NFA_H
#include <cstddef>
#include <fstream>
#include <istream>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
#include "dfa.h"
// ε no es un símbolo del alfabeto. En la clave de δ se representa con un carácter que ningún
// archivo puede usar como símbolo.
inline constexpr char EPS = '\0';
using StateSet = std::set<std::string>;
struct Nfa {
std::vector<std::string> states; // Q, en el orden del archivo
std::vector<char> alphabet; // Σ
std::map<std::pair<std::string, char>, StateSet> delta; // δ : Q × (Σ ∪ {ε}) → P(Q)
std::string start; // q0
StateSet accept; // F ⊆ Q
};
// ------------------------------------------------------------
// Comprobar que la quíntupla es un NFA
// ------------------------------------------------------------
// Lanza std::runtime_error si n no cumple la definición. A diferencia de check_dfa, no pide
// que δ sea total: un par sin transiciones vale ∅.
inline void check_nfa(const Nfa& n) {
StateSet q(n.states.begin(), n.states.end());
std::set<char> sigma(n.alphabet.begin(), n.alphabet.end());
if (n.states.empty()) {
throw std::runtime_error("Q no puede ser vacío");
}
if (q.size() != n.states.size()) {
throw std::runtime_error("hay un estado repetido en states");
}
if (n.alphabet.empty()) {
throw std::runtime_error("el alfabeto no puede ser vacío");
}
if (sigma.size() != n.alphabet.size()) {
throw std::runtime_error("hay un símbolo repetido en alphabet");
}
if (q.count(n.start) == 0) {
throw std::runtime_error("el estado inicial " + n.start + " no está en states");
}
for (const std::string& f : n.accept) {
if (q.count(f) == 0) {
throw std::runtime_error("el estado de aceptación " + f + " no está en states");
}
}
for (const auto& [key, targets] : n.delta) {
if (q.count(key.first) == 0) {
throw std::runtime_error("transición desde " + key.first + ", que no está en states");
}
if (key.second != EPS && sigma.count(key.second) == 0) {
throw std::runtime_error(std::string("transición con ") + key.second + ", que no está en alphabet");
}
for (const std::string& target : targets) {
if (q.count(target) == 0) {
throw std::runtime_error("transición hacia " + target + ", que no está en states");
}
}
}
}
// ------------------------------------------------------------
// Leer y escribir el formato .nfa
// ------------------------------------------------------------
// Lee una descripción completa, hasta el final de la entrada. Si un par de estado y símbolo
// aparece en varias líneas, sus destinos se juntan.
inline Nfa read_nfa(std::istream& in) {
int number = 0;
auto fail = [&number](const std::string& message) {
throw std::runtime_error("línea " + std::to_string(number) + ": " + message);
};
// Siguiente línea que no es comentario ni está vacía. Devuelve false al final.
auto next_line = [&in, &number](std::vector<std::string>& words) {
std::string line;
while (std::getline(in, line)) {
number++;
if (!line.empty() && line[0] == '#') {
continue;
}
words = split_words(line);
if (!words.empty()) {
return true;
}
}
return false;
};
// Un campo: "nombre: valor valor ...". Devuelve los valores.
auto field = [&next_line, &fail](const std::string& name) {
std::vector<std::string> words;
if (!next_line(words) || words[0] != name + ":") {
fail("se esperaba el campo " + name + ":");
}
words.erase(words.begin());
return words;
};
Nfa n;
n.states = field("states");
for (const std::string& symbol : field("alphabet")) {
if (symbol.size() != 1 || symbol[0] == '#') {
fail("un símbolo es un solo carácter distinto de #: " + symbol);
}
n.alphabet.push_back(symbol[0]);
}
std::vector<std::string> start = field("start");
if (start.size() != 1) {
fail("start: lleva exactamente un estado");
}
n.start = start[0];
for (const std::string& state : field("accept")) {
n.accept.insert(state);
}
if (!field("delta").empty()) {
fail("después de delta: las transiciones van una por línea");
}
std::vector<std::string> words;
while (next_line(words)) {
// estado símbolo destino…, con eps en el lugar del símbolo para una transición ε.
if (words.size() < 3 || (words[1] != "eps" && words[1].size() != 1)) {
fail("una transición se escribe: estado símbolo destino… (uno o más destinos)");
}
char symbol = (words[1] == "eps") ? EPS : words[1][0];
for (std::size_t i = 2; i < words.size(); i++) {
n.delta[{words[0], symbol}].insert(words[i]);
}
}
try {
check_nfa(n);
} catch (const std::runtime_error& error) {
throw std::runtime_error(std::string("no es un NFA: ") + error.what());
}
return n;
}
inline Nfa load_nfa(const std::string& path) {
std::ifstream file(path);
if (!file) {
throw std::runtime_error("no se pudo abrir " + path);
}
try {
return read_nfa(file);
} catch (const std::runtime_error& error) {
throw std::runtime_error(path + ": " + error.what());
}
}
// Escribe n en el formato .nfa: una línea por cada par con al menos un destino, con los
// destinos en el orden de states. Lo que escribe se puede volver a leer con read_nfa.
inline void write_nfa(std::ostream& out, const Nfa& n) {
out << "states:";
for (const std::string& state : n.states) {
out << ' ' << state;
}
out << "\nalphabet:";
for (char a : n.alphabet) {
out << ' ' << a;
}
out << "\nstart: " << n.start << "\naccept:";
for (const std::string& state : n.states) {
if (n.accept.count(state) > 0) {
out << ' ' << state;
}
}
out << "\ndelta:\n";
std::vector<char> columns = n.alphabet;
columns.push_back(EPS);
for (const std::string& state : n.states) {
for (char a : columns) {
auto it = n.delta.find({state, a});
if (it == n.delta.end() || it->second.empty()) {
continue;
}
out << state << ' ' << (a == EPS ? std::string("eps") : std::string(1, a));
for (const std::string& target : n.states) {
if (it->second.count(target) > 0) {
out << ' ' << target;
}
}
out << '\n';
}
}
}
// ------------------------------------------------------------
// Ejecutar
// ------------------------------------------------------------
// δ(q, a), con a ∈ Σ o a = EPS. Un par sin transiciones da ∅.
inline StateSet delta_of(const Nfa& n, const std::string& q, char a) {
auto it = n.delta.find({q, a});
return it == n.delta.end() ? StateSet{} : it->second;
}
// Clausura ε: E(S) son los estados a los que se llega desde algún estado de S con cero o más
// transiciones ε. Es una búsqueda en el grafo que solo tiene las flechas ε.
inline StateSet eps_closure(const Nfa& n, const StateSet& s) {
StateSet closure = s;
std::queue<std::string> pending;
for (const std::string& q : s) {
pending.push(q);
}
while (!pending.empty()) {
std::string q = pending.front();
pending.pop();
for (const std::string& r : delta_of(n, q, EPS)) {
if (closure.insert(r).second) {
pending.push(r);
}
}
}
return closure;
}
// Un paso con el símbolo a desde un conjunto: primero todas las flechas con a que salen de
// algún estado de S, después la clausura ε. Es E(⋃ δ(q, a)), con q en S.
inline StateSet step(const Nfa& n, const StateSet& s, char a) {
StateSet targets;
for (const std::string& q : s) {
StateSet next = delta_of(n, q, a);
targets.insert(next.begin(), next.end());
}
return eps_closure(n, targets);
}
// La función extendida sobre conjuntos: δ*(S, ε) = E(S) y δ*(S, xa) = E(⋃ δ(q, a)), con q en δ*(S, x).
// δ*({q0}, w) es el conjunto de estados activos después de leer w.
inline StateSet delta_star(const Nfa& n, const StateSet& s, const std::string& w) {
StateSet active = eps_closure(n, s);
for (char a : w) {
active = step(n, active, a);
}
return active;
}
// ¿S tiene algún estado de aceptación?
inline bool has_accept(const Nfa& n, const StateSet& s) {
for (const std::string& q : s) {
if (n.accept.count(q) > 0) {
return true;
}
}
return false;
}
// N acepta w si algún estado activo al final es de aceptación.
inline bool accepts(const Nfa& n, const std::string& w) {
return has_accept(n, delta_star(n, {n.start}, w));
}
// Los conjuntos de estados activos: antes de leer nada y después de cada símbolo de w.
inline std::vector<StateSet> run(const Nfa& n, const std::string& w) {
std::vector<StateSet> sequence = {eps_closure(n, {n.start})};
for (char a : w) {
sequence.push_back(step(n, sequence.back(), a));
}
return sequence;
}
// Un conjunto de estados escrito como {q0,q1}, en el orden de states y sin espacios, para que
// sirva de nombre de un estado en un archivo .dfa. El conjunto vacío es {}.
inline std::string set_name(const Nfa& n, const StateSet& s) {
std::string name = "{";
for (const std::string& q : n.states) {
if (s.count(q) > 0) {
name += (name.size() > 1 ? "," : "") + q;
}
}
return name + "}";
}
// ------------------------------------------------------------
// De DFA a NFA y de NFA a DFA
// ------------------------------------------------------------
// Todo DFA es un NFA: la misma máquina, con δ(q, a) = {el único destino} y sin transiciones ε.
inline Nfa to_nfa(const Dfa& m) {
Nfa n;
n.states = m.states;
n.alphabet = m.alphabet;
n.start = m.start;
n.accept = m.accept;
for (const auto& [key, target] : m.delta) {
n.delta[key] = {target};
}
return n;
}
// Construcción de subconjuntos. El DFA tiene un estado por cada conjunto de estados del NFA
// que se alcanza desde E({q0}):
// inicial E({q0})
// transición δ_D(S, a) = E(⋃ δ(q, a)), con q en S
// aceptación los S que contienen algún estado de F
// Solo genera los subconjuntos alcanzables, con una cola, en el orden en que aparecen.
// Si subsets no es nulo, deja ahí el conjunto que corresponde a cada estado del DFA.
inline Dfa subset_construction(const Nfa& n, std::vector<StateSet>* subsets = nullptr) {
Dfa d;
d.alphabet = n.alphabet;
StateSet first = eps_closure(n, {n.start});
d.start = set_name(n, first);
std::vector<StateSet> found = {first}; // found[i] es el conjunto del estado d.states[i]
std::set<StateSet> seen = {first};
std::queue<StateSet> pending;
pending.push(first);
d.states.push_back(d.start);
while (!pending.empty()) {
StateSet s = pending.front();
pending.pop();
std::string name = set_name(n, s);
if (has_accept(n, s)) {
d.accept.insert(name);
}
for (char a : n.alphabet) {
StateSet t = step(n, s, a);
d.delta[{name, a}] = set_name(n, t);
if (seen.insert(t).second) {
found.push_back(t);
d.states.push_back(set_name(n, t));
pending.push(t);
}
}
}
check_dfa(d);
if (subsets != nullptr) {
*subsets = found;
}
return d;
}
// ------------------------------------------------------------
// Construcciones de cierre
// ------------------------------------------------------------
// Un nombre que no esté en used: name, o name con apóstrofos hasta que no choque.
inline std::string fresh_name(const std::vector<std::string>& used, std::string name) {
StateSet taken(used.begin(), used.end());
while (taken.count(name) > 0) {
name += "'";
}
return name;
}
// El mismo NFA con prefix delante del nombre de cada estado. Sirve para que dos máquinas no
// compartan nombres: las construcciones necesitan Q1 ∩ Q2 = ∅.
inline Nfa with_prefix(const Nfa& n, const std::string& prefix) {
Nfa result;
result.alphabet = n.alphabet;
result.start = prefix + n.start;
for (const std::string& state : n.states) {
result.states.push_back(prefix + state);
}
for (const std::string& state : n.accept) {
result.accept.insert(prefix + state);
}
for (const auto& [key, targets] : n.delta) {
for (const std::string& target : targets) {
result.delta[{prefix + key.first, key.second}].insert(prefix + target);
}
}
return result;
}
inline void require_same_alphabet(const Nfa& n1, const Nfa& n2) {
std::set<char> sigma1(n1.alphabet.begin(), n1.alphabet.end());
std::set<char> sigma2(n2.alphabet.begin(), n2.alphabet.end());
if (sigma1 != sigma2) {
throw std::runtime_error("la construcción necesita dos NFA con el mismo alfabeto");
}
}
// Unión: un estado inicial nuevo s, con transiciones ε a los iniciales de N1 y de N2.
// F = F1 ∪ F2. Los estados de N1 pasan a llamarse 1.q y los de N2, 2.q.
inline Nfa nfa_union(const Nfa& first, const Nfa& second) {
require_same_alphabet(first, second);
Nfa n1 = with_prefix(first, "1.");
Nfa n2 = with_prefix(second, "2.");
Nfa n;
n.alphabet = n1.alphabet;
n.start = "s";
n.states = {n.start};
n.states.insert(n.states.end(), n1.states.begin(), n1.states.end());
n.states.insert(n.states.end(), n2.states.begin(), n2.states.end());
n.delta = n1.delta;
n.delta.insert(n2.delta.begin(), n2.delta.end());
n.delta[{n.start, EPS}] = {n1.start, n2.start};
n.accept = n1.accept;
n.accept.insert(n2.accept.begin(), n2.accept.end());
check_nfa(n);
return n;
}
// Concatenación: se empieza en N1, y de cada estado de aceptación de N1 sale una transición ε
// al inicial de N2. F = F2.
inline Nfa nfa_concat(const Nfa& first, const Nfa& second) {
require_same_alphabet(first, second);
Nfa n1 = with_prefix(first, "1.");
Nfa n2 = with_prefix(second, "2.");
Nfa n;
n.alphabet = n1.alphabet;
n.start = n1.start;
n.states = n1.states;
n.states.insert(n.states.end(), n2.states.begin(), n2.states.end());
n.delta = n1.delta;
n.delta.insert(n2.delta.begin(), n2.delta.end());
for (const std::string& f : n1.accept) {
n.delta[{f, EPS}].insert(n2.start);
}
n.accept = n2.accept;
check_nfa(n);
return n;
}
// Estrella: un estado inicial nuevo s, que es de aceptación, con una transición ε al inicial
// anterior. De cada estado de aceptación sale una transición ε al inicial anterior.
// F = F1 ∪ {s}.
inline Nfa nfa_star(const Nfa& n1) {
Nfa n = n1;
n.start = fresh_name(n1.states, "s");
n.states.insert(n.states.begin(), n.start);
n.delta[{n.start, EPS}] = {n1.start};
for (const std::string& f : n1.accept) {
n.delta[{f, EPS}].insert(n1.start);
}
n.accept.insert(n.start);
check_nfa(n);
return n;
}
// Reverso: todas las flechas al revés, un estado inicial nuevo s con transiciones ε a los que
// eran de aceptación, y un solo estado de aceptación: el que era inicial.
inline Nfa nfa_reverse(const Nfa& n1) {
Nfa n;
n.alphabet = n1.alphabet;
n.start = fresh_name(n1.states, "s");
n.states = {n.start};
n.states.insert(n.states.end(), n1.states.begin(), n1.states.end());
for (const auto& [key, targets] : n1.delta) {
for (const std::string& target : targets) {
n.delta[{target, key.second}].insert(key.first);
}
}
if (!n1.accept.empty()) {
n.delta[{n.start, EPS}] = n1.accept;
}
n.accept = {n1.start};
check_nfa(n);
return n;
}
#endif// Todos los caminos de un NFA con una cadena, uno por línea: paths_nfa ARCHIVO.nfa CADENA
// Es el árbol de ejecuciones, con cada rama escrita desde la raíz. Una rama termina cuando
// se acaba la cadena o cuando el estado no tiene transición con el símbolo que toca (muere).
// La cadena vacía se pasa como '' en la terminal.
#include <cstddef>
#include <iostream>
#include <set>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
#include "nfa.h"
#include "strings.h"
struct Count {
int finished = 0; // caminos que leyeron toda la cadena
int accepting = 0; // de esos, los que terminan en F
int dead = 0; // caminos que murieron antes
};
// Extiende el camino text, que está en el estado q y ya leyó pos símbolos de w.
// on_path tiene los pares (estado, posición) del camino: evita dar vueltas por un ciclo de ε.
static void explore(const Nfa& n, const std::string& w, const std::string& q, std::size_t pos,
const std::string& text, std::set<std::pair<std::string, std::size_t>>& on_path, Count& count) {
on_path.insert({q, pos});
bool moved = false;
if (pos == w.size()) {
bool ok = n.accept.count(q) > 0;
std::cout << " " << text << " termina en " << q << (ok ? ", que está en F" : ", que no está en F") << '\n';
count.finished++;
count.accepting += ok;
moved = true;
} else {
for (const std::string& r : delta_of(n, q, w[pos])) {
explore(n, w, r, pos + 1, text + " -" + w[pos] + "-> " + r, on_path, count);
moved = true;
}
}
for (const std::string& r : delta_of(n, q, EPS)) {
if (on_path.count({r, pos}) == 0) {
explore(n, w, r, pos, text + " -ε-> " + r, on_path, count);
moved = true;
}
}
if (!moved) {
std::cout << " " << text << " muere: " << q << " no tiene transición con " << w[pos] << '\n';
count.dead++;
}
on_path.erase({q, pos});
}
int main(int argc, char** argv) {
if (argc != 3) {
std::cerr << "uso: paths_nfa ARCHIVO.nfa CADENA\n";
return 2;
}
try {
Nfa n = load_nfa(argv[1]);
std::string w = argv[2];
std::cout << "w = " << show(w) << '\n';
std::set<std::pair<std::string, std::size_t>> on_path;
Count count;
explore(n, w, n.start, 0, n.start, on_path, count);
std::cout << "caminos que leen toda la cadena: " << count.finished << " que mueren antes: " << count.dead
<< " que terminan en F: " << count.accepting << "\n"
<< (count.accepting > 0 ? "algún camino termina en F: acepta" : "ningún camino termina en F: rechaza")
<< '\n';
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Ayudas para imprimir tablas alineadas aunque el texto tenga letras como δ o ε, que ocupan
// más de un byte y una sola columna.
#ifndef PRINT_H
#define PRINT_H
#include <cstddef>
#include <string>
// Cuántas columnas ocupa un texto en UTF-8: los bytes de continuación no cuentan.
inline std::size_t columns(const std::string& text) {
std::size_t count = 0;
for (unsigned char c : text) {
count += ((c & 0xC0) != 0x80);
}
return count;
}
inline std::string padded(const std::string& text, std::size_t width) {
std::size_t used = columns(text);
return text + std::string(width > used ? width - used : 0, ' ');
}
#endif// Sigue un DFA con una o más cadenas: run_dfa ARCHIVO.dfa CADENA...
// Con - en lugar del archivo, lee la descripción de la entrada estándar.
// La cadena vacía se pasa como '' en la terminal.
// Es el programa de la semana 1: sirve para seguir el DFA que escribe nfa_to_dfa.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include "dfa.h"
int main(int argc, char** argv) {
if (argc < 3) {
std::cerr << "uso: run_dfa ARCHIVO.dfa CADENA...\n";
return 2;
}
try {
std::string path = argv[1];
Dfa m = (path == "-") ? read_dfa(std::cin) : load_dfa(path);
for (int i = 2; i < argc; i++) {
std::string w = argv[i];
std::vector<std::string> sequence = run(m, w);
std::cout << "w = " << (w.empty() ? "ε" : w) << "\n " << sequence[0];
for (std::size_t k = 0; k < w.size(); k++) {
std::cout << " -" << w[k] << "-> " << sequence[k + 1];
}
const std::string& last = sequence.back();
bool ok = m.accept.count(last) > 0;
std::cout << "\n termina en " << last << (ok ? ", que está en F: acepta" : ", que no está en F: rechaza")
<< '\n';
}
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Sigue un NFA con una o más cadenas: run_nfa ARCHIVO.nfa CADENA...
// Imprime el conjunto de estados activos antes de leer nada y después de cada símbolo.
// Con - en lugar del archivo, lee la descripción de la entrada estándar.
// La cadena vacía se pasa como '' en la terminal.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include "nfa.h"
#include "strings.h"
int main(int argc, char** argv) {
if (argc < 3) {
std::cerr << "uso: run_nfa ARCHIVO.nfa CADENA...\n";
return 2;
}
try {
std::string path = argv[1];
Nfa n = (path == "-") ? read_nfa(std::cin) : load_nfa(path);
for (int i = 2; i < argc; i++) {
std::string w = argv[i];
std::vector<StateSet> sequence = run(n, w);
std::cout << "w = " << show(w) << "\n " << set_name(n, sequence[0]);
for (std::size_t k = 0; k < w.size(); k++) {
std::cout << " -" << w[k] << "-> " << set_name(n, sequence[k + 1]);
}
const StateSet& last = sequence.back();
std::cout << "\n termina con " << set_name(n, last) << " activos";
// El primero de los estados finales que está en F, en el orden de states.
std::string witness;
for (const std::string& state : n.states) {
if (witness.empty() && last.count(state) > 0 && n.accept.count(state) > 0) {
witness = state;
}
}
if (witness.empty()) {
std::cout << ", y ninguno está en F: rechaza\n";
} else {
std::cout << ", y " << witness << " está en F: acepta\n";
}
}
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Muestra un NFA como quíntupla y como tabla de transiciones: show_nfa ARCHIVO.nfa
// Cada casilla de la tabla es un conjunto de estados, y hay una columna más para ε.
// En la tabla, -> marca el estado inicial y * los estados de aceptación.
// Si hay transiciones ε, al final imprime la clausura ε de cada estado.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include "nfa.h"
#include "print.h"
int main(int argc, char** argv) {
if (argc != 2) {
std::cerr << "uso: show_nfa ARCHIVO.nfa\n";
return 2;
}
try {
Nfa n = load_nfa(argv[1]);
std::cout << "Q = {";
for (std::size_t i = 0; i < n.states.size(); i++) {
std::cout << (i > 0 ? ", " : "") << n.states[i];
}
std::cout << "}\nΣ = {";
for (std::size_t i = 0; i < n.alphabet.size(); i++) {
std::cout << (i > 0 ? ", " : "") << n.alphabet[i];
}
std::cout << "}\nq0 = " << n.start << "\nF = {";
bool first = true;
for (const std::string& state : n.states) {
if (n.accept.count(state) > 0) {
std::cout << (first ? "" : ", ") << state;
first = false;
}
}
std::cout << "}\n\n";
// Las columnas: los símbolos y, al final, ε.
std::vector<char> symbols = n.alphabet;
symbols.push_back(EPS);
std::vector<std::string> heads;
for (char a : symbols) {
heads.push_back(a == EPS ? "ε" : std::string(1, a));
}
std::size_t name_width = 1;
for (const std::string& state : n.states) {
name_width = std::max(name_width, state.size());
}
std::vector<std::size_t> width(symbols.size(), 1);
bool has_eps = false;
for (const std::string& state : n.states) {
for (std::size_t j = 0; j < symbols.size(); j++) {
width[j] = std::max(width[j], set_name(n, delta_of(n, state, symbols[j])).size());
}
has_eps = has_eps || !delta_of(n, state, EPS).empty();
}
// La última columna va sin relleno, para no dejar espacios al final de la línea.
std::cout << " " << padded("δ", name_width);
for (std::size_t j = 0; j < symbols.size(); j++) {
std::cout << " " << (j + 1 < symbols.size() ? padded(heads[j], width[j]) : heads[j]);
}
std::cout << '\n';
for (const std::string& state : n.states) {
std::cout << (state == n.start ? "-> " : " ") << (n.accept.count(state) > 0 ? "* " : " ")
<< padded(state, name_width);
for (std::size_t j = 0; j < symbols.size(); j++) {
std::string cell = set_name(n, delta_of(n, state, symbols[j]));
std::cout << " " << (j + 1 < symbols.size() ? padded(cell, width[j]) : cell);
}
std::cout << '\n';
}
if (has_eps) {
std::cout << "\nclausura ε de cada estado:\n";
for (const std::string& state : n.states) {
std::cout << " E({" << state << "}) = " << set_name(n, eps_closure(n, {state})) << '\n';
}
} else {
std::cout << "\nno tiene transiciones ε: E(S) = S para todo conjunto S\n";
}
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Cadenas, para las pruebas y los ejemplos: todas las cadenas hasta cierta longitud, y cómo
// se muestra la cadena vacía. all_strings es la de languages.h de la semana 1.
#ifndef STRINGS_H
#define STRINGS_H
#include <cstddef>
#include <string>
#include <vector>
// Todas las cadenas sobre el alfabeto con longitud a lo sumo max_len, primero las más cortas
// y, entre las de igual longitud, en el orden del alfabeto.
inline std::vector<std::string> all_strings(const std::vector<char>& alphabet, std::size_t max_len) {
std::vector<std::string> result = {""};
std::size_t first = 0; // dónde empiezan las cadenas de la longitud anterior
for (std::size_t len = 1; len <= max_len; len++) {
std::size_t last = result.size();
for (std::size_t i = first; i < last; i++) {
for (char a : alphabet) {
result.push_back(result[i] + a);
}
}
first = last;
}
return result;
}
// Para imprimir: la cadena vacía se muestra como ε.
inline std::string show(const std::string& w) {
return w.empty() ? "ε" : w;
}
#endif// La tabla de la construcción de subconjuntos: subset ARCHIVO.nfa
// Una fila por cada subconjunto alcanzable, en el orden en que la cola los encuentra.
// -> marca el estado inicial del DFA y * los de aceptación.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include "nfa.h"
#include "print.h"
int main(int argc, char** argv) {
if (argc != 2) {
std::cerr << "uso: subset ARCHIVO.nfa\n";
return 2;
}
try {
Nfa n = load_nfa(argv[1]);
Dfa d = subset_construction(n);
std::size_t width = 1;
for (const std::string& state : d.states) {
width = std::max(width, state.size());
}
std::cout << "E({" << n.start << "}) = " << d.start << "\n\n";
std::cout << " " << padded("S", width);
for (std::size_t j = 0; j < d.alphabet.size(); j++) {
std::string head(1, d.alphabet[j]);
std::cout << " " << (j + 1 < d.alphabet.size() ? padded(head, width) : head);
}
std::cout << '\n';
for (const std::string& state : d.states) {
std::cout << (state == d.start ? "-> " : " ") << (d.accept.count(state) > 0 ? "* " : " ")
<< padded(state, width);
for (std::size_t j = 0; j < d.alphabet.size(); j++) {
const std::string& target = step(d, state, d.alphabet[j]);
std::cout << " " << (j + 1 < d.alphabet.size() ? padded(target, width) : target);
}
std::cout << '\n';
}
std::cout << "\nel NFA tiene " << n.states.size() << " estados: 2^" << n.states.size() << " = "
<< (1UL << n.states.size()) << " subconjuntos, " << d.states.size() << " alcanzables\n";
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Intercambiar los estados de aceptación de un NFA no da el complemento:
// swap_accept ARCHIVO.nfa CADENA...
// Por cada cadena dice qué responde el NFA, qué responde el NFA con F cambiado por Q − F, y
// qué responde el complemento bien hecho: construcción de subconjuntos y después el intercambio.
#include <iostream>
#include <stdexcept>
#include <string>
#include "errors/wrong_constructions.h"
#include "nfa.h"
#include "strings.h"
int main(int argc, char** argv) {
if (argc < 3) {
std::cerr << "uso: swap_accept ARCHIVO.nfa CADENA...\n";
return 2;
}
try {
Nfa n = load_nfa(argv[1]);
Nfa swapped = swap_accept(n);
Dfa right = complement(subset_construction(n));
std::cout << "F = " << set_name(n, n.accept) << " Q − F = " << set_name(n, swapped.accept) << '\n';
for (int i = 2; i < argc; i++) {
std::string w = argv[i];
std::cout << "w = " << show(w) << '\n';
std::cout << " activos al final: " << set_name(n, delta_star(n, {n.start}, w)) << '\n';
std::cout << " el NFA: " << (accepts(n, w) ? "acepta" : "rechaza") << '\n';
std::cout << " el NFA con Q − F: " << (accepts(swapped, w) ? "acepta" : "rechaza") << '\n';
std::cout << " el DFA de subconjuntos, Q − F: " << (accepts(right, w) ? "acepta" : "rechaza") << '\n';
}
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// La estrella sin estado inicial nuevo acepta cadenas de más: wrong_star ARCHIVO.nfa [LONGITUD]
// Compara la construcción correcta con la incorrecta en todas las cadenas hasta la longitud
// dada (por defecto 4) e imprime las cadenas en las que no coinciden.
#include <cstddef>
#include <cstdlib>
#include <iostream>
#include <stdexcept>
#include <string>
#include "errors/wrong_constructions.h"
#include "nfa.h"
#include "strings.h"
int main(int argc, char** argv) {
if (argc != 2 && argc != 3) {
std::cerr << "uso: wrong_star ARCHIVO.nfa [LONGITUD]\n";
return 2;
}
try {
Nfa n = load_nfa(argv[1]);
std::size_t max_len = argc == 3 ? static_cast<std::size_t>(std::atoi(argv[2])) : 4;
Nfa good = nfa_star(n);
Nfa bad = star_without_new_start(n);
std::cout << "cadena con estado inicial nuevo sin estado inicial nuevo\n";
int differences = 0;
for (const std::string& w : all_strings(n.alphabet, max_len)) {
bool in_good = accepts(good, w);
bool in_bad = accepts(bad, w);
if (in_good != in_bad) {
std::cout << w << std::string(w.size() < 9 ? 9 - w.size() : 1, ' ')
<< (in_good ? "acepta " : "rechaza ")
<< (in_bad ? "acepta" : "rechaza") << '\n';
differences++;
}
}
std::cout << differences << " cadenas de longitud a lo sumo " << max_len << " en las que no coinciden\n";
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}# Algunas a, después algunas b, después algunas c: cada bloque puede ser vacío.
# Las transiciones ε pasan al bloque siguiente sin leer nada.
states: qa qb qc
alphabet: a b c
start: qa
accept: qc
delta:
qa a qa
qa eps qb
qb b qb
qb eps qc
qc c qc# Cadenas binarias que contienen 101 o 11.
# q0: espera. q1: adivinó que aquí empieza el patrón y leyó su primer 1.
# q2: leyó el 0 del medio, o se lo saltó con la transición ε. q3: ya leyó el patrón completo.
states: q0 q1 q2 q3
alphabet: 0 1
start: q0
accept: q3
delta:
q0 0 q0
q0 1 q0 q1
q1 0 q2
q1 eps q2
q2 1 q3
q3 0 q3
q3 1 q3# 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# Cadenas binarias que terminan en 01, con un NFA que adivina dónde empieza el 01 final.
states: q0 q1 q2
alphabet: 0 1
start: q0
accept: q2
delta:
q0 0 q0 q1
q0 1 q0
q1 1 q2# Cadenas binarias con una cantidad par de unos.
states: par impar
alphabet: 0 1
start: par
accept: par
delta:
par 0 par
par 1 impar
impar 0 impar
impar 1 par# El tercer símbolo desde el final es 1.
# q0: espera. q1: adivinó que el 1 que acaba de leer es el tercero desde el final.
# q2: leyó un símbolo más. q3: leyó dos más.
states: q0 q1 q2 q3
alphabet: 0 1
start: q0
accept: q3
delta:
q0 0 q0
q0 1 q0 q1
q1 0 q2
q1 1 q2
q2 0 q3
q2 1 q3# Algunos ceros y después un solo 1: 1, 01, 001, ...
# El estado inicial tiene una flecha que vuelve a él: es el ejemplo de la estrella.
states: q0 q1
alphabet: 0 1
start: q0
accept: q1
delta:
q0 0 q0
q0 1 q1Errores
Ejemplos con errores a propósito: no compilan, fallan o dan un resultado incorrecto. Los apuntes explican cada uno.
# No es un NFA: a la transición ε le falta el destino. (eps va en el lugar del símbolo.)
states: q0 q1
alphabet: 0 1
start: q0
accept: q1
delta:
q0 1 q1
q0 eps# No es un NFA: una transición lleva a un estado que no está en states.
states: q0 q1
alphabet: 0 1
start: q0
accept: q1
delta:
q0 0 q0
q0 1 q0 q2// Dos construcciones INCORRECTAS, para los ejemplos de los apuntes. Parecen razonables y
// fallan con cadenas concretas: wrong_star.cpp y swap_accept.cpp muestran con cuáles, y
// test_closure.cpp lo comprueba.
#ifndef WRONG_CONSTRUCTIONS_H
#define WRONG_CONSTRUCTIONS_H
#include <string>
#include "../nfa.h"
// "Estrella" sin estado inicial nuevo: marca el inicial como de aceptación, para aceptar ε, y
// agrega las transiciones ε de los estados de aceptación al inicial.
// Falla cuando alguna flecha vuelve al estado inicial: una cadena que regresa a él queda
// aceptada aunque no sea una concatenación de cadenas del lenguaje.
inline Nfa star_without_new_start(const Nfa& n1) {
Nfa n = n1;
for (const std::string& f : n1.accept) {
n.delta[{f, EPS}].insert(n1.start);
}
n.accept.insert(n1.start);
return n;
}
// "Complemento" de un NFA: la misma máquina con F cambiado por Q − F.
// En un DFA es correcto. En un NFA no: una cadena con un camino que acepta y otro que no
// queda aceptada antes y después del intercambio.
inline Nfa swap_accept(const Nfa& n1) {
Nfa n = n1;
n.accept.clear();
for (const std::string& state : n1.states) {
if (n1.accept.count(state) == 0) {
n.accept.insert(state);
}
}
return n;
}
#endifPruebas
Comprueban lo que afirman los apuntes; se ejecutan con make test.
// Pruebas de las construcciones de cierre (sesión B): cada una se compara con el predicado que
// define la operación, calculado sin autómatas. Y las dos construcciones incorrectas de los
// apuntes fallan con las cadenas que los apuntes dicen.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <functional>
#include <random>
#include <string>
#include <vector>
#include "errors/wrong_constructions.h"
#include "nfa.h"
#include "strings.h"
#include "test_helpers.h"
using Predicate = std::function<bool(const std::string&)>;
// w ∈ AB: alguna partición w = uv tiene u ∈ A y v ∈ B.
static bool in_concat(const Predicate& in_a, const Predicate& in_b, const std::string& w) {
for (std::size_t cut = 0; cut <= w.size(); cut++) {
if (in_a(w.substr(0, cut)) && in_b(w.substr(cut))) {
return true;
}
}
return false;
}
// w ∈ A*: w se parte en cero o más trozos de A. splits[i] dice si el prefijo de longitud i está en A*.
static bool in_star(const Predicate& in_a, const std::string& w) {
std::vector<bool> splits(w.size() + 1, false);
splits[0] = true;
for (std::size_t end = 1; end <= w.size(); end++) {
for (std::size_t from = 0; from < end && !splits[end]; from++) {
splits[end] = splits[from] && in_a(w.substr(from, end - from));
}
}
return splits[w.size()];
}
static void test_examples_of_notes() {
Nfa even = load_nfa("machines/even_ones.dfa");
Nfa ends = load_nfa("machines/ends_01.dfa");
Predicate in_even = [](const std::string& w) { return count_ones(w) % 2 == 0; };
Predicate in_ends = [](const std::string& w) { return ends_with(w, "01"); };
std::vector<std::string> words = all_strings({'0', '1'}, 9);
// Unión: 1 + 2 + 3 estados, y el mismo lenguaje que el producto de la semana 1.
Nfa either = nfa_union(even, ends);
assert(either.states == (std::vector<std::string>{"s", "1.par", "1.impar", "2.q0", "2.q1", "2.q2"}));
assert(delta_of(either, "s", EPS) == (StateSet{"1.par", "2.q0"}));
assert(either.accept == (StateSet{"1.par", "2.q2"}));
Dfa product_union = product(load_dfa("machines/even_ones.dfa"), load_dfa("machines/ends_01.dfa"), Combine::Union);
for (const std::string& w : words) {
assert(accepts(either, w) == (in_even(w) || in_ends(w)));
assert(accepts(either, w) == accepts(product_union, w));
}
assert(run(either, "").front() == (StateSet{"s", "1.par", "2.q0"}));
// Concatenación: termina en 01, y después una cantidad par de unos.
Nfa both = nfa_concat(ends, even);
assert(both.states.size() == 5 && both.start == "1.q0");
assert(both.accept == (StateSet{"2.par"}));
assert(delta_of(both, "1.q2", EPS) == (StateSet{"2.par"}));
for (const std::string& w : words) {
assert(accepts(both, w) == in_concat(in_ends, in_even, w));
}
// 0111 = 01 · 11 está; 011 no: después de cualquier 01 queda una cantidad impar de unos.
assert(accepts(both, "0111") && accepts(both, "01") && !accepts(both, "011") && !accepts(both, ""));
// Estrella de 0*1: ε y las cadenas que terminan en 1.
Nfa one = load_nfa("machines/zeros_then_one.nfa");
Predicate in_one = [](const std::string& w) { return !w.empty() && w.back() == '1' && count_ones(w) == 1; };
Nfa star = nfa_star(one);
assert(star.states == (std::vector<std::string>{"s", "q0", "q1"}));
assert(star.start == "s" && star.accept == (StateSet{"s", "q1"}));
assert(delta_of(star, "s", EPS) == (StateSet{"q0"}) && delta_of(star, "q1", EPS) == (StateSet{"q0"}));
for (const std::string& w : words) {
assert(accepts(star, w) == in_star(in_one, w));
assert(accepts(star, w) == (w.empty() || w.back() == '1'));
}
// La estrella sin estado inicial nuevo acepta 0, que no está en (0*1)*: es exactamente
// las cadenas no vacías que terminan en 0 lo que acepta de más.
Nfa wrong = star_without_new_start(one);
assert(accepts(wrong, "0") && !accepts(star, "0") && !in_star(in_one, "0"));
assert(accepts(wrong, "") && accepts(wrong, "01"));
for (const std::string& w : words) {
assert(accepts(wrong, w)); // acepta todas las cadenas
}
// Reverso: de "termina en 01" a "empieza con 10", y de "tercero desde el final" a "tercero".
Nfa backwards = nfa_reverse(ends);
assert(backwards.states.size() == 4 && backwards.accept == (StateSet{"q0"}));
assert(delta_of(backwards, "s", EPS) == (StateSet{"q2"}));
Nfa third = load_nfa("machines/third_from_end.nfa");
Nfa third_reversed = nfa_reverse(third);
for (const std::string& w : words) {
assert(accepts(backwards, w) == (w.size() >= 2 && w[0] == '1' && w[1] == '0'));
assert(accepts(third_reversed, w) == (w.size() >= 3 && w[2] == '1'));
}
// El reverso de un DFA no es un DFA: de q1 salen tres flechas con 0 (eran q0→q1, q1→q1 y q2→q1).
assert(delta_of(backwards, "q1", '0').size() == 3);
}
// Intercambiar F por Q − F en un NFA no da el complemento.
static void test_swap_accept() {
Nfa third = load_nfa("machines/third_from_end.nfa");
Nfa swapped = swap_accept(third);
assert(swapped.accept == (StateSet{"q0", "q1", "q2"}));
// 100 está en el lenguaje y el NFA intercambiado también la acepta.
assert(accepts(third, "100") && accepts(swapped, "100"));
// De hecho acepta todo, porque q0 siempre está activo.
Dfa right = complement(subset_construction(third));
for (const std::string& w : all_strings({'0', '1'}, 9)) {
assert(accepts(swapped, w));
assert(accepts(right, w) == !accepts(third, w)); // el camino correcto: primero el DFA
}
assert(!accepts(right, "100") && accepts(right, "000"));
}
// Las cuatro construcciones con NFA al azar, que tienen transiciones ε, ciclos y flechas que
// vuelven al estado inicial.
static int test_random() {
std::mt19937 rng(40404);
std::vector<std::string> words = all_strings({'0', '1'}, 5);
int machines = 0;
for (int round = 0; round < 100; round++) {
Nfa a = random_nfa(rng, 1 + static_cast<int>(rng() % 4));
Nfa b = random_nfa(rng, 1 + static_cast<int>(rng() % 4));
Predicate in_a = [&a](const std::string& w) { return accepts_by_paths(a, w); };
Predicate in_b = [&b](const std::string& w) { return accepts_by_paths(b, w); };
Nfa either = nfa_union(a, b);
Nfa both = nfa_concat(a, b);
Nfa star = nfa_star(a);
Nfa backwards = nfa_reverse(a);
assert(either.states.size() == a.states.size() + b.states.size() + 1);
assert(both.states.size() == a.states.size() + b.states.size());
assert(star.states.size() == a.states.size() + 1 && backwards.states.size() == a.states.size() + 1);
for (const std::string& w : words) {
assert(accepts(either, w) == (in_a(w) || in_b(w)));
assert(accepts(both, w) == in_concat(in_a, in_b, w));
assert(accepts(star, w) == in_star(in_a, w));
assert(accepts(backwards, w) == in_a(reversed(w)));
}
machines++;
}
return machines;
}
int main() {
test_examples_of_notes();
test_swap_accept();
int machines = test_random();
std::printf("test_closure: ok (unión, concatenación, estrella y reverso; %d pares de NFA al azar)\n", machines);
}// Ayudas compartidas por las pruebas: predicados sobre cadenas, la aceptación de un NFA
// calculada directamente con la definición (buscando un camino) y NFA al azar con semilla fija.
#ifndef TEST_HELPERS_H
#define TEST_HELPERS_H
#include <algorithm>
#include <cstddef>
#include <random>
#include <set>
#include <string>
#include <utility>
#include <vector>
#include "nfa.h"
inline bool ends_with(const std::string& w, const std::string& tail) {
return w.size() >= tail.size() && w.compare(w.size() - tail.size(), tail.size(), tail) == 0;
}
inline bool contains(const std::string& w, const std::string& piece) {
return w.find(piece) != std::string::npos;
}
inline int count_ones(const std::string& w) {
return static_cast<int>(std::count(w.begin(), w.end(), '1'));
}
inline std::string reversed(const std::string& w) {
return std::string(w.rbegin(), w.rend());
}
// ¿Hay un camino desde q, habiendo leído pos símbolos de w, que termine en F con toda la cadena leída?
// Es la definición de aceptación, sin conjuntos de estados activos. on_path evita los ciclos de ε.
inline bool path_exists(const Nfa& n, const std::string& w, const std::string& q, std::size_t pos,
std::set<std::pair<std::string, std::size_t>>& on_path) {
if (pos == w.size() && n.accept.count(q) > 0) {
return true;
}
if (!on_path.insert({q, pos}).second) {
return false;
}
bool found = false;
if (pos < w.size()) {
for (const std::string& r : delta_of(n, q, w[pos])) {
found = found || path_exists(n, w, r, pos + 1, on_path);
}
}
for (const std::string& r : delta_of(n, q, EPS)) {
found = found || path_exists(n, w, r, pos, on_path);
}
on_path.erase({q, pos});
return found;
}
inline bool accepts_by_paths(const Nfa& n, const std::string& w) {
std::set<std::pair<std::string, std::size_t>> on_path;
return path_exists(n, w, n.start, 0, on_path);
}
// Un NFA al azar con size estados sobre {0, 1}, con transiciones ε (también ciclos de ε),
// pares sin transición y estados inalcanzables. Solo usa rng() y restos, para que salga igual
// en cualquier plataforma.
inline Nfa random_nfa(std::mt19937& rng, int size) {
Nfa n;
n.alphabet = {'0', '1'};
for (int i = 0; i < size; i++) {
n.states.push_back("p" + std::to_string(i));
}
n.start = n.states[rng() % size];
for (const std::string& state : n.states) {
if (rng() % 3 == 0) {
n.accept.insert(state);
}
for (char a : {'0', '1', EPS}) {
// Pocas transiciones ε, para que no todo quede conectado con todo.
unsigned arrows = (a == EPS) ? (rng() % 4 == 0 ? 1 : 0) : rng() % 3;
for (unsigned k = 0; k < arrows; k++) {
n.delta[{state, a}].insert(n.states[rng() % size]);
}
}
}
return n;
}
#endif// Pruebas de lo que los apuntes afirman sobre los NFA del capítulo (sesión A).
// Cada autómata de machines/ se compara con una función de C++ que decide el mismo lenguaje
// mirando la cadena completa, y la simulación con conjuntos de estados activos se compara
// con la definición: existe un camino que termina en un estado de aceptación.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <functional>
#include <random>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
#include "kth.h"
#include "nfa.h"
#include "strings.h"
#include "test_helpers.h"
// Compara N con el predicado y con la definición por caminos. Devuelve cuántas cadenas revisó.
static std::size_t check_language(const std::string& path, std::size_t max_len,
const std::function<bool(const std::string&)>& in_language) {
Nfa n = load_nfa(path);
std::vector<std::string> words = all_strings(n.alphabet, max_len);
for (const std::string& w : words) {
assert(accepts(n, w) == in_language(w));
assert(accepts_by_paths(n, w) == in_language(w));
}
return words.size();
}
static bool third_from_end_is_one(const std::string& w) {
return w.size() >= 3 && w[w.size() - 3] == '1';
}
// a*b*c*: la cadena está ordenada.
static bool in_blocks(const std::string& w) {
for (std::size_t i = 1; i < w.size(); i++) {
if (w[i - 1] > w[i]) {
return false;
}
}
return true;
}
static std::size_t test_languages_of_machines() {
std::size_t total = 0;
total += check_language("machines/third_from_end.nfa", 10, third_from_end_is_one);
total += check_language("machines/contains_101_or_11.nfa", 10,
[](const std::string& w) { return contains(w, "101") || contains(w, "11"); });
total += check_language("machines/abc_blocks.nfa", 7, in_blocks);
total += check_language("machines/ends_01.nfa", 10, [](const std::string& w) { return ends_with(w, "01"); });
total += check_language("machines/zeros_then_one.nfa", 10, [](const std::string& w) {
return !w.empty() && w.back() == '1' && count_ones(w) == 1;
});
// Todo archivo .dfa es un .nfa válido, y como NFA acepta lo mismo.
total += check_language("machines/even_ones.dfa", 10, [](const std::string& w) { return count_ones(w) % 2 == 0; });
total += check_language("machines/ends_01.dfa", 10, [](const std::string& w) { return ends_with(w, "01"); });
return total;
}
static void test_runs_of_notes() {
Nfa third = load_nfa("machines/third_from_end.nfa");
// El conjunto de estados activos después de cada símbolo, como lo imprime run_nfa.
assert(run(third, "0110") == (std::vector<StateSet>{{"q0"}, {"q0"}, {"q0", "q1"}, {"q0", "q1", "q2"},
{"q0", "q2", "q3"}}));
assert(accepts(third, "0110") && accepts(third, "100") && !accepts(third, "") && !accepts(third, "011"));
assert(run(third, "100").back() == (StateSet{"q0", "q3"}));
// Sin transiciones ε, la clausura no agrega nada.
assert(eps_closure(third, {"q0", "q2"}) == (StateSet{"q0", "q2"}));
// De q3 no sale ninguna flecha: δ(q3, 0) = ∅.
assert(delta_of(third, "q3", '0').empty() && delta_of(third, "q3", EPS).empty());
assert(delta_of(third, "q0", '1') == (StateSet{"q0", "q1"}));
Nfa either = load_nfa("machines/contains_101_or_11.nfa");
assert(eps_closure(either, {"q1"}) == (StateSet{"q1", "q2"}));
assert(eps_closure(either, {"q0"}) == (StateSet{"q0"}));
assert(run(either, "01011") ==
(std::vector<StateSet>{{"q0"}, {"q0"}, {"q0", "q1", "q2"}, {"q0", "q2"}, {"q0", "q1", "q2", "q3"},
{"q0", "q1", "q2", "q3"}}));
assert(run(either, "0100").back() == (StateSet{"q0"}));
assert(accepts(either, "01011") && !accepts(either, "0100") && accepts(either, "11") && !accepts(either, "10"));
Nfa blocks = load_nfa("machines/abc_blocks.nfa");
// La clausura sigue varias transiciones ε seguidas, y el estado inicial ya llega activo a qc.
assert(eps_closure(blocks, {"qa"}) == (StateSet{"qa", "qb", "qc"}));
assert(eps_closure(blocks, {"qb"}) == (StateSet{"qb", "qc"}));
assert(eps_closure(blocks, {}).empty());
assert(accepts(blocks, "") && accepts(blocks, "aacc") && accepts(blocks, "b") && !accepts(blocks, "ba"));
assert(run(blocks, "abca") ==
(std::vector<StateSet>{{"qa", "qb", "qc"}, {"qa", "qb", "qc"}, {"qb", "qc"}, {"qc"}, {}}));
}
// Propiedades de la clausura ε: contiene a S, aplicarla dos veces no cambia nada, y crece con S.
static void test_closure_properties() {
std::mt19937 rng(20202);
for (int round = 0; round < 300; round++) {
Nfa n = random_nfa(rng, 1 + static_cast<int>(rng() % 6));
StateSet small;
StateSet big;
for (const std::string& state : n.states) {
unsigned coin = rng() % 3;
if (coin == 0) {
small.insert(state);
}
if (coin <= 1) {
big.insert(state);
}
}
StateSet closed = eps_closure(n, small);
assert(std::includes(closed.begin(), closed.end(), small.begin(), small.end()));
assert(eps_closure(n, closed) == closed);
StateSet closed_big = eps_closure(n, big);
assert(std::includes(closed_big.begin(), closed_big.end(), closed.begin(), closed.end()));
}
}
// El lema de los estados activos: la simulación con conjuntos acepta exactamente cuando la
// definición dice que hay un camino. Con NFA al azar, que tienen ciclos de ε y caminos que mueren.
static int test_active_sets_against_paths() {
std::mt19937 rng(10102);
int machines = 0;
for (int round = 0; round < 200; round++) {
Nfa n = random_nfa(rng, 1 + static_cast<int>(rng() % 6));
check_nfa(n);
for (const std::string& w : all_strings(n.alphabet, 6)) {
assert(accepts(n, w) == accepts_by_paths(n, w));
}
machines++;
}
return machines;
}
static void test_format() {
// Leer, escribir y volver a leer da la misma máquina.
for (const char* path : {"machines/third_from_end.nfa", "machines/contains_101_or_11.nfa",
"machines/abc_blocks.nfa", "machines/ends_01.dfa"}) {
Nfa n = load_nfa(path);
std::ostringstream text;
write_nfa(text, n);
std::istringstream again(text.str());
Nfa copy = read_nfa(again);
assert(copy.states == n.states && copy.alphabet == n.alphabet && copy.delta == n.delta);
assert(copy.start == n.start && copy.accept == n.accept);
}
// Un par de estado y símbolo puede estar en varias líneas: los destinos se juntan.
std::istringstream split("states: a b\nalphabet: 0\nstart: a\naccept: b\ndelta:\na 0 a\n# otra\na 0 b a\na eps b\n");
Nfa joined = read_nfa(split);
assert(delta_of(joined, "a", '0') == (StateSet{"a", "b"}) && delta_of(joined, "a", EPS) == (StateSet{"b"}));
// kth_from_end(3) es la máquina del archivo.
Nfa third = load_nfa("machines/third_from_end.nfa");
Nfa built = kth_from_end(3);
assert(built.states == third.states && built.delta == third.delta && built.accept == third.accept);
// Un DFA visto como NFA: δ(q, a) tiene exactamente un estado y no hay transiciones ε.
Nfa even = to_nfa(load_dfa("machines/even_ones.dfa"));
for (const std::string& state : even.states) {
assert(delta_of(even, state, '0').size() == 1 && delta_of(even, state, '1').size() == 1);
assert(delta_of(even, state, EPS).empty());
}
// Un NFA no suele ser un archivo .dfa válido.
bool failed = false;
try {
load_dfa("machines/third_from_end.nfa");
} catch (const std::runtime_error&) {
failed = true;
}
assert(failed);
for (const char* path : {"errors/unknown_state.nfa", "errors/eps_as_target.nfa"}) {
failed = false;
try {
load_nfa(path);
} catch (const std::runtime_error&) {
failed = true;
}
assert(failed);
}
}
int main() {
std::size_t words = test_languages_of_machines();
test_runs_of_notes();
test_closure_properties();
int machines = test_active_sets_against_paths();
test_format();
std::printf("test_nfa: ok (7 autómatas, %zu cadenas en total; %d NFA al azar contra la definición)\n", words,
machines);
}// Pruebas de la construcción de subconjuntos (sesión B): el DFA construido acepta lo mismo
// que el NFA, sigue al conjunto de estados activos cadena por cadena, y tiene los estados que
// dicen los apuntes.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <random>
#include <set>
#include <string>
#include <vector>
#include "kth.h"
#include "nfa.h"
#include "strings.h"
#include "test_helpers.h"
// El lema de la construcción: δ_D*(E({q0}), w) es el conjunto de estados activos de N con w.
// Y lo que importa: D acepta w si y solo si N acepta w. Devuelve cuántas cadenas revisó.
static std::size_t check_equivalent(const Nfa& n, const Dfa& d, std::size_t max_len) {
std::vector<std::string> words = all_strings(n.alphabet, max_len);
for (const std::string& w : words) {
assert(delta_star(d, d.start, w) == set_name(n, delta_star(n, {n.start}, w)));
assert(accepts(d, w) == accepts(n, w));
}
return words.size();
}
static void test_machines_of_notes() {
// Tercero desde el final: 4 estados en el NFA, 8 subconjuntos alcanzables de 16.
Nfa third = load_nfa("machines/third_from_end.nfa");
std::vector<StateSet> subsets;
Dfa d3 = subset_construction(third, &subsets);
assert(d3.states.size() == 8 && subsets.size() == 8);
assert(reachable(d3).size() == 8);
assert(d3.start == "{q0}");
assert(d3.accept == (std::set<std::string>{"{q0,q3}", "{q0,q1,q3}", "{q0,q2,q3}", "{q0,q1,q2,q3}"}));
// Algunas casillas de la tabla de los apuntes.
assert(step(d3, "{q0}", '1') == "{q0,q1}");
assert(step(d3, "{q0,q1}", '0') == "{q0,q2}");
assert(step(d3, "{q0,q1,q2}", '0') == "{q0,q2,q3}");
assert(step(d3, "{q0,q3}", '0') == "{q0}");
assert(step(d3, "{q0,q1,q2,q3}", '1') == "{q0,q1,q2,q3}");
// Todos los subconjuntos alcanzables contienen a q0, y cada uno es de aceptación si tiene a q3.
for (std::size_t i = 0; i < subsets.size(); i++) {
assert(subsets[i].count("q0") == 1);
assert((d3.accept.count(d3.states[i]) > 0) == (subsets[i].count("q3") > 0));
}
// La ejecución del DFA es la de run_nfa, conjunto por conjunto.
assert(run(d3, "0110") ==
(std::vector<std::string>{"{q0}", "{q0}", "{q0,q1}", "{q0,q1,q2}", "{q0,q2,q3}"}));
check_equivalent(third, d3, 10);
// El estado recuerda los tres últimos símbolos: las 8 cadenas de longitud 3 van a 8 estados distintos.
std::set<std::string> ends;
for (const std::string& w : all_strings({'0', '1'}, 3)) {
if (w.size() == 3) {
ends.insert(delta_star(d3, d3.start, w));
}
}
assert(ends.size() == 8);
// Contiene 101 o 11: con ε. 6 alcanzables.
Nfa either = load_nfa("machines/contains_101_or_11.nfa");
Dfa d_either = subset_construction(either);
assert(d_either.states.size() == 6 && d_either.start == "{q0}");
assert(step(d_either, "{q0}", '1') == "{q0,q1,q2}"); // la clausura ε agrega q2
assert(step(d_either, "{q0,q1,q2}", '0') == "{q0,q2}");
check_equivalent(either, d_either, 10);
// a*b*c*: el inicial del DFA es E({qa}), y aparece el conjunto vacío como estado trampa.
Nfa blocks = load_nfa("machines/abc_blocks.nfa");
Dfa d_blocks = subset_construction(blocks);
assert(d_blocks.states == (std::vector<std::string>{"{qa,qb,qc}", "{qb,qc}", "{qc}", "{}"}));
assert(d_blocks.start == "{qa,qb,qc}" && d_blocks.accept.count("{qa,qb,qc}") == 1);
assert(d_blocks.accept.count("{}") == 0);
for (char a : blocks.alphabet) {
assert(step(d_blocks, "{}", a) == "{}");
}
check_equivalent(blocks, d_blocks, 7);
// Termina en 01: el NFA de 3 estados da un DFA de 3 estados, con el mismo lenguaje que el de la semana 1.
Nfa ends_nfa = load_nfa("machines/ends_01.nfa");
Dfa d_ends = subset_construction(ends_nfa);
Dfa week1 = load_dfa("machines/ends_01.dfa");
assert(d_ends.states == (std::vector<std::string>{"{q0}", "{q0,q1}", "{q0,q2}"}));
for (const std::string& w : all_strings({'0', '1'}, 10)) {
assert(accepts(d_ends, w) == accepts(week1, w));
}
check_equivalent(ends_nfa, d_ends, 10);
// Un DFA pasado por la construcción sale igual, con cada estado q convertido en {q}.
Dfa again = subset_construction(to_nfa(week1));
assert(again.states == (std::vector<std::string>{"{q0}", "{q1}", "{q2}"}));
}
// La tabla de los apuntes: para "el k-ésimo símbolo desde el final es 1", el NFA tiene k + 1
// estados y la construcción da exactamente 2^k.
static void test_kth_table() {
for (int k = 1; k <= 12; k++) {
Nfa n = kth_from_end(k);
Dfa d = subset_construction(n);
assert(n.states.size() == static_cast<std::size_t>(k) + 1);
assert(d.states.size() == (std::size_t{1} << k));
if (k <= 6) {
for (const std::string& w : all_strings({'0', '1'}, 10)) {
bool in_language = w.size() >= static_cast<std::size_t>(k) && w[w.size() - k] == '1';
assert(accepts(d, w) == in_language);
}
}
}
}
static int test_random() {
std::mt19937 rng(30303);
int machines = 0;
for (int round = 0; round < 200; round++) {
Nfa n = random_nfa(rng, 1 + static_cast<int>(rng() % 6));
Dfa d = subset_construction(n);
assert(d.states.size() <= (std::size_t{1} << n.states.size()));
assert(reachable(d).size() == d.states.size());
check_equivalent(n, d, 6);
// Y contra la definición por caminos, que no usa conjuntos.
for (const std::string& w : all_strings(n.alphabet, 5)) {
assert(accepts(d, w) == accepts_by_paths(n, w));
}
machines++;
}
return machines;
}
int main() {
test_machines_of_notes();
test_kth_table();
int machines = test_random();
std::printf("test_subset: ok (4 autómatas de los apuntes, k de 1 a 12, %d NFA al azar)\n", machines);
}Laboratorio
Archivos de partida del laboratorio de la semana.
TIEMPO = 2
VERIFICADOR = verificador.cpp
include ../../../lab.mk# De NFA a DFA
En clase se demostró que todo autómata finito no determinista (NFA) tiene un autómata finito determinista (DFA)
equivalente, con la construcción de subconjuntos. Aquí la programan: su programa recibe un NFA, que puede tener
transiciones $\varepsilon$, y escribe un DFA que reconoce el mismo lenguaje.
Si el NFA es $N = (Q, \Sigma, \delta, q_0, F)$ y $E(S)$ es la clausura $\varepsilon$ de un conjunto de estados
$S$, el DFA de la construcción tiene un estado por cada conjunto de estados de $N$:
- su estado inicial es $E(\{q_0\})$;
- desde el conjunto $S$, con el símbolo $a$, va al conjunto $E\bigl(\bigcup_{q \in S} \delta(q, a)\bigr)$;
- un conjunto es de aceptación si contiene algún estado de $F$.
## Entrada
La descripción de un NFA en el formato `.nfa` de [`code/formats.md`](../../../formats.md):
```text
# Cadenas binarias que contienen 101 o 11.
states: q0 q1 q2 q3
alphabet: 0 1
start: q0
accept: q3
delta:
q0 0 q0
q0 1 q0 q1
q1 0 q2
q1 eps q2
q2 1 q3
q3 0 q3
q3 1 q3
```
- Una línea que empieza con `#` es un comentario. Puede haber comentarios en cualquier línea, también entre
las transiciones.
- Puede haber líneas vacías antes de `delta:`. Después de `delta:` no hay líneas vacías, y la descripción
termina donde termina la entrada.
- `states:`, `alphabet:`, `start:`, `accept:` y `delta:` vienen siempre en ese orden. `accept:` puede no tener
ningún estado.
- Después de `delta:`, cada línea es `estado símbolo destino…`, con uno o más destinos. Una transición
$\varepsilon$ lleva `eps` en el lugar del símbolo.
- Un par de estado y símbolo que no aparece no tiene transiciones. Puede no haber ninguna línea después de
`delta:`.
- El mismo par puede aparecer en varias líneas, y un destino puede estar repetido: los destinos de todas esas
líneas se juntan en un solo conjunto.
## Salida
Un DFA equivalente al NFA de la entrada, en el formato `.dfa` del mismo documento: los cinco campos en su orden
y, después de `delta:`, exactamente una línea `estado símbolo destino` por cada par de estado y símbolo.
- El alfabeto del DFA tiene los mismos símbolos que el del NFA, en cualquier orden.
- Los nombres de los estados los eligen ustedes. Cada uno tiene entre 1 y 20 caracteres visibles, sin espacios,
no empieza con `#` y no termina con `:`.
- El DFA tiene **a lo sumo 10 000 estados**.
Hay muchas respuestas correctas: los estados pueden llamarse de otro modo, ir en otro orden o ser más o menos
que los de `casos/NN.out`. El juez no compara textos. Usa un verificador, que se describe más abajo.
## Límites
- $1 \leq |Q| \leq 60$ y $1 \leq |\Sigma| \leq 10$.
- El nombre de un estado tiene entre 1 y 20 caracteres visibles, sin espacios. No empieza con `#` ni termina con
`:`. Un nombre puede ser prefijo de otro, puede ser igual a un símbolo, y puede ser `eps`: en una línea de
`delta:`, lo que decide qué es cada palabra es su posición.
- Un símbolo es un solo carácter visible, distinto de `#`.
- Se garantiza que la construcción de subconjuntos, **si solo genera los subconjuntos alcanzables** desde
$E(\{q_0\})$, produce a lo sumo 5000 estados.
- La entrada siempre describe un NFA válido: no tienen que detectar errores en la descripción.
## Ejemplo
Para la entrada de arriba, una salida correcta es:
```text
states: s0 s1 s2 s3 s4 s5
alphabet: 0 1
start: s0
accept: s3 s4 s5
delta:
s0 0 s0
s0 1 s1
s1 0 s2
s1 1 s3
s2 0 s0
s2 1 s3
s3 0 s4
s3 1 s3
s4 0 s5
s4 1 s3
s5 0 s5
s5 1 s3
```
Es la de `casos/02.out`. Los seis estados son los subconjuntos alcanzables, numerados en el orden en que una
cola los encuentra:
| Nombre | Subconjunto |
|---|---|
| `s0` | $\{q_0\}$ |
| `s1` | $\{q_0, q_1, q_2\}$ |
| `s2` | $\{q_0, q_2\}$ |
| `s3` | $\{q_0, q_1, q_2, q_3\}$ |
| `s4` | $\{q_0, q_2, q_3\}$ |
| `s5` | $\{q_0, q_3\}$ |
Desde $\{q_0\}$ con $\mathtt{1}$ se llega a $q_0$ y a $q_1$, y la clausura $\varepsilon$ agrega $q_2$: por eso
`s0 1 s1`. El NFA tiene 4 estados y $2^4 = 16$ subconjuntos, pero desde el inicial solo se alcanzan estos 6.
## Tiempo
2 segundos por caso. Se compila con `g++ -Wall -Wextra -std=c++20 -O2`.
Un NFA de 60 estados tiene $2^{60}$ subconjuntos, más de $10^{18}$. Un programa que escribe un estado por cada
subconjunto no termina nunca con ese caso, y el juez da `TLE`. Con 18 estados sí termina, pero escribe $2^{18} =
262\,144$ estados y el verificador lo rechaza por pasarse de 10 000. La construcción tiene que partir de
$E(\{q_0\})$ y generar solo los subconjuntos que va encontrando.
## El verificador
`make test` compila `verificador.cpp` y el juez lo llama con cada caso. Pueden leerlo: son las ideas de la semana
1. Con la salida de su programa hace tres cosas.
1. **Comprueba que es un DFA bien formado**: los cinco campos, ningún estado repetido, el estado inicial y los
de aceptación dentro de `states:`, y exactamente una transición por cada par de estado y símbolo.
2. **Comprueba los límites**: el mismo alfabeto que el NFA, a lo sumo 10 000 estados, nombres de hasta 20
caracteres.
3. **Compara los lenguajes.** Recorre a la vez el NFA, con su conjunto de estados activos, y el DFA que
ustedes entregaron, como en la construcción del producto: parte del par formado por $E(\{q_0\})$ y su estado
inicial, y avanza en los dos con cada símbolo. Si llega a un par en el que uno acepta y el otro no, las
máquinas no son equivalentes, y la cadena que llevó hasta ese par lo demuestra.
Cuando algo falla, el juez muestra el motivo al lado del veredicto. Con una solución que olvida la clausura
$\varepsilon$ del estado inicial, el caso 07 da:
```text
07 WA 0.01 s no reconocen el mismo lenguaje: la cadena vacía la acepta el NFA y la rechaza el DFA
```
La cadena que muestra es de las más cortas en las que las dos máquinas difieren: síganla a mano en el NFA y en
su DFA.
## Qué se practica aquí
En `code/week-02/nfa.h` hay un `struct Nfa` y una función `subset_construction`: es lo que usan los ejemplos de
los apuntes, y pueden leerla cuanto quieran. Está escrita para que se lea como la definición, con conjuntos de
nombres, y no para ser rápida. `solution.cpp` se escribe **sin incluir `nfa.h`**: el juez compila ese único
archivo.
El trabajo del laboratorio está en tres decisiones:
- **Cómo representar un conjunto de estados** para que compararlos y buscarlos sea barato. Con $|Q| \leq 60$,
un conjunto cabe en un entero de 64 bits, con un bit por estado. La unión es `|` y preguntar si hay algún
estado de aceptación es `&`.
- **Cómo saber si un subconjunto ya apareció**, para no generarlo dos veces: un `std::map` o un
`std::unordered_map` del conjunto a su número.
- **Qué nombre darle a cada uno.** El nombre natural, $\{q_0, q_1, q_2\}$, puede pasar de 20 caracteres. Basta
el número de orden: `s0`, `s1`, `s2`…
Los casos traen, entre otros: transiciones $\varepsilon$ en cadena y en ciclo, un NFA sin estados de aceptación,
uno con un solo estado y ninguna transición, estados inalcanzables, un DFA como entrada, un estado que se llama
`eps`, pares repartidos en varias líneas y cuatro casos grandes.
## Cómo avanzar
```sh
make # compila solution.cpp en build/
make test # corre el juez con todos los casos
```
1. **Lean el NFA.** Numeren los estados y los símbolos en el orden en que aparecen, y guarden $\delta$ por
números. Empiecen con `casos/01.in`, que no tiene transiciones $\varepsilon$.
2. **Calculen la clausura $\varepsilon$** con una búsqueda en el grafo que solo tiene las flechas
$\varepsilon$: desde cada estado del conjunto, sigan esas flechas hasta que no aparezca ningún estado nuevo.
Antes de programarla, calculen a mano $E(\{q_a\})$ en `casos/03.in`.
3. **Generen los subconjuntos alcanzables con una cola.** El primero es $E(\{q_0\})$. Mientras la cola no esté
vacía, saquen un subconjunto $S$ y calculen, para cada símbolo $a$, el conjunto
$E\bigl(\bigcup_{q \in S} \delta(q, a)\bigr)$. Si es nuevo, denle el siguiente número y pónganlo en la cola.
El conjunto vacío es un subconjunto como cualquier otro: si aparece, es el estado trampa del DFA.
4. **Escriban el DFA** y pásenlo por el juez. Si un caso da `WA`, lean el motivo que da el verificador y sigan a
mano la cadena que muestra.
5. **Midan** cuántos estados salen con la familia de la sección siguiente.
Mientras desarrollan, compilen con sanitizers, como explica [`labs/README.md`](../../../../labs/README.md).
Para ver su DFA funcionando, pásenle la salida al simulador que escribieron en el laboratorio de la semana 1,
agregando el bloque de cadenas:
```sh
{ build/solution < casos/02.in; printf 'strings: 3\n0101\n0100\n\n'; } | ../../../week-01/lab/dfa_sim/build/solution
```
Debe imprimir `acepta`, `rechaza`, `rechaza`.
## El k-ésimo símbolo desde el final
El lenguaje "el $k$-ésimo símbolo desde el final es $\mathtt{1}$" tiene un NFA de $k + 1$ estados. El programa
`kth_nfa` de la carpeta de la semana lo escribe para el $k$ que le pidan. Desde `code/week-02`, después de
correr `make` ahí:
```sh
build/kth_nfa 3 | lab/nfa_to_dfa/build/solution | head -1 | wc -w
```
La primera línea de su salida es `states:` seguida de los nombres, así que la cantidad de estados es ese número
menos 1. Con $k = 3$ debe salir 9: ocho estados.
Corran su programa con $k$ de 1 a 12 y llenen la tabla:
| $k$ | Estados del NFA | Estados de su DFA |
|---|---|---|
| 1 | 2 | |
| 2 | 3 | |
| 3 | 4 | 8 |
| … | | |
| 12 | 13 | |
Después respondan:
1. ¿Qué fórmula sigue la tercera columna? Compárenla con la tabla de los apuntes, en la sección *El costo: hasta
2ⁿ estados*.
2. Para $k = 12$ el NFA tiene 13 estados y $2^{13} = 8192$ subconjuntos. ¿Cuántos alcanzó su programa? ¿Qué
tienen en común todos los subconjuntos alcanzables?
3. ¿Hasta qué $k$ llega su programa en 2 segundos? ¿Qué se acaba primero, el tiempo o el límite de 10 000
estados?
## Para seguir
Opcional, sin casos en el juez.
- Escriban la construcción de la unión: un programa que lea dos NFA, uno después del otro, y escriba el NFA con
un estado inicial nuevo y dos transiciones $\varepsilon$. Pásenlo por su `solution` y comparen la cantidad de
estados con el producto de la semana 1.
- Su DFA puede tener estados de más: dos subconjuntos distintos a veces se comportan igual. Con `casos/12.in`,
¿cuántos estados produce su programa? En la semana 4 veremos cómo hallar el DFA más pequeño.// De NFA a DFA. Lee un NFA con transiciones ε en formato .nfa y escribe un DFA equivalente en
// formato .dfa, con solo los subconjuntos alcanzables.
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
// Con |Q| ≤ 60, un conjunto de estados cabe en un entero de 64 bits: el bit i dice si el
// estado número i está en el conjunto. Es una propuesta: también sirve un std::set<int>.
using StateSet = std::uint64_t;
// Los cinco componentes de N = (Q, Σ, δ, q0, F), con los nombres del formato.
struct Nfa {
std::vector<std::string> states; // Q: los nombres, en el orden de la entrada
std::vector<char> alphabet; // Σ
std::vector<std::vector<StateSet>> delta; // δ: delta[i][j] es el conjunto al que va states[i] con alphabet[j]
std::vector<StateSet> eps; // δ(q, ε): eps[i] es el conjunto al que va states[i] sin leer nada
int start = 0; // q0, como posición en states
StateSet accept = 0; // F
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Nfa n;
std::string line;
// Por hacer:
// 1. Leer la descripción línea por línea, hasta el final de la entrada.
// 2. Calcular la clausura ε con una búsqueda en el grafo de las transiciones ε.
// 3. Generar los subconjuntos alcanzables con una cola, a partir de E({q0}), y darle a
// cada uno un nombre nuevo y corto: s0, s1, s2…
// 4. Escribir el DFA en formato .dfa.
while (std::getline(std::cin, line)) {
}
// Este esqueleto no escribe nada, así que el verificador da WA en todos los casos.
return static_cast<int>(n.states.size());
}// Verificador de "De NFA a DFA": verificador ENTRADA ESPERADA SALIDA
// Hay muchos DFA correctos para un mismo NFA, así que no compara textos. Comprueba que SALIDA
// 1. es un DFA bien formado, en formato .dfa, con el mismo alfabeto que el NFA de ENTRADA;
// 2. respeta los límites del enunciado: a lo sumo 10 000 estados, nombres de hasta 20 caracteres;
// 3. reconoce el mismo lenguaje que el NFA.
// Para el punto 3 recorre a la vez el NFA (con su conjunto de estados activos) y el DFA
// entregado, como en la construcción del producto, y busca un par alcanzable en el que uno
// acepte y el otro no. Si lo encuentra, imprime la cadena más corta que lleva hasta él.
// ESPERADA (una respuesta correcta) no se usa. Termina con 0 si la salida es correcta.
#include <cstddef>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using Mask = std::uint64_t;
constexpr std::size_t MAX_STATES = 10000;
constexpr std::size_t MAX_NAME = 20;
struct Nfa {
std::vector<std::string> states;
std::vector<char> alphabet;
std::vector<std::vector<Mask>> delta; // delta[i][j]: destinos del estado i con alphabet[j]
std::vector<Mask> eps; // eps[i]: destinos del estado i con ε
int start = 0;
Mask accept = 0;
};
struct Dfa {
std::vector<std::string> states;
std::vector<std::vector<int>> delta; // delta[i][j]: destino del estado i con el símbolo j del NFA
int start = 0;
std::vector<bool> accept;
};
static std::vector<std::string> split_words(const std::string& text) {
std::istringstream in(text);
std::vector<std::string> words;
std::string word;
while (in >> word) {
words.push_back(word);
}
return words;
}
// Las líneas de una descripción que no son comentarios ni están vacías, ya separadas en palabras.
static std::vector<std::vector<std::string>> read_lines(std::istream& in) {
std::vector<std::vector<std::string>> lines;
std::string line;
while (std::getline(in, line)) {
if (!line.empty() && line[0] == '#') {
continue;
}
std::vector<std::string> words = split_words(line);
if (!words.empty()) {
lines.push_back(words);
}
}
return lines;
}
// La entrada la escribió el curso: se lee sin revisar.
static Nfa read_nfa(std::istream& in) {
Nfa n;
std::map<std::string, int> index;
std::map<char, int> column;
bool in_delta = false;
for (const std::vector<std::string>& words : read_lines(in)) {
if (in_delta) {
int from = index.at(words[0]);
for (std::size_t i = 2; i < words.size(); i++) {
Mask bit = Mask{1} << index.at(words[i]);
if (words[1] == "eps") {
n.eps[from] |= bit;
} else {
n.delta[from][column.at(words[1][0])] |= bit;
}
}
} else if (words[0] == "states:") {
n.states.assign(words.begin() + 1, words.end());
for (std::size_t i = 0; i < n.states.size(); i++) {
index[n.states[i]] = static_cast<int>(i);
}
} else if (words[0] == "alphabet:") {
for (std::size_t i = 1; i < words.size(); i++) {
column[words[i][0]] = static_cast<int>(n.alphabet.size());
n.alphabet.push_back(words[i][0]);
}
} else if (words[0] == "start:") {
n.start = index.at(words[1]);
} else if (words[0] == "accept:") {
for (std::size_t i = 1; i < words.size(); i++) {
n.accept |= Mask{1} << index.at(words[i]);
}
} else if (words[0] == "delta:") {
in_delta = true;
n.delta.assign(n.states.size(), std::vector<Mask>(n.alphabet.size(), 0));
n.eps.assign(n.states.size(), 0);
}
}
return n;
}
// Lee el DFA entregado, revisando todo. Si algo está mal, deja el motivo en error y devuelve false.
static bool read_dfa(std::istream& in, const Nfa& n, Dfa& d, std::string& error) {
std::vector<std::vector<std::string>> lines = read_lines(in);
const char* fields[] = {"states:", "alphabet:", "start:", "accept:", "delta:"};
if (lines.size() < 5) {
error = "la salida no tiene los cinco campos states:, alphabet:, start:, accept: y delta:";
return false;
}
for (int i = 0; i < 5; i++) {
if (lines[i][0] != fields[i]) {
error = std::string("se esperaba el campo ") + fields[i] + " y salió " + lines[i][0];
return false;
}
}
// states:
d.states.assign(lines[0].begin() + 1, lines[0].end());
if (d.states.empty()) {
error = "states: no tiene ningún estado";
return false;
}
if (d.states.size() > MAX_STATES) {
error = "el DFA tiene " + std::to_string(d.states.size()) + " estados, y el límite es " +
std::to_string(MAX_STATES) + ": construyan solo los subconjuntos alcanzables";
return false;
}
std::unordered_map<std::string, int> index;
for (std::size_t i = 0; i < d.states.size(); i++) {
const std::string& name = d.states[i];
if (name.size() > MAX_NAME) {
error = "el nombre " + name.substr(0, 30) + "… pasa de " + std::to_string(MAX_NAME) + " caracteres";
return false;
}
if (name.back() == ':') {
error = "el nombre " + name + " termina con dos puntos";
return false;
}
if (!index.insert({name, static_cast<int>(i)}).second) {
error = "el estado " + name + " está repetido en states:";
return false;
}
}
// alphabet: los mismos símbolos que el NFA, en cualquier orden.
std::map<char, int> column;
for (std::size_t j = 0; j < n.alphabet.size(); j++) {
column[n.alphabet[j]] = static_cast<int>(j);
}
std::set<char> sigma;
for (std::size_t i = 1; i < lines[1].size(); i++) {
const std::string& symbol = lines[1][i];
if (symbol.size() != 1 || column.count(symbol[0]) == 0) {
error = "el símbolo " + symbol + " no está en el alfabeto del NFA";
return false;
}
if (!sigma.insert(symbol[0]).second) {
error = "el símbolo " + symbol + " está repetido en alphabet:";
return false;
}
}
if (sigma.size() != n.alphabet.size()) {
error = "al alfabeto del DFA le faltan símbolos del NFA";
return false;
}
// start: y accept:
if (lines[2].size() != 2 || index.count(lines[2][1]) == 0) {
error = "start: lleva exactamente un estado, que debe estar en states:";
return false;
}
d.start = index[lines[2][1]];
d.accept.assign(d.states.size(), false);
for (std::size_t i = 1; i < lines[3].size(); i++) {
if (index.count(lines[3][i]) == 0) {
error = "el estado de aceptación " + lines[3][i] + " no está en states:";
return false;
}
d.accept[index[lines[3][i]]] = true;
}
// delta: exactamente una línea por cada par de estado y símbolo.
if (lines[4].size() != 1) {
error = "después de delta: las transiciones van una por línea";
return false;
}
d.delta.assign(d.states.size(), std::vector<int>(n.alphabet.size(), -1));
for (std::size_t k = 5; k < lines.size(); k++) {
const std::vector<std::string>& words = lines[k];
if (words.size() != 3) {
error = "una transición de un DFA se escribe: estado símbolo destino. Salió una línea con " +
std::to_string(words.size()) + " palabras que empieza con " + words[0].substr(0, 30);
return false;
}
if (index.count(words[0]) == 0 || index.count(words[2]) == 0) {
error = "la transición " + words[0] + " " + words[1] + " " + words[2] + " usa un estado que no está en states:";
return false;
}
if (words[1].size() != 1 || column.count(words[1][0]) == 0) {
error = "la transición " + words[0] + " " + words[1] + " " + words[2] + " usa un símbolo que no está en el alfabeto";
return false;
}
int& cell = d.delta[index[words[0]]][column[words[1][0]]];
if (cell != -1) {
error = "hay dos transiciones para δ(" + words[0] + ", " + words[1] + "): no es un DFA";
return false;
}
cell = index[words[2]];
}
for (std::size_t i = 0; i < d.states.size(); i++) {
for (std::size_t j = 0; j < n.alphabet.size(); j++) {
if (d.delta[i][j] == -1) {
error = "falta la transición δ(" + d.states[i] + ", " + n.alphabet[j] + "): en un DFA, δ es total";
return false;
}
}
}
return true;
}
static Mask eps_closure(const Nfa& n, Mask set) {
Mask closure = set;
for (bool changed = true; changed;) {
changed = false;
for (std::size_t i = 0; i < n.states.size(); i++) {
if (((closure >> i) & 1) && (n.eps[i] & ~closure) != 0) {
closure |= n.eps[i];
changed = true;
}
}
}
return closure;
}
// Un par alcanzable: el conjunto de estados activos del NFA y el estado del DFA entregado,
// con el par del que se llegó y el símbolo, para reconstruir la cadena.
struct Pair {
int subset;
int state;
int parent;
char symbol;
};
int main(int argc, char** argv) {
if (argc != 4) {
std::cout << "uso: verificador ENTRADA ESPERADA SALIDA\n";
return 2;
}
std::ifstream input(argv[1]);
std::ifstream output(argv[3]);
if (!input || !output) {
std::cout << "no se pudo abrir la entrada o la salida\n";
return 2;
}
Nfa n = read_nfa(input);
Dfa d;
std::string error;
if (!read_dfa(output, n, d, error)) {
std::cout << error << '\n';
return 1;
}
// closed[i][j] = E(δ(i, alphabet[j])).
std::size_t symbols = n.alphabet.size();
std::vector<std::vector<Mask>> closed(n.states.size(), std::vector<Mask>(symbols, 0));
for (std::size_t i = 0; i < n.states.size(); i++) {
for (std::size_t j = 0; j < symbols; j++) {
closed[i][j] = eps_closure(n, n.delta[i][j]);
}
}
// Recorrido en anchura de los pares (conjunto activo del NFA, estado del DFA).
std::vector<Mask> subsets = {eps_closure(n, Mask{1} << n.start)};
std::unordered_map<Mask, int> number = {{subsets[0], 0}};
std::vector<Pair> pairs = {{0, d.start, -1, ' '}};
std::unordered_set<std::uint64_t> seen = {static_cast<std::uint64_t>(d.start)};
for (std::size_t at = 0; at < pairs.size(); at++) {
Pair current = pairs[at];
Mask set = subsets[current.subset];
bool nfa_accepts = (set & n.accept) != 0;
bool dfa_accepts = d.accept[current.state];
if (nfa_accepts != dfa_accepts) {
std::string w;
for (int k = static_cast<int>(at); pairs[k].parent != -1; k = pairs[k].parent) {
w = pairs[k].symbol + w;
}
std::string shown = w.empty() ? "la cadena vacía" : "la cadena " + (w.size() > 60 ? w.substr(0, 60) + "…" : w);
std::cout << "no reconocen el mismo lenguaje: " << shown
<< (nfa_accepts ? " la acepta el NFA y la rechaza el DFA" : " la rechaza el NFA y la acepta el DFA")
<< '\n';
return 1;
}
for (std::size_t j = 0; j < symbols; j++) {
Mask target = 0;
for (std::size_t i = 0; i < n.states.size(); i++) {
if ((set >> i) & 1) {
target |= closed[i][j];
}
}
auto [it, is_new] = number.insert({target, static_cast<int>(subsets.size())});
if (is_new) {
subsets.push_back(target);
}
int next_state = d.delta[current.state][j];
std::uint64_t key = static_cast<std::uint64_t>(it->second) * (MAX_STATES + 1) +
static_cast<std::uint64_t>(next_state);
if (seen.insert(key).second) {
pairs.push_back({it->second, next_state, static_cast<int>(at), n.alphabet[j]});
}
}
}
return 0;
}Compilación
Cómo se compilan y ejecutan los ejemplos.
# Semana 2: autómatas finitos no deterministas, construcción de subconjuntos y propiedades de cierre.
# Se usa dentro del entorno del curso.
#
# make compila los programas de la clase en build/
# make test corre las pruebas de los ejemplos, con sanitizers
# make clean borra lo generado
#
# Las pruebas leen los autómatas de machines/ y de errors/, así que se corren desde esta carpeta.
# El laboratorio está en lab/nfa_to_dfa y tiene su propio Makefile: estas reglas no lo tocan.
CXX = g++
CXXFLAGS = -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined
BUILD = build
PROGRAMS = show_nfa run_nfa paths_nfa subset nfa_to_dfa run_dfa combine kth_nfa kth_table wrong_star swap_accept
TESTS = test_nfa test_subset test_closure
HEADERS = dfa.h nfa.h kth.h strings.h print.h test_helpers.h errors/wrong_constructions.h
.PHONY: all test clean
all: $(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%)
$(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(HEADERS) | $(BUILD)
$(CXX) $(CXXFLAGS) $< -o $@
$(BUILD):
mkdir -p $@
test: $(TESTS:%=$(BUILD)/%) $(PROGRAMS:%=$(BUILD)/%)
@for t in $(TESTS); do $(BUILD)/$$t || exit 1; done
@echo "Todas las pruebas pasaron."
clean:
rm -rf $(BUILD)