Semana 3 — Expresiones regulares
Objetivos
- Leer y escribir expresiones regulares con unión, concatenación y estrella, y decir qué lenguaje describen.
- Convertir una expresión regular en un NFA con la construcción de Thompson.
- Convertir un DFA en una expresión regular eliminando estados.
- Enunciar el teorema de Kleene y explicar por qué las expresiones de las herramientas reales no siempre son regulares.
Sesión A — Expresiones regulares · De expresión regular a NFA
Lectura: Apuntes, semana 3.
Apoyo: Sipser, sec. 1.3 (Regular Expressions). Erickson, Models of Computation, nota 2 (Regular languages).
Temas:
- Describir un lenguaje en vez de dar una máquina que lo reconoce.
grep, los validadores de formularios y los lexers de los compiladores. - Definición inductiva: , , un símbolo, unión, concatenación y estrella. Precedencia: estrella, concatenación, unión.
- Leer expresiones: , , . Escribirlas: cadenas con un número par de ceros, cadenas sin
11. - Identidades útiles y trampas: , , .
- De expresión regular a NFA: una construcción por cada caso de la definición, que son las de cierre de la semana 2. Construcción de Thompson.
- El NFA resultante tiene un número de estados lineal en el tamaño de la expresión.
- Abreviaturas de las herramientas (
+,?,[a-z],{n,m}) y por qué no agregan poder. - Error común: escribir una expresión que acepta lo pedido y también cadenas que no debía. Se prueba con cadenas de los dos lados.
Sesión B — De DFA a expresión regular: el teorema de Kleene
Lectura: Apuntes, semana 3.
Apoyo: Sipser, sec. 1.3, la segunda mitad: los autómatas generalizados (GNFA). Erickson, Models of Computation, nota 4.
Temas:
- La dirección difícil: de una máquina a una descripción.
- Autómatas con expresiones regulares en las flechas. Normalizar: un estado inicial nuevo y uno solo de aceptación.
- Eliminar un estado: la flecha de a pasa a ser . Ejemplo completo con un DFA de tres estados.
- El orden de eliminación cambia la expresión que sale, no el lenguaje. Las expresiones crecen rápido.
- Teorema de Kleene: DFA, NFA y expresiones regulares describen los mismos lenguajes. El triángulo de conversiones del curso.
- Cómo busca un motor real: simular el NFA con el conjunto de estados activos, en tiempo , frente al backtracking, que puede tardar un tiempo exponencial.
- Las referencias hacia atrás (
\1) no son regulares: se demuestra en la semana 4. - Error común: al eliminar un estado, olvidar el ciclo sobre sí mismo o alguna de las parejas .
Laboratorio — Un grep pequeño
- Leer una expresión regular con
|, concatenación,*y paréntesis, y una lista de líneas; responder por cada una si la expresión la acepta completa. - Construir el árbol de la expresión respetando la precedencia.
- Convertirlo en un NFA con la construcción de Thompson.
- Decidir cada línea simulando el NFA con el conjunto de estados activos, sin backtracking.
- Pasar el caso grande: la expresión (a|a)*b contra una cadena larga de
a, que hace exponencial a una búsqueda con backtracking.
Preguntas de repaso
- ¿Qué lenguajes describen y ? Den dos cadenas dentro y dos fuera de cada uno.
- Escriban una expresión regular para las cadenas binarias con un número de ceros múltiplo de 3.
- Conviertan en un NFA con la construcción de la clase.
- Eliminen los estados de un DFA de dos estados en los dos órdenes posibles y comprueben que las expresiones son equivalentes.
- ¿Por qué simular el NFA cuesta y el backtracking puede costar un tiempo exponencial con la misma expresión?
Código de la semana
Compilar y probar dentro del contenedor del curso con make y make test.
Ejemplos (23)Errores (1)Pruebas (4)Laboratorio (3)Compilación (1)
Ejemplos
Los programas que usan los apuntes y la clase.
// Busca con backtracking: backtrack EXPRESIÓN CADENA...
// Dice si la expresión describe cada cadena completa y cuántas llamadas hizo la búsqueda.
#include <iostream>
#include <stdexcept>
#include <string>
#include "backtrack.h"
#include "regex.h"
#include "words.h"
int main(int argc, char** argv) {
if (argc < 3) {
std::cerr << "uso: backtrack EXPRESIÓN CADENA...\n";
return 2;
}
try {
RegexPtr r = parse_regex(argv[1]);
for (int i = 2; i < argc; i++) {
std::string w = argv[i];
long long calls = 0;
bool found = backtrack_accepts(r, w, &calls);
std::cout << show(w) << ": " << (found ? "acepta" : "rechaza") << ", " << calls << " llamadas\n";
}
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Un buscador con backtracking: recorre el árbol de la expresión y prueba las alternativas
// una por una. Cuando una falla, vuelve atrás y prueba la siguiente.
// Es correcto, y con algunas expresiones tarda un tiempo exponencial en la longitud de la
// cadena: está aquí para compararlo con la simulación del NFA.
#ifndef BACKTRACK_H
#define BACKTRACK_H
#include <cstddef>
#include <functional>
#include <string>
#include "regex.h"
struct Backtracker {
std::string w;
long long calls = 0; // cuántas veces se llamó a match
// ¿Se puede leer con r un tramo de w que empieza en pos, de modo que lo que sigue (rest)
// acepte desde donde r terminó?
bool match(const RegexPtr& r, std::size_t pos, const std::function<bool(std::size_t)>& rest) {
calls++;
switch (r->kind) {
case Kind::Empty:
return false;
case Kind::Epsilon:
return rest(pos);
case Kind::Symbol:
return pos < w.size() && w[pos] == r->symbol && rest(pos + 1);
case Kind::Union:
// Primero la alternativa izquierda; si falla, la derecha.
return match(r->left, pos, rest) || match(r->right, pos, rest);
case Kind::Concat:
return match(r->left, pos, [&](std::size_t middle) { return match(r->right, middle, rest); });
case Kind::Star:
// Primero intenta una vuelta más y, si falla, sale de la estrella. Una vuelta
// que no avanza no se cuenta: sin esa condición, (a*)* no terminaría.
return match(r->left, pos,
[&](std::size_t middle) { return middle > pos && match(r, middle, rest); }) ||
rest(pos);
}
return false;
}
};
// ¿Describe r la cadena w completa? Devuelve además cuántas llamadas hizo.
inline bool backtrack_accepts(const RegexPtr& r, const std::string& w, long long* calls = nullptr) {
Backtracker search{w};
bool found = search.match(r, 0, [&](std::size_t end) { return end == w.size(); });
if (calls != nullptr) {
*calls = search.calls;
}
return found;
}
#endif// Autómata finito determinista. El struct tiene los cinco componentes de la definición
// M = (Q, Σ, δ, q0, F), con los nombres del formato .dfa de code/formats.md.
// Es una copia de code/week-01/dfa.h, sin cambios, para que esta carpeta no dependa de otra.
// Además: leer y escribir ese formato, la función de transición extendida, la construcción
// del producto y el complemento.
#ifndef DFA_H
#define DFA_H
#include <cstddef>
#include <fstream>
#include <istream>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
struct Dfa {
std::vector<std::string> states; // Q, en el orden del archivo
std::vector<char> alphabet; // Σ
std::map<std::pair<std::string, char>, std::string> delta; // δ : Q × Σ → Q
std::string start; // q0
std::set<std::string> accept; // F ⊆ Q
};
// ------------------------------------------------------------
// Comprobar que la quíntupla es un DFA
// ------------------------------------------------------------
// Lanza std::runtime_error si m no cumple la definición. Lo más importante: δ es total.
inline void check_dfa(const Dfa& m) {
std::set<std::string> q(m.states.begin(), m.states.end());
std::set<char> sigma(m.alphabet.begin(), m.alphabet.end());
if (m.states.empty()) {
throw std::runtime_error("Q no puede ser vacío");
}
if (q.size() != m.states.size()) {
throw std::runtime_error("hay un estado repetido en states");
}
if (m.alphabet.empty()) {
throw std::runtime_error("el alfabeto no puede ser vacío");
}
if (sigma.size() != m.alphabet.size()) {
throw std::runtime_error("hay un símbolo repetido en alphabet");
}
if (q.count(m.start) == 0) {
throw std::runtime_error("el estado inicial " + m.start + " no está en states");
}
for (const std::string& f : m.accept) {
if (q.count(f) == 0) {
throw std::runtime_error("el estado de aceptación " + f + " no está en states");
}
}
for (const auto& [key, target] : m.delta) {
if (q.count(key.first) == 0) {
throw std::runtime_error("transición desde " + key.first + ", que no está en states");
}
if (sigma.count(key.second) == 0) {
throw std::runtime_error(std::string("transición con ") + key.second + ", que no está en alphabet");
}
if (q.count(target) == 0) {
throw std::runtime_error("transición hacia " + target + ", que no está en states");
}
}
for (const std::string& state : m.states) {
for (char a : m.alphabet) {
if (m.delta.count({state, a}) == 0) {
throw std::runtime_error("falta la transición δ(" + state + ", " + a + "): en un DFA, δ es total");
}
}
}
}
// ------------------------------------------------------------
// Leer y escribir el formato .dfa
// ------------------------------------------------------------
inline std::vector<std::string> split_words(const std::string& text) {
std::istringstream in(text);
std::vector<std::string> words;
std::string word;
while (in >> word) {
words.push_back(word);
}
return words;
}
// Lee una descripción completa, hasta el final de la entrada.
inline Dfa read_dfa(std::istream& in) {
int number = 0;
auto fail = [&number](const std::string& message) {
throw std::runtime_error("línea " + std::to_string(number) + ": " + message);
};
// Siguiente línea que no es comentario ni está vacía. Devuelve false al final.
auto next_line = [&in, &number](std::vector<std::string>& words) {
std::string line;
while (std::getline(in, line)) {
number++;
if (!line.empty() && line[0] == '#') {
continue;
}
words = split_words(line);
if (!words.empty()) {
return true;
}
}
return false;
};
// Un campo: "nombre: valor valor ...". Devuelve los valores.
auto field = [&next_line, &fail](const std::string& name) {
std::vector<std::string> words;
if (!next_line(words) || words[0] != name + ":") {
fail("se esperaba el campo " + name + ":");
}
words.erase(words.begin());
return words;
};
Dfa m;
m.states = field("states");
for (const std::string& symbol : field("alphabet")) {
if (symbol.size() != 1 || symbol[0] == '#') {
fail("un símbolo es un solo carácter distinto de #: " + symbol);
}
m.alphabet.push_back(symbol[0]);
}
std::vector<std::string> start = field("start");
if (start.size() != 1) {
fail("start: lleva exactamente un estado");
}
m.start = start[0];
for (const std::string& state : field("accept")) {
m.accept.insert(state);
}
if (!field("delta").empty()) {
fail("después de delta: las transiciones van una por línea");
}
std::vector<std::string> words;
while (next_line(words)) {
if (words.size() != 3 || words[1].size() != 1) {
fail("una transición se escribe: estado símbolo destino");
}
std::pair<std::string, char> key = {words[0], words[1][0]};
if (m.delta.count(key) > 0) {
fail("transición repetida para δ(" + words[0] + ", " + words[1] + "): en un DFA hay una sola");
}
m.delta[key] = words[2];
}
check_dfa(m);
return m;
}
inline Dfa load_dfa(const std::string& path) {
std::ifstream file(path);
if (!file) {
throw std::runtime_error("no se pudo abrir " + path);
}
try {
return read_dfa(file);
} catch (const std::runtime_error& error) {
throw std::runtime_error(path + ": " + error.what());
}
}
// Escribe m en el formato .dfa: lo que escribe se puede volver a leer con read_dfa.
inline void write_dfa(std::ostream& out, const Dfa& m) {
out << "states:";
for (const std::string& state : m.states) {
out << ' ' << state;
}
out << "\nalphabet:";
for (char a : m.alphabet) {
out << ' ' << a;
}
out << "\nstart: " << m.start << "\naccept:";
for (const std::string& state : m.states) {
if (m.accept.count(state) > 0) {
out << ' ' << state;
}
}
out << "\ndelta:\n";
for (const std::string& state : m.states) {
for (char a : m.alphabet) {
out << state << ' ' << a << ' ' << m.delta.at({state, a}) << '\n';
}
}
}
// ------------------------------------------------------------
// Ejecutar
// ------------------------------------------------------------
// Un paso: δ(q, a).
inline const std::string& step(const Dfa& m, const std::string& q, char a) {
auto it = m.delta.find({q, a});
if (it == m.delta.end()) {
throw std::runtime_error("δ(" + q + ", " + a + ") no está definida");
}
return it->second;
}
// La función de transición extendida: δ*(q, ε) = q y δ*(q, wa) = δ(δ*(q, w), a).
// El ciclo aplica la segunda línea de la definición una vez por símbolo, de izquierda a derecha.
inline std::string delta_star(const Dfa& m, std::string q, const std::string& w) {
for (char a : w) {
q = step(m, q, a);
}
return q;
}
// M acepta w si δ*(q0, w) ∈ F.
inline bool accepts(const Dfa& m, const std::string& w) {
return m.accept.count(delta_star(m, m.start, w)) > 0;
}
// La ejecución de M con w: los estados r0, r1, …, rn, con r0 = q0 y r(i+1) = δ(r(i), w(i+1)).
inline std::vector<std::string> run(const Dfa& m, const std::string& w) {
std::vector<std::string> sequence = {m.start};
for (char a : w) {
sequence.push_back(step(m, sequence.back(), a));
}
return sequence;
}
// Los estados a los que se llega desde q0 con alguna cadena.
inline std::set<std::string> reachable(const Dfa& m) {
std::set<std::string> seen = {m.start};
std::queue<std::string> pending;
pending.push(m.start);
while (!pending.empty()) {
std::string q = pending.front();
pending.pop();
for (char a : m.alphabet) {
const std::string& next = step(m, q, a);
if (seen.insert(next).second) {
pending.push(next);
}
}
}
return seen;
}
// ------------------------------------------------------------
// Construcciones
// ------------------------------------------------------------
enum class Combine { Intersection, Union };
// El nombre del estado (p, q) del producto. Los nombres del formato no llevan espacios.
inline std::string pair_name(const std::string& p, const std::string& q) {
return "(" + p + "," + q + ")";
}
// Construcción del producto: Q = Q1 × Q2, δ((p, q), a) = (δ1(p, a), δ2(q, a)), q0 = (q1, q2).
// Para la intersección, F = F1 × F2. Para la unión, F = (F1 × Q2) ∪ (Q1 × F2).
inline Dfa product(const Dfa& m1, const Dfa& m2, Combine mode) {
std::set<char> sigma1(m1.alphabet.begin(), m1.alphabet.end());
std::set<char> sigma2(m2.alphabet.begin(), m2.alphabet.end());
if (sigma1 != sigma2) {
throw std::runtime_error("el producto necesita dos DFA con el mismo alfabeto");
}
Dfa m;
m.alphabet = m1.alphabet;
m.start = pair_name(m1.start, m2.start);
for (const std::string& p : m1.states) {
for (const std::string& q : m2.states) {
std::string name = pair_name(p, q);
m.states.push_back(name);
bool in1 = m1.accept.count(p) > 0;
bool in2 = m2.accept.count(q) > 0;
bool accepting = (mode == Combine::Intersection) ? (in1 && in2) : (in1 || in2);
if (accepting) {
m.accept.insert(name);
}
for (char a : m.alphabet) {
m.delta[{name, a}] = pair_name(step(m1, p, a), step(m2, q, a));
}
}
}
check_dfa(m); // también detecta dos pares con el mismo nombre, si los nombres traían comas
return m;
}
// Complemento: la misma máquina con F cambiado por Q − F.
inline Dfa complement(const Dfa& m) {
Dfa result = m;
result.accept.clear();
for (const std::string& state : m.states) {
if (m.accept.count(state) == 0) {
result.accept.insert(state);
}
}
return result;
}
// La misma máquina sin los estados inalcanzables. Reconoce el mismo lenguaje.
inline Dfa remove_unreachable(const Dfa& m) {
std::set<std::string> keep = reachable(m);
Dfa result;
result.alphabet = m.alphabet;
result.start = m.start;
for (const std::string& state : m.states) {
if (keep.count(state) == 0) {
continue;
}
result.states.push_back(state);
if (m.accept.count(state) > 0) {
result.accept.insert(state);
}
for (char a : m.alphabet) {
result.delta[{state, a}] = step(m, state, a);
}
}
return result;
}
#endif// De DFA a expresión regular eliminando estados: eliminate ARCHIVO.dfa [ESTADO...]
// Los estados se eliminan en el orden en que se nombran; sin nombres, en el orden del archivo.
// Muestra las flechas del autómata generalizado al empezar y después de cada eliminación.
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include "dfa.h"
#include "gnfa.h"
#include "regex.h"
static void show_gnfa(const Gnfa& g) {
std::cout << " estados:";
for (const std::string& q : g.states) {
std::cout << ' ' << q;
}
std::cout << '\n';
for (const std::string& i : g.states) {
for (const std::string& j : g.states) {
auto it = g.arrow.find({i, j});
if (it != g.arrow.end()) {
std::cout << " " << i << " -> " << j << " : " << to_string(it->second) << '\n';
}
}
}
}
int main(int argc, char** argv) {
if (argc < 2) {
std::cerr << "uso: eliminate ARCHIVO.dfa [ESTADO...]\n";
return 2;
}
try {
Dfa m = load_dfa(argv[1]);
std::vector<std::string> order(argv + 2, argv + argc);
if (order.empty()) {
order = m.states;
}
RegexPtr result = to_regex(m, order); // también revisa que el orden esté completo
Gnfa g = to_gnfa(m);
std::cout << "Autómata generalizado de " << argv[1] << '\n';
show_gnfa(g);
for (const std::string& k : order) {
g = eliminate(g, k);
std::cout << "\nSe elimina " << k << '\n';
show_gnfa(g);
}
std::cout << "\nExpresión: " << to_string(result) << '\n';
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Autómata finito no determinista generalizado (GNFA): las flechas llevan expresiones
// regulares en lugar de símbolos. Sirve para convertir un DFA en una expresión regular
// eliminando sus estados de uno en uno.
#ifndef GNFA_H
#define GNFA_H
#include <map>
#include <set>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
#include "dfa.h"
#include "regex.h"
struct Gnfa {
std::vector<std::string> states; // Q, con start y accept
std::string start; // no le entra ninguna flecha
std::string accept; // no le sale ninguna flecha
std::map<std::pair<std::string, std::string>, RegexPtr> arrow; // la expresión de i a j
};
// La expresión de la flecha de i a j. Una flecha que no está dibujada lleva ∅.
inline RegexPtr label(const Gnfa& g, const std::string& i, const std::string& j) {
auto it = g.arrow.find({i, j});
return it == g.arrow.end() ? empty_set() : it->second;
}
// Un nombre que no esté usado: base, o base con apóstrofos.
inline std::string fresh_name(const std::set<std::string>& used, std::string base) {
while (used.count(base) > 0) {
base += "'";
}
return base;
}
// Normalizar: un estado inicial nuevo con una flecha ε al inicial del DFA, y un único estado
// de aceptación nuevo al que llega una flecha ε desde cada estado de aceptación del DFA.
// Las flechas del DFA entre dos mismos estados se juntan en una sola, con la unión de sus
// símbolos.
inline Gnfa to_gnfa(const Dfa& m) {
std::set<std::string> used(m.states.begin(), m.states.end());
Gnfa g;
g.start = fresh_name(used, "ini");
used.insert(g.start);
g.accept = fresh_name(used, "fin");
g.states.push_back(g.start);
g.states.insert(g.states.end(), m.states.begin(), m.states.end());
g.states.push_back(g.accept);
g.arrow[{g.start, m.start}] = epsilon();
for (const std::string& q : m.states) {
if (m.accept.count(q) > 0) {
g.arrow[{q, g.accept}] = epsilon();
}
for (char a : m.alphabet) {
const std::string& target = step(m, q, a);
g.arrow[{q, target}] = simple_union(label(g, q, target), symbol(a));
}
}
return g;
}
// Eliminar el estado k. Para cada pareja (i, j) de los estados que quedan, la flecha nueva es
// R(i, j) ∪ R(i, k) R(k, k)* R(k, j)
// Las operaciones aplican las identidades de ∅ y de ε, para no arrastrar términos vacíos.
inline Gnfa eliminate(const Gnfa& g, const std::string& k) {
if (k == g.start || k == g.accept) {
throw std::runtime_error("no se elimina el estado inicial ni el de aceptación");
}
Gnfa result;
result.start = g.start;
result.accept = g.accept;
for (const std::string& q : g.states) {
if (q != k) {
result.states.push_back(q);
}
}
if (result.states.size() == g.states.size()) {
throw std::runtime_error("el estado " + k + " no está en el autómata");
}
RegexPtr loop = simple_star(label(g, k, k));
for (const std::string& i : result.states) {
if (i == g.accept) {
continue; // del estado de aceptación no sale nada
}
for (const std::string& j : result.states) {
if (j == g.start) {
continue; // al estado inicial no entra nada
}
RegexPtr through = simple_concat(simple_concat(label(g, i, k), loop), label(g, k, j));
RegexPtr merged = simple_union(label(g, i, j), through);
if (merged->kind != Kind::Empty) {
result.arrow[{i, j}] = merged;
}
}
}
return result;
}
// De DFA a expresión regular, eliminando los estados en el orden dado.
// El orden debe nombrar cada estado del DFA exactamente una vez.
inline RegexPtr to_regex(const Dfa& m, const std::vector<std::string>& order) {
std::set<std::string> named(order.begin(), order.end());
std::set<std::string> all(m.states.begin(), m.states.end());
if (order.size() != m.states.size() || named != all) {
throw std::runtime_error("el orden debe nombrar cada estado una vez");
}
Gnfa g = to_gnfa(m);
for (const std::string& k : order) {
g = eliminate(g, k);
}
return label(g, g.start, g.accept);
}
#endif// Cuánto crece la expresión al eliminar estados: growth [K_MÁXIMO]
// Para cada k construye el DFA de k estados de los múltiplos de k en binario (el de la
// semana 1 con k = 3), elimina sus estados en el orden r0, r1, … y en el orden inverso, y
// cuenta los nodos de la expresión que sale.
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>
#include "dfa.h"
#include "gnfa.h"
#include "regex.h"
// El estado rI dice que el valor de lo leído deja resto I al dividir entre k.
// Leer el bit b cambia el valor v por 2v + b.
static Dfa multiples_of(int k) {
Dfa m;
m.alphabet = {'0', '1'};
for (int i = 0; i < k; i++) {
m.states.push_back("r" + std::to_string(i));
}
m.start = "r0";
m.accept = {"r0"};
for (int i = 0; i < k; i++) {
m.delta[{m.states[i], '0'}] = m.states[(2 * i) % k];
m.delta[{m.states[i], '1'}] = m.states[(2 * i + 1) % k];
}
check_dfa(m);
return m;
}
int main(int argc, char** argv) {
int max_k = (argc == 2) ? std::stoi(argv[1]) : 8;
std::cout << " k estados nodos (r0 primero) nodos (r0 al final)\n";
for (int k = 2; k <= max_k; k++) {
Dfa m = multiples_of(k);
std::vector<std::string> forward = m.states;
std::vector<std::string> backward(m.states.rbegin(), m.states.rend());
std::size_t a = size(to_regex(m, forward));
std::size_t b = size(to_regex(m, backward));
std::cout.width(2);
std::cout << k;
std::cout.width(10);
std::cout << k;
std::cout.width(21);
std::cout << a;
std::cout.width(22);
std::cout << b << '\n';
}
}// Backtracking frente a simulación del NFA, con el caso malo: (a|a)*b contra a^n.
// La cadena no tiene ninguna b, así que la respuesta siempre es "rechaza".
// Cuenta las llamadas del backtracking y mide el tiempo de las dos búsquedas.
// Se compila con -O2 y sin sanitizers: make bench.
#include <chrono>
#include <cstddef>
#include <cstdio>
#include <string>
#include <vector>
#include "backtrack.h"
#include "nfa.h"
#include "regex.h"
#include "thompson.h"
static double seconds_since(std::chrono::steady_clock::time_point start) {
return std::chrono::duration<double>(std::chrono::steady_clock::now() - start).count();
}
int main() {
RegexPtr r = parse_regex("(a|a)*b");
Nfa n = thompson(r);
std::printf("expresión: (a|a)*b cadena: a^n NFA de Thompson: %zu estados\n\n", n.states.size());
std::printf(" n backtracking: llamadas backtracking: tiempo NFA: tiempo\n");
std::vector<std::size_t> lengths = {5, 10, 15, 20, 25};
for (std::size_t length : lengths) {
std::string w(length, 'a');
long long calls = 0;
auto t0 = std::chrono::steady_clock::now();
bool by_backtracking = backtrack_accepts(r, w, &calls);
double backtracking_time = seconds_since(t0);
auto t1 = std::chrono::steady_clock::now();
bool by_nfa = accepts(n, w);
double nfa_time = seconds_since(t1);
if (by_backtracking || by_nfa) {
std::printf("error: alguna de las dos búsquedas aceptó\n");
return 1;
}
std::printf("%7zu %22lld %18.4f s %9.4f s\n", length, calls, backtracking_time, nfa_time);
}
// Solo el NFA: con estas longitudes el backtracking no termina.
for (std::size_t length : {1000, 100000}) {
std::string w(length, 'a');
auto t1 = std::chrono::steady_clock::now();
bool by_nfa = accepts(n, w);
double nfa_time = seconds_since(t1);
if (by_nfa) {
std::printf("error: el NFA aceptó\n");
return 1;
}
std::printf("%7zu %22s %20s %9.4f s\n", length, "-", "-", nfa_time);
}
}// Autómata finito no determinista, con transiciones ε. El struct tiene los cinco componentes
// de la definición N = (Q, Σ, δ, q0, F), con los nombres del formato .nfa de code/formats.md.
// Además: leer y escribir ese formato, la clausura ε y la simulación con el conjunto de
// estados activos.
#ifndef NFA_H
#define NFA_H
#include <cstddef>
#include <fstream>
#include <istream>
#include <map>
#include <ostream>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
// En δ, una transición ε se guarda con este carácter en el lugar del símbolo.
const char EPS = '\0';
using StateSet = std::set<std::string>;
struct Nfa {
std::vector<std::string> states; // Q, en el orden del archivo
std::vector<char> alphabet; // Σ
std::map<std::pair<std::string, char>, StateSet> delta; // δ : Q × (Σ ∪ {ε}) → P(Q)
std::string start; // q0
StateSet accept; // F ⊆ Q
};
// ------------------------------------------------------------
// Comprobar que la quíntupla es un NFA
// ------------------------------------------------------------
inline void check_nfa(const Nfa& n) {
StateSet q(n.states.begin(), n.states.end());
std::set<char> sigma(n.alphabet.begin(), n.alphabet.end());
if (n.states.empty()) {
throw std::runtime_error("Q no puede ser vacío");
}
if (q.size() != n.states.size()) {
throw std::runtime_error("hay un estado repetido en states");
}
if (n.alphabet.empty()) {
throw std::runtime_error("el alfabeto no puede ser vacío");
}
if (sigma.size() != n.alphabet.size()) {
throw std::runtime_error("hay un símbolo repetido en alphabet");
}
if (q.count(n.start) == 0) {
throw std::runtime_error("el estado inicial " + n.start + " no está en states");
}
for (const std::string& f : n.accept) {
if (q.count(f) == 0) {
throw std::runtime_error("el estado de aceptación " + f + " no está en states");
}
}
for (const auto& [key, targets] : n.delta) {
if (q.count(key.first) == 0) {
throw std::runtime_error("transición desde " + key.first + ", que no está en states");
}
if (key.second != EPS && sigma.count(key.second) == 0) {
throw std::runtime_error(std::string("transición con ") + key.second + ", que no está en alphabet");
}
for (const std::string& target : targets) {
if (q.count(target) == 0) {
throw std::runtime_error("transición hacia " + target + ", que no está en states");
}
}
}
}
// ------------------------------------------------------------
// Leer y escribir el formato .nfa
// ------------------------------------------------------------
inline std::vector<std::string> split_nfa_words(const std::string& text) {
std::istringstream in(text);
std::vector<std::string> words;
std::string word;
while (in >> word) {
words.push_back(word);
}
return words;
}
// Lee una descripción completa, hasta el final de la entrada.
inline Nfa read_nfa(std::istream& in) {
int number = 0;
auto fail = [&number](const std::string& message) {
throw std::runtime_error("línea " + std::to_string(number) + ": " + message);
};
// Siguiente línea que no es comentario ni está vacía. Devuelve false al final.
auto next_line = [&in, &number](std::vector<std::string>& words) {
std::string line;
while (std::getline(in, line)) {
number++;
if (!line.empty() && line[0] == '#') {
continue;
}
words = split_nfa_words(line);
if (!words.empty()) {
return true;
}
}
return false;
};
auto field = [&next_line, &fail](const std::string& name) {
std::vector<std::string> words;
if (!next_line(words) || words[0] != name + ":") {
fail("se esperaba el campo " + name + ":");
}
words.erase(words.begin());
return words;
};
Nfa n;
n.states = field("states");
for (const std::string& symbol : field("alphabet")) {
if (symbol.size() != 1 || symbol[0] == '#') {
fail("un símbolo es un solo carácter distinto de #: " + symbol);
}
n.alphabet.push_back(symbol[0]);
}
std::vector<std::string> start = field("start");
if (start.size() != 1) {
fail("start: lleva exactamente un estado");
}
n.start = start[0];
for (const std::string& state : field("accept")) {
n.accept.insert(state);
}
if (!field("delta").empty()) {
fail("después de delta: las transiciones van una por línea");
}
std::vector<std::string> words;
while (next_line(words)) {
// estado símbolo destino… con eps en el lugar del símbolo para una transición ε
if (words.size() < 3 || (words[1] != "eps" && words[1].size() != 1)) {
fail("una transición se escribe: estado símbolo destino…");
}
char a = (words[1] == "eps") ? EPS : words[1][0];
for (std::size_t i = 2; i < words.size(); i++) {
n.delta[{words[0], a}].insert(words[i]);
}
}
check_nfa(n);
return n;
}
inline Nfa load_nfa(const std::string& path) {
std::ifstream file(path);
if (!file) {
throw std::runtime_error("no se pudo abrir " + path);
}
try {
return read_nfa(file);
} catch (const std::runtime_error& error) {
throw std::runtime_error(path + ": " + error.what());
}
}
// Escribe n en el formato .nfa. Un par de estado y símbolo sin transiciones no lleva línea.
inline void write_nfa(std::ostream& out, const Nfa& n) {
out << "states:";
for (const std::string& state : n.states) {
out << ' ' << state;
}
out << "\nalphabet:";
for (char a : n.alphabet) {
out << ' ' << a;
}
out << "\nstart: " << n.start << "\naccept:";
for (const std::string& state : n.states) {
if (n.accept.count(state) > 0) {
out << ' ' << state;
}
}
out << "\ndelta:\n";
std::vector<char> labels = n.alphabet;
labels.push_back(EPS);
for (const std::string& state : n.states) {
for (char a : labels) {
auto it = n.delta.find({state, a});
if (it == n.delta.end() || it->second.empty()) {
continue;
}
out << state << ' ' << (a == EPS ? std::string("eps") : std::string(1, a));
// Los destinos, en el orden de states.
for (const std::string& target : n.states) {
if (it->second.count(target) > 0) {
out << ' ' << target;
}
}
out << '\n';
}
}
}
// ------------------------------------------------------------
// Ejecutar: el conjunto de estados activos
// ------------------------------------------------------------
// Clausura ε: los estados de s y todos los que se alcanzan desde ellos con transiciones ε.
// Es una búsqueda en el grafo de las transiciones ε.
inline StateSet eps_closure(const Nfa& n, const StateSet& s) {
StateSet closure = s;
std::vector<std::string> pending(s.begin(), s.end());
while (!pending.empty()) {
std::string q = pending.back();
pending.pop_back();
auto it = n.delta.find({q, EPS});
if (it == n.delta.end()) {
continue;
}
for (const std::string& target : it->second) {
if (closure.insert(target).second) {
pending.push_back(target);
}
}
}
return closure;
}
// Un paso: desde los estados de s, leer el símbolo a y después seguir las transiciones ε.
inline StateSet step(const Nfa& n, const StateSet& s, char a) {
StateSet next;
for (const std::string& q : s) {
auto it = n.delta.find({q, a});
if (it != n.delta.end()) {
next.insert(it->second.begin(), it->second.end());
}
}
return eps_closure(n, next);
}
// Los conjuntos de estados activos S0, S1, …, Sn: S0 es la clausura ε de {q0}, y S(i) es el
// conjunto de estados en los que el NFA puede estar después de leer los primeros i símbolos.
inline std::vector<StateSet> run(const Nfa& n, const std::string& w) {
std::vector<StateSet> sets = {eps_closure(n, {n.start})};
for (char a : w) {
sets.push_back(step(n, sets.back(), a));
}
return sets;
}
// N acepta w si, después de leerla, algún estado activo es de aceptación.
inline bool accepts(const Nfa& n, const std::string& w) {
StateSet active = eps_closure(n, {n.start});
for (char a : w) {
active = step(n, active, a);
}
for (const std::string& q : active) {
if (n.accept.count(q) > 0) {
return true;
}
}
return false;
}
// Para imprimir un conjunto de estados en el orden de states: {q0, q3}.
inline std::string show_set(const Nfa& n, const StateSet& s) {
std::string text = "{";
for (const std::string& state : n.states) {
if (s.count(state) > 0) {
text += (text.size() > 1 ? ", " : "") + state;
}
}
return text + "}";
}
#endif// Elimina los estados de un DFA en todos los órdenes posibles: orders ARCHIVO.dfa
// Imprime la expresión que sale con cada orden y cuántos nodos tiene su árbol.
#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include "dfa.h"
#include "gnfa.h"
#include "regex.h"
int main(int argc, char** argv) {
if (argc != 2) {
std::cerr << "uso: orders ARCHIVO.dfa\n";
return 2;
}
try {
Dfa m = load_dfa(argv[1]);
if (m.states.size() > 6) {
throw std::runtime_error("con más de 6 estados son demasiados órdenes");
}
std::vector<std::string> order = m.states;
std::sort(order.begin(), order.end());
do {
RegexPtr r = to_regex(m, order);
for (const std::string& k : order) {
std::cout << k << ' ';
}
std::cout << " (" << size(r) << " nodos)\n " << to_string(r) << '\n';
} while (std::next_permutation(order.begin(), order.end()));
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Compara dos expresiones con todas las cadenas cortas: regex_diff EXPRESIÓN1 EXPRESIÓN2 [LONGITUD]
// Lista las cadenas que una describe y la otra no. La longitud máxima por defecto es 8.
// Que no haya diferencias hasta esa longitud no demuestra que sean equivalentes.
#include <cstddef>
#include <iostream>
#include <set>
#include <stdexcept>
#include <string>
#include <vector>
#include "nfa.h"
#include "regex.h"
#include "thompson.h"
#include "words.h"
int main(int argc, char** argv) {
if (argc < 3 || argc > 4) {
std::cerr << "uso: regex_diff EXPRESIÓN1 EXPRESIÓN2 [LONGITUD]\n";
return 2;
}
try {
RegexPtr r1 = parse_regex(argv[1]);
RegexPtr r2 = parse_regex(argv[2]);
std::size_t max_len = (argc == 4) ? std::stoul(argv[3]) : 8;
std::set<char> both;
collect_symbols(r1, both);
collect_symbols(r2, both);
std::vector<char> alphabet(both.begin(), both.end());
if (alphabet.empty()) {
throw std::runtime_error("las expresiones no tienen símbolos");
}
Nfa n1 = thompson(r1, alphabet);
Nfa n2 = thompson(r2, alphabet);
std::vector<std::string> only1;
std::vector<std::string> only2;
std::vector<std::string> words = all_strings(alphabet, max_len);
for (const std::string& w : words) {
bool in1 = accepts(n1, w);
bool in2 = accepts(n2, w);
if (in1 && !in2) {
only1.push_back(w);
}
if (in2 && !in1) {
only2.push_back(w);
}
}
auto report = [](const std::string& name, const std::vector<std::string>& list) {
std::cout << "solo en " << name << ": " << list.size();
if (!list.empty()) {
std::cout << ". Las más cortas:";
for (std::size_t i = 0; i < list.size() && i < 6; i++) {
std::cout << ' ' << show(list[i]);
}
}
std::cout << '\n';
};
std::cout << "R1 = " << to_string(r1) << "\nR2 = " << to_string(r2) << '\n'
<< words.size() << " cadenas de longitud a lo sumo " << max_len << '\n';
report("R1", only1);
report("R2", only2);
if (only1.empty() && only2.empty()) {
std::cout << "sin diferencias hasta esa longitud\n";
}
} catch (const std::exception& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Lista las cadenas más cortas del lenguaje de una expresión: regex_lang EXPRESIÓN [LONGITUD] [ALFABETO]
// Sin alfabeto, usa los símbolos que aparecen en la expresión. La longitud máxima por defecto es 4.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include "nfa.h"
#include "regex.h"
#include "thompson.h"
#include "words.h"
int main(int argc, char** argv) {
if (argc < 2 || argc > 4) {
std::cerr << "uso: regex_lang EXPRESIÓN [LONGITUD] [ALFABETO]\n";
return 2;
}
try {
RegexPtr r = parse_regex(argv[1]);
std::size_t max_len = (argc >= 3) ? std::stoul(argv[2]) : 4;
std::vector<char> alphabet = symbols_of(r);
if (argc == 4) {
std::string given = argv[3];
alphabet.assign(given.begin(), given.end());
}
if (alphabet.empty()) {
throw std::runtime_error("la expresión no tiene símbolos: indiquen el alfabeto");
}
Nfa n = thompson(r, alphabet);
std::vector<std::string> words = all_strings(alphabet, max_len);
std::size_t inside = 0;
std::cout << "L(" << to_string(r) << "), hasta longitud " << max_len << ":\n ";
for (const std::string& w : words) {
if (accepts(n, w)) {
std::cout << ' ' << show(w);
inside++;
}
}
std::cout << (inside == 0 ? " (ninguna)" : "") << '\n'
<< inside << " de " << words.size() << " cadenas\n";
} catch (const std::exception& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Muestra cómo se lee una expresión regular: regex_tree EXPRESIÓN...
// Imprime la expresión con los paréntesis justos, con todos los paréntesis, y su árbol.
#include <iostream>
#include <stdexcept>
#include "regex.h"
int main(int argc, char** argv) {
if (argc < 2) {
std::cerr << "uso: regex_tree EXPRESIÓN...\n";
return 2;
}
for (int i = 1; i < argc; i++) {
try {
RegexPtr r = parse_regex(argv[i]);
std::cout << "expresión: " << to_string(r) << '\n'
<< "con sus paréntesis: " << to_string_full(r) << '\n'
<< "nodos del árbol: " << size(r) << '\n'
<< tree(r);
} catch (const std::runtime_error& error) {
std::cout << argv[i] << "\n error: " << error.what() << '\n';
}
if (i + 1 < argc) {
std::cout << '\n';
}
}
}// Expresiones regulares. Una expresión es un árbol con un nodo por cada caso de la definición
// inductiva: ∅, ε, un símbolo, unión, concatenación y estrella.
// Además: el parser que lee una expresión escrita en una línea, y la escritura con los
// paréntesis justos.
//
// Cómo se escribe una expresión para estos programas:
// - un símbolo es una letra o un dígito: a, b, 0, 1
// - la unión es |, la concatenación no se escribe y la estrella es *
// - ε se escribe % (o la propia letra ε) y ∅ se escribe @ (o el propio signo ∅)
// - precedencia: primero la estrella, después la concatenación, al final la unión
// - los paréntesis agrupan y los espacios se ignoran
#ifndef REGEX_H
#define REGEX_H
#include <cctype>
#include <cstddef>
#include <memory>
#include <set>
#include <stdexcept>
#include <string>
#include <vector>
enum class Kind { Empty, Epsilon, Symbol, Union, Concat, Star };
struct Regex;
// Un árbol no cambia después de construido, así que dos expresiones pueden compartir un subárbol.
using RegexPtr = std::shared_ptr<const Regex>;
struct Regex {
Kind kind;
char symbol; // solo si kind == Symbol
RegexPtr left; // el único hijo de Star; el hijo izquierdo de Union y de Concat
RegexPtr right;
};
// ------------------------------------------------------------
// Los seis casos de la definición
// ------------------------------------------------------------
inline RegexPtr empty_set() {
return std::make_shared<const Regex>(Regex{Kind::Empty, '\0', nullptr, nullptr});
}
inline RegexPtr epsilon() {
return std::make_shared<const Regex>(Regex{Kind::Epsilon, '\0', nullptr, nullptr});
}
inline RegexPtr symbol(char a) {
return std::make_shared<const Regex>(Regex{Kind::Symbol, a, nullptr, nullptr});
}
inline RegexPtr make_union(const RegexPtr& r1, const RegexPtr& r2) {
return std::make_shared<const Regex>(Regex{Kind::Union, '\0', r1, r2});
}
inline RegexPtr make_concat(const RegexPtr& r1, const RegexPtr& r2) {
return std::make_shared<const Regex>(Regex{Kind::Concat, '\0', r1, r2});
}
inline RegexPtr make_star(const RegexPtr& r) {
return std::make_shared<const Regex>(Regex{Kind::Star, '\0', r, nullptr});
}
// ------------------------------------------------------------
// Las mismas operaciones, aplicando las identidades de ∅ y de ε
// ------------------------------------------------------------
// R ∪ ∅ = ∅ ∪ R = R.
inline RegexPtr simple_union(const RegexPtr& r1, const RegexPtr& r2) {
if (r1->kind == Kind::Empty) {
return r2;
}
if (r2->kind == Kind::Empty) {
return r1;
}
return make_union(r1, r2);
}
// R∅ = ∅R = ∅ y Rε = εR = R.
inline RegexPtr simple_concat(const RegexPtr& r1, const RegexPtr& r2) {
if (r1->kind == Kind::Empty || r2->kind == Kind::Empty) {
return empty_set();
}
if (r1->kind == Kind::Epsilon) {
return r2;
}
if (r2->kind == Kind::Epsilon) {
return r1;
}
return make_concat(r1, r2);
}
// ∅* = ε y ε* = ε.
inline RegexPtr simple_star(const RegexPtr& r) {
if (r->kind == Kind::Empty || r->kind == Kind::Epsilon) {
return epsilon();
}
return make_star(r);
}
// ------------------------------------------------------------
// Medidas
// ------------------------------------------------------------
// El tamaño de una expresión: cuántos nodos tiene su árbol.
inline std::size_t size(const RegexPtr& r) {
switch (r->kind) {
case Kind::Union:
case Kind::Concat:
return 1 + size(r->left) + size(r->right);
case Kind::Star:
return 1 + size(r->left);
default:
return 1;
}
}
// Cuántas hojas, uniones y estrellas tiene: de eso depende el tamaño del NFA de Thompson.
inline std::size_t count_without_concat(const RegexPtr& r) {
switch (r->kind) {
case Kind::Union:
return 1 + count_without_concat(r->left) + count_without_concat(r->right);
case Kind::Concat:
return count_without_concat(r->left) + count_without_concat(r->right);
case Kind::Star:
return 1 + count_without_concat(r->left);
default:
return 1;
}
}
inline void collect_symbols(const RegexPtr& r, std::set<char>& symbols) {
if (r->kind == Kind::Symbol) {
symbols.insert(r->symbol);
}
if (r->left) {
collect_symbols(r->left, symbols);
}
if (r->right) {
collect_symbols(r->right, symbols);
}
}
// Los símbolos que aparecen en la expresión, en orden.
inline std::vector<char> symbols_of(const RegexPtr& r) {
std::set<char> symbols;
collect_symbols(r, symbols);
return std::vector<char>(symbols.begin(), symbols.end());
}
// ------------------------------------------------------------
// Escribir
// ------------------------------------------------------------
// Qué tan fuerte liga cada operación: la unión 1, la concatenación 2, la estrella 3.
// Las hojas no necesitan paréntesis nunca.
inline int precedence(Kind kind) {
switch (kind) {
case Kind::Union:
return 1;
case Kind::Concat:
return 2;
case Kind::Star:
return 3;
default:
return 4;
}
}
inline std::string to_string(const RegexPtr& r);
// Escribe r como operando de una operación de precedencia level: con paréntesis solo si r
// liga más débil que ella.
inline std::string operand(const RegexPtr& r, int level) {
std::string text = to_string(r);
return precedence(r->kind) < level ? "(" + text + ")" : text;
}
// La expresión con los paréntesis justos. La unión y la concatenación son asociativas, así
// que (R1|R2)|R3 y R1|(R2|R3) se escriben igual: R1|R2|R3.
inline std::string to_string(const RegexPtr& r) {
switch (r->kind) {
case Kind::Empty:
return "∅";
case Kind::Epsilon:
return "ε";
case Kind::Symbol:
return std::string(1, r->symbol);
case Kind::Union:
return operand(r->left, 1) + "|" + operand(r->right, 1);
case Kind::Concat:
return operand(r->left, 2) + operand(r->right, 2);
case Kind::Star:
// Una estrella sobre otra estrella lleva paréntesis para que se lea: (a*)*.
return (r->left->kind == Kind::Star ? "(" + to_string(r->left) + ")" : operand(r->left, 3)) + "*";
}
return "";
}
// La expresión con todos los paréntesis, un par por cada operación: muestra el árbol sin
// depender de la precedencia.
inline std::string to_string_full(const RegexPtr& r) {
switch (r->kind) {
case Kind::Union:
return "(" + to_string_full(r->left) + "|" + to_string_full(r->right) + ")";
case Kind::Concat:
return "(" + to_string_full(r->left) + to_string_full(r->right) + ")";
case Kind::Star:
return "(" + to_string_full(r->left) + "*)";
default:
return to_string(r);
}
}
inline void tree_lines(const RegexPtr& r, const std::string& indent, std::string& out) {
switch (r->kind) {
case Kind::Union:
out += indent + "unión\n";
break;
case Kind::Concat:
out += indent + "concatenación\n";
break;
case Kind::Star:
out += indent + "estrella\n";
break;
default:
out += indent + to_string(r) + "\n";
break;
}
if (r->left) {
tree_lines(r->left, indent + " ", out);
}
if (r->right) {
tree_lines(r->right, indent + " ", out);
}
}
// El árbol, un nodo por línea, con los hijos debajo y más adentro.
inline std::string tree(const RegexPtr& r) {
std::string out;
tree_lines(r, "", out);
return out;
}
// ------------------------------------------------------------
// Leer: un parser recursivo, con una función por nivel de precedencia
// ------------------------------------------------------------
//
// unión → concatenación ( '|' concatenación )*
// concatenación → estrella estrella*
// estrella → átomo '*'*
// átomo → símbolo | ε | ∅ | '(' unión ')'
struct RegexParser {
std::string text;
std::size_t pos = 0;
[[noreturn]] void fail(const std::string& message) const {
throw std::runtime_error("posición " + std::to_string(pos + 1) + ": " + message);
}
void skip_spaces() {
while (pos < text.size() && text[pos] == ' ') {
pos++;
}
}
// ¿Sigue el texto s en la posición actual? Si sigue, lo consume.
bool take(const std::string& s) {
skip_spaces();
if (text.compare(pos, s.size(), s) == 0) {
pos += s.size();
return true;
}
return false;
}
// ¿Empieza un átomo en la posición actual? Sirve para saber si la concatenación sigue.
bool atom_ahead() {
skip_spaces();
if (pos >= text.size()) {
return false;
}
unsigned char c = static_cast<unsigned char>(text[pos]);
return std::isalnum(c) != 0 || c == '(' || c == '%' || c == '@' || text.compare(pos, 2, "ε") == 0 ||
text.compare(pos, 3, "∅") == 0;
}
RegexPtr parse_atom() {
if (take("(")) {
RegexPtr inside = parse_union();
if (!take(")")) {
fail("falta cerrar un paréntesis");
}
return inside;
}
if (take("%") || take("ε")) {
return epsilon();
}
if (take("@") || take("∅")) {
return empty_set();
}
skip_spaces();
if (pos < text.size() && std::isalnum(static_cast<unsigned char>(text[pos])) != 0) {
return symbol(text[pos++]);
}
if (pos >= text.size()) {
fail("la expresión termina donde se esperaba un símbolo o un paréntesis");
}
fail(std::string("se esperaba un símbolo o un paréntesis, y hay ") + text[pos]);
}
RegexPtr parse_star() {
RegexPtr r = parse_atom();
while (take("*")) {
r = make_star(r);
}
return r;
}
RegexPtr parse_concat() {
RegexPtr r = parse_star();
while (atom_ahead()) {
RegexPtr next = parse_star();
r = make_concat(r, next);
}
return r;
}
RegexPtr parse_union() {
RegexPtr r = parse_concat();
while (take("|")) {
RegexPtr next = parse_concat();
r = make_union(r, next);
}
return r;
}
};
// Lee una expresión completa. Lanza std::runtime_error si no está bien formada.
inline RegexPtr parse_regex(const std::string& text) {
RegexParser parser{text};
RegexPtr r = parser.parse_union();
parser.skip_spaces();
if (parser.pos != text.size()) {
parser.fail(std::string("sobra ") + text[parser.pos]);
}
return r;
}
#endif// Sigue un NFA con una o más cadenas: run_nfa ARCHIVO.nfa CADENA...
// Con - en lugar del archivo, lee la descripción de la entrada estándar.
// Muestra el conjunto de estados activos antes de leer nada y después de cada símbolo.
// La cadena vacía se pasa como '' en la terminal.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include "nfa.h"
#include "words.h"
int main(int argc, char** argv) {
if (argc < 3) {
std::cerr << "uso: run_nfa ARCHIVO.nfa CADENA...\n";
return 2;
}
try {
std::string path = argv[1];
Nfa n = (path == "-") ? read_nfa(std::cin) : load_nfa(path);
for (int i = 2; i < argc; i++) {
std::string w = argv[i];
std::vector<StateSet> sets = run(n, w);
std::cout << "w = " << show(w) << '\n';
std::cout << " inicio " << show_set(n, sets[0]) << '\n';
for (std::size_t k = 0; k < w.size(); k++) {
std::cout << " lee " << w[k] << " " << show_set(n, sets[k + 1]) << '\n';
}
bool ok = false;
for (const std::string& q : sets.back()) {
ok = ok || n.accept.count(q) > 0;
}
std::cout << (ok ? " hay un estado de F entre los activos: acepta\n"
: " ningún estado activo está en F: rechaza\n");
}
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// De expresión regular a NFA con la construcción de Thompson: thompson EXPRESIÓN [ALFABETO]
// Escribe el NFA en el formato .nfa. Sin alfabeto, usa los símbolos de la expresión.
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include "nfa.h"
#include "regex.h"
#include "thompson.h"
int main(int argc, char** argv) {
if (argc < 2 || argc > 3) {
std::cerr << "uso: thompson EXPRESIÓN [ALFABETO]\n";
return 2;
}
try {
RegexPtr r = parse_regex(argv[1]);
std::vector<char> alphabet = symbols_of(r);
if (argc == 3) {
std::string given = argv[2];
alphabet.assign(given.begin(), given.end());
}
Nfa n = thompson(r, alphabet);
std::cout << "# NFA de Thompson de " << to_string(r) << '\n';
write_nfa(std::cout, n);
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Construcción de Thompson: de una expresión regular a un NFA con transiciones ε.
// Hay una pieza por cada caso de la definición de expresión regular. Cada pieza tiene un solo
// estado inicial y un solo estado de aceptación, y por eso se pueden conectar sin mirar adentro.
#ifndef THOMPSON_H
#define THOMPSON_H
#include <stdexcept>
#include <string>
#include <vector>
#include "nfa.h"
#include "regex.h"
// Una pieza ya construida dentro del NFA: por dónde se entra y por dónde se sale.
struct Fragment {
std::string start;
std::string accept;
};
// Agrega un estado nuevo, con el siguiente nombre libre: q0, q1, q2…
inline std::string new_state(Nfa& n) {
std::string name = "q" + std::to_string(n.states.size());
n.states.push_back(name);
return name;
}
// Construye dentro de n la pieza de r y dice cuáles son su entrada y su salida.
inline Fragment build_fragment(Nfa& n, const RegexPtr& r) {
switch (r->kind) {
case Kind::Empty: {
// Dos estados sin ninguna flecha: no hay camino de la entrada a la salida.
std::string s = new_state(n);
std::string f = new_state(n);
return {s, f};
}
case Kind::Epsilon: {
std::string s = new_state(n);
std::string f = new_state(n);
n.delta[{s, EPS}].insert(f);
return {s, f};
}
case Kind::Symbol: {
std::string s = new_state(n);
std::string f = new_state(n);
n.delta[{s, r->symbol}].insert(f);
return {s, f};
}
case Kind::Union: {
// Una entrada nueva que elige una de las dos piezas, y una salida nueva para las dos.
std::string s = new_state(n);
Fragment a = build_fragment(n, r->left);
Fragment b = build_fragment(n, r->right);
std::string f = new_state(n);
n.delta[{s, EPS}].insert(a.start);
n.delta[{s, EPS}].insert(b.start);
n.delta[{a.accept, EPS}].insert(f);
n.delta[{b.accept, EPS}].insert(f);
return {s, f};
}
case Kind::Concat: {
// La salida de la primera pieza se une con la entrada de la segunda.
Fragment a = build_fragment(n, r->left);
Fragment b = build_fragment(n, r->right);
n.delta[{a.accept, EPS}].insert(b.start);
return {a.start, b.accept};
}
case Kind::Star: {
// Entrada y salida nuevas: se puede saltar la pieza, o recorrerla y repetir.
std::string s = new_state(n);
Fragment a = build_fragment(n, r->left);
std::string f = new_state(n);
n.delta[{s, EPS}].insert(a.start);
n.delta[{s, EPS}].insert(f);
n.delta[{a.accept, EPS}].insert(a.start);
n.delta[{a.accept, EPS}].insert(f);
return {s, f};
}
}
throw std::runtime_error("expresión mal formada");
}
// El NFA de Thompson de r sobre el alfabeto dado, que debe contener los símbolos de r.
inline Nfa thompson(const RegexPtr& r, const std::vector<char>& alphabet) {
Nfa n;
n.alphabet = alphabet;
Fragment whole = build_fragment(n, r);
n.start = whole.start;
n.accept = {whole.accept};
check_nfa(n);
return n;
}
// Lo mismo, con el alfabeto formado por los símbolos que aparecen en r.
inline Nfa thompson(const RegexPtr& r) {
return thompson(r, symbols_of(r));
}
#endif// Listar cadenas, para comprobar un lenguaje con todas las cadenas cortas.
#ifndef WORDS_H
#define WORDS_H
#include <cstddef>
#include <string>
#include <vector>
// Todas las cadenas sobre el alfabeto con longitud a lo sumo max_len, primero las más cortas
// y, entre las de igual longitud, en el orden del alfabeto. Es la función de la semana 1.
inline std::vector<std::string> all_strings(const std::vector<char>& alphabet, std::size_t max_len) {
std::vector<std::string> result = {""};
std::size_t first = 0; // dónde empiezan las cadenas de la longitud anterior
for (std::size_t len = 1; len <= max_len; len++) {
std::size_t last = result.size();
for (std::size_t i = first; i < last; i++) {
for (char a : alphabet) {
result.push_back(result[i] + a);
}
}
first = last;
}
return result;
}
// Para imprimir: la cadena vacía se muestra como ε.
inline std::string show(const std::string& w) {
return w.empty() ? "ε" : w;
}
#endif# NFA de Thompson de (ab|a)*
states: q0 q1 q2 q3 q4 q5 q6 q7 q8 q9
alphabet: a b
start: q0
accept: q9
delta:
q0 eps q1 q9
q1 eps q2 q6
q2 a q3
q3 eps q4
q4 b q5
q5 eps q8
q6 a q7
q7 eps q8
q8 eps q1 q9# 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# NFA de Thompson de (0|1)*1
states: q0 q1 q2 q3 q4 q5 q6 q7 q8 q9
alphabet: 0 1
start: q0
accept: q9
delta:
q0 eps q1 q7
q1 eps q2 q4
q2 0 q3
q3 eps q6
q4 1 q5
q5 eps q6
q6 eps q1 q7
q7 eps q8
q8 1 q9# 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# Cadenas binarias que, leídas como un número en base 2, dan un múltiplo de 3.
# La cadena vacía vale 0. El estado rK dice que el valor de lo leído deja resto K al dividir entre 3.
states: r0 r1 r2
alphabet: 0 1
start: r0
accept: r0
delta:
r0 0 r0
r0 1 r1
r1 0 r2
r1 1 r0
r2 0 r1
r2 1 r2# Cadenas binarias que no contienen 11.
# q0: sin 11 y no termina en 1. q1: sin 11 y termina en 1. q2: ya apareció 11 (estado trampa).
states: q0 q1 q2
alphabet: 0 1
start: q0
accept: q0 q1
delta:
q0 0 q0
q0 1 q1
q1 0 q0
q1 1 q2
q2 0 q2
q2 1 q2Errores
Ejemplos con errores a propósito: no compilan, fallan o dan un resultado incorrecto. Los apuntes explican cada uno.
# Expresiones mal formadas: el parser debe rechazar cada una. Una por línea.
# Una unión a la que le falta el lado derecho.
0|
# Una unión a la que le falta el lado izquierdo.
|1
# Dos barras seguidas: entre ellas no hay nada. La expresión vacía no existe; ε se escribe %.
0||1
# Una estrella sin nada a su izquierda.
*0
# Una estrella justo después de abrir un paréntesis.
(*0)
# Un paréntesis sin cerrar.
(0|1
# Un paréntesis que nadie abrió.
0|1)
# Paréntesis sin nada adentro.
()
# Un carácter que no es símbolo ni operador: el + de las herramientas no está en la definición.
0+1Pruebas
Comprueban lo que afirman los apuntes; se ejecutan con make test.
// Pruebas del buscador con backtracking (sesión B): responde lo mismo que la simulación del
// NFA, termina con estrellas anidadas, y con (a|a)*b contra a^n hace 10·2^n − 4 llamadas.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <string>
#include <vector>
#include "backtrack.h"
#include "nfa.h"
#include "regex.h"
#include "thompson.h"
#include "words.h"
static std::size_t test_agrees_with_nfa() {
std::vector<std::string> expressions = {
"(0|1)*1", "((0|1)(0|1))*", "0*10*10*", "(1|01*0)*", "(0|10)*(%|1)", "(01)*|(10)*",
"(0*)*1", "(0|%)*1", "(0*1*)*", "@", "%", "(0|@)1",
"(%|0)*", "((0|1)*)*",
};
std::vector<std::string> words = all_strings({'0', '1'}, 8);
for (const std::string& text : expressions) {
RegexPtr r = parse_regex(text);
Nfa n = thompson(r, {'0', '1'});
for (const std::string& w : words) {
assert(backtrack_accepts(r, w) == accepts(n, w));
}
}
return expressions.size();
}
static void test_bad_case() {
RegexPtr r = parse_regex("(a|a)*b");
long long calls = 0;
assert(backtrack_accepts(r, "aab", &calls) && calls == 12);
assert(!backtrack_accepts(r, "aaa", &calls) && calls == 76);
long long power = 1;
for (std::size_t n = 0; n <= 14; n++) {
assert(!backtrack_accepts(r, std::string(n, 'a'), &calls));
assert(calls == 10 * power - 4);
power *= 2;
}
// Con la b al final, la primera rama que prueba ya acierta: las llamadas son lineales.
for (std::size_t n = 0; n <= 14; n++) {
assert(backtrack_accepts(r, std::string(n, 'a') + "b", &calls));
assert(calls == static_cast<long long>(3 * n + 6));
}
}
int main() {
std::size_t expressions = test_agrees_with_nfa();
test_bad_case();
std::printf("test_backtrack: ok (%zu expresiones, 511 cadenas cada una)\n", expressions);
}// Pruebas de la eliminación de estados (sesión B).
// La expresión que sale de un DFA se vuelve a leer, se convierte en un NFA con la construcción
// de Thompson y se compara con el DFA original sobre todas las cadenas cortas. Así se cierra
// el triángulo: DFA → expresión → NFA, y los dos extremos deben aceptar lo mismo.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <string>
#include <vector>
#include "dfa.h"
#include "gnfa.h"
#include "nfa.h"
#include "regex.h"
#include "thompson.h"
#include "words.h"
// La expresión, pasando por su texto: comprueba de paso que lo escrito se puede volver a leer.
static Nfa nfa_of(const RegexPtr& r, const std::vector<char>& alphabet) {
return thompson(parse_regex(to_string(r)), alphabet);
}
static void check_equivalent(const Dfa& m, const RegexPtr& r, std::size_t max_len) {
Nfa n = nfa_of(r, m.alphabet);
for (const std::string& w : all_strings(m.alphabet, max_len)) {
assert(accepts(m, w) == accepts(n, w));
}
}
// Todos los órdenes de eliminación de m. Devuelve cuántos son.
static std::size_t check_all_orders(const std::string& path, std::size_t max_len) {
Dfa m = load_dfa(path);
std::vector<std::string> order = m.states;
std::sort(order.begin(), order.end());
std::size_t count = 0;
do {
check_equivalent(m, to_regex(m, order), max_len);
count++;
} while (std::next_permutation(order.begin(), order.end()));
return count;
}
static Dfa multiples_of(int k) {
Dfa m;
m.alphabet = {'0', '1'};
for (int i = 0; i < k; i++) {
m.states.push_back("r" + std::to_string(i));
}
m.start = "r0";
m.accept = {"r0"};
for (int i = 0; i < k; i++) {
m.delta[{m.states[i], '0'}] = m.states[(2 * i) % k];
m.delta[{m.states[i], '1'}] = m.states[(2 * i + 1) % k];
}
check_dfa(m);
return m;
}
static void test_gnfa_of_dfa() {
Dfa m = load_dfa("machines/multiple_of_3.dfa");
Gnfa g = to_gnfa(m);
assert(g.states == (std::vector<std::string>{"ini", "r0", "r1", "r2", "fin"}));
assert(g.arrow.size() == 8);
assert(to_string(label(g, "ini", "r0")) == "ε");
assert(to_string(label(g, "r0", "fin")) == "ε");
assert(to_string(label(g, "r0", "r1")) == "1");
assert(to_string(label(g, "r2", "r2")) == "1");
assert(label(g, "r0", "r2")->kind == Kind::Empty); // la flecha que no está lleva ∅
// Al inicial no le entra nada y del de aceptación no sale nada.
for (const auto& [key, r] : g.arrow) {
assert(key.second != g.start && key.first != g.accept);
}
// Dos símbolos entre los mismos estados se juntan en una unión.
Dfa all;
all.states = {"q"};
all.alphabet = {'0', '1'};
all.start = "q";
all.accept = {"q"};
all.delta[{"q", '0'}] = "q";
all.delta[{"q", '1'}] = "q";
assert(to_string(label(to_gnfa(all), "q", "q")) == "0|1");
assert(to_string(to_regex(all, {"q"})) == "(0|1)*");
// Sin estados de aceptación no hay camino hasta fin: sale ∅.
all.accept.clear();
assert(to_regex(all, {"q"})->kind == Kind::Empty);
}
static void test_steps_of_the_notes() {
// El ejemplo de dos estados, en los dos órdenes.
Dfa parity = load_dfa("machines/even_ones.dfa");
Gnfa g = eliminate(to_gnfa(parity), "impar");
assert(g.arrow.size() == 3);
assert(to_string(label(g, "par", "par")) == "0|10*1");
assert(to_string(to_regex(parity, {"impar", "par"})) == "(0|10*1)*");
Gnfa h = eliminate(to_gnfa(parity), "par");
assert(to_string(label(h, "ini", "impar")) == "0*1");
assert(to_string(label(h, "ini", "fin")) == "0*");
assert(to_string(label(h, "impar", "impar")) == "0|10*1");
assert(to_string(label(h, "impar", "fin")) == "10*");
assert(to_string(to_regex(parity, {"par", "impar"})) == "0*|0*1(0|10*1)*10*");
// El ejemplo completo de tres estados: r2, r1, r0.
Dfa three = load_dfa("machines/multiple_of_3.dfa");
Gnfa a = eliminate(to_gnfa(three), "r2");
assert(a.arrow.size() == 6);
assert(to_string(label(a, "r1", "r1")) == "01*0");
assert(to_string(label(a, "r0", "r1")) == "1" && to_string(label(a, "r1", "r0")) == "1");
Gnfa b = eliminate(a, "r1");
assert(b.arrow.size() == 3);
assert(to_string(label(b, "r0", "r0")) == "0|1(01*0)*1");
assert(to_string(to_regex(three, {"r2", "r1", "r0"})) == "(0|1(01*0)*1)*");
assert(size(to_regex(three, {"r2", "r1", "r0"})) == 14);
assert(to_string(to_regex(three, {"r1", "r2", "r0"})) == "(0|11|10(1|00)*01)*");
assert(size(to_regex(three, {"r0", "r1", "r2"})) == 65);
// La de 14 nodos y la de 65 describen el mismo lenguaje: los múltiplos de 3.
Nfa small = nfa_of(to_regex(three, {"r2", "r1", "r0"}), three.alphabet);
Nfa large = nfa_of(to_regex(three, {"r0", "r1", "r2"}), three.alphabet);
for (const std::string& w : all_strings(three.alphabet, 9)) {
bool multiple = w.empty() || std::stoul(w, nullptr, 2) % 3 == 0;
assert(accepts(small, w) == multiple && accepts(large, w) == multiple);
}
// Termina en 01.
Dfa ends = load_dfa("machines/ends_01.dfa");
assert(to_string(to_regex(ends, {"q2", "q0", "q1"})) == "1*0(0|10|111*0)*1");
// No es la más corta: (0|1)*01 describe lo mismo que el autómata.
check_equivalent(ends, parse_regex("(0|1)*01"), 9);
// Sin 11: la eliminación devuelve la expresión que la sesión A escribió a mano.
Dfa no_11 = load_dfa("machines/no_11.dfa");
assert(to_string(to_regex(no_11, {"q2", "q1", "q0"})) == "(0|10)*(ε|1)");
assert(to_string(to_regex(no_11, {"q0", "q1", "q2"})) == "0*|0*1(00*1)*(ε|00*)");
}
static void test_growth_table() {
// La tabla de growth: nodos de la expresión con r0 primero y con r0 al final.
std::vector<std::vector<std::size_t>> expected = {{2, 22, 9}, {3, 65, 14}, {4, 110, 27}, {5, 314, 52}};
for (const std::vector<std::size_t>& row : expected) {
Dfa m = multiples_of(static_cast<int>(row[0]));
std::vector<std::string> backward(m.states.rbegin(), m.states.rend());
RegexPtr first = to_regex(m, m.states);
RegexPtr last = to_regex(m, backward);
assert(size(first) == row[1] && size(last) == row[2]);
check_equivalent(m, first, 6);
check_equivalent(m, last, 6);
}
}
int main() {
test_gnfa_of_dfa();
test_steps_of_the_notes();
std::size_t orders = 0;
orders += check_all_orders("machines/even_ones.dfa", 8);
orders += check_all_orders("machines/multiple_of_3.dfa", 8);
orders += check_all_orders("machines/ends_01.dfa", 8);
orders += check_all_orders("machines/no_11.dfa", 8);
test_growth_table();
std::printf("test_elimination: ok (4 autómatas, %zu órdenes de eliminación, 511 cadenas cada uno)\n", orders);
}// Pruebas del parser y de la escritura de expresiones regulares (sesión A).
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <fstream>
#include <stdexcept>
#include <string>
#include <vector>
#include "regex.h"
static bool is_malformed(const std::string& text) {
try {
parse_regex(text);
} catch (const std::runtime_error&) {
return true;
}
return false;
}
static void test_precedence() {
// La estrella liga más que la concatenación, y la concatenación más que la unión.
assert(to_string_full(parse_regex("ab|c*")) == "((ab)|(c*))");
assert(to_string_full(parse_regex("ab*")) == "(a(b*))");
assert(to_string_full(parse_regex("(ab)*")) == "((ab)*)");
assert(to_string_full(parse_regex("a|bc")) == "(a|(bc))");
assert(to_string_full(parse_regex("(a|b)c")) == "((a|b)c)");
assert(to_string_full(parse_regex("(0|1)*1")) == "(((0|1)*)1)");
assert(to_string_full(parse_regex("0|1*")) == "(0|(1*))");
// La unión y la concatenación se agrupan hacia la izquierda.
assert(to_string_full(parse_regex("abc")) == "((ab)c)");
assert(to_string_full(parse_regex("a|b|c")) == "((a|b)|c)");
// El árbol de (0|1)*1: la raíz es la concatenación.
RegexPtr r = parse_regex("(0|1)*1");
assert(r->kind == Kind::Concat);
assert(r->left->kind == Kind::Star && r->left->left->kind == Kind::Union);
assert(r->right->kind == Kind::Symbol && r->right->symbol == '1');
assert(size(r) == 6);
assert(tree(parse_regex("ab|c*")) ==
"unión\n concatenación\n a\n b\n estrella\n c\n");
}
static void test_epsilon_and_empty() {
assert(parse_regex("%")->kind == Kind::Epsilon);
assert(parse_regex("ε")->kind == Kind::Epsilon);
assert(parse_regex("@")->kind == Kind::Empty);
assert(parse_regex("∅")->kind == Kind::Empty);
assert(to_string(parse_regex("(0|%)1*")) == "(0|ε)1*");
assert(to_string(parse_regex("(0|ε)1*")) == "(0|ε)1*");
assert(to_string(parse_regex("@*")) == "∅*");
assert(to_string(parse_regex(" 0* 1 0* ")) == "0*10*");
}
static void test_round_trip() {
// Lo que se escribe se vuelve a leer y se escribe igual, con los paréntesis justos.
std::vector<std::string> expressions = {
"(0|1)*1", "((0|1)(0|1))*", "0*10*10*", "1*(01*01*)*", "(1|01*0)*", "(0|10)*(ε|1)",
"(0|ε)1*", "(01)*|(10)*", "(1|01*01*0)*", "(ab|a)*", "(a*)*", "(a|a)*b",
"∅*", "a|b|c", "(a|b)(c|d)", "a(b|c)*d", "0|1*", "(0|1*)*",
};
for (const std::string& text : expressions) {
RegexPtr r = parse_regex(text);
assert(to_string(r) == text);
assert(to_string(parse_regex(to_string(r))) == text);
assert(to_string(parse_regex(to_string_full(r))) == text);
}
// Paréntesis de más: se leen y no se vuelven a escribir.
assert(to_string(parse_regex("((0)|(1))*")) == "(0|1)*");
assert(to_string(parse_regex("(a(b))c")) == "abc");
assert(to_string(parse_regex("a**")) == "(a*)*");
}
static void test_simplified_operations() {
RegexPtr r = parse_regex("0|1");
assert(to_string(simple_union(r, empty_set())) == "0|1");
assert(to_string(simple_union(empty_set(), r)) == "0|1");
assert(simple_concat(r, empty_set())->kind == Kind::Empty);
assert(simple_concat(empty_set(), r)->kind == Kind::Empty);
assert(to_string(simple_concat(r, epsilon())) == "0|1");
assert(to_string(simple_concat(epsilon(), r)) == "0|1");
assert(simple_star(empty_set())->kind == Kind::Epsilon);
assert(simple_star(epsilon())->kind == Kind::Epsilon);
assert(to_string(simple_star(r)) == "(0|1)*");
}
static std::size_t test_malformed() {
std::ifstream file("errors/malformed.txt");
assert(file);
std::string line;
std::size_t count = 0;
while (std::getline(file, line)) {
if (line.empty() || line[0] == '#') {
continue;
}
assert(is_malformed(line));
count++;
}
assert(count == 9);
assert(is_malformed(""));
assert(is_malformed(" "));
// El mensaje dice dónde está el problema.
try {
parse_regex("0|*");
assert(false);
} catch (const std::runtime_error& error) {
assert(std::string(error.what()) == "posición 3: se esperaba un símbolo o un paréntesis, y hay *");
}
return count;
}
int main() {
test_precedence();
test_epsilon_and_empty();
test_round_trip();
test_simplified_operations();
std::size_t malformed = test_malformed();
std::printf("test_regex: ok (%zu expresiones mal formadas rechazadas)\n", malformed);
}// Pruebas de la construcción de Thompson (sesión A).
// Cada expresión de los apuntes se convierte en un NFA y se compara con una función de C++
// que decide el mismo lenguaje mirando la cadena completa, sobre todas las cadenas cortas.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <functional>
#include <map>
#include <sstream>
#include <string>
#include <vector>
#include "nfa.h"
#include "regex.h"
#include "thompson.h"
#include "words.h"
using Predicate = std::function<bool(const std::string&)>;
static int count_of(const std::string& w, char c) {
int total = 0;
for (char x : w) {
total += (x == c);
}
return total;
}
static bool contains(const std::string& w, const std::string& piece) {
return w.find(piece) != std::string::npos;
}
// w es una repetición de la pieza: ε, pieza, pieza pieza, …
static bool is_power_of(const std::string& w, const std::string& piece) {
if (w.size() % piece.size() != 0) {
return false;
}
for (std::size_t i = 0; i < w.size(); i++) {
if (w[i] != piece[i % piece.size()]) {
return false;
}
}
return true;
}
// La forma del NFA de Thompson: un solo estado de aceptación, del que no sale nada; al
// inicial no entra nada; de cada estado salen a lo sumo dos flechas; y el número de estados
// es exactamente el doble del número de hojas, uniones y estrellas.
static void check_shape(const RegexPtr& r, const Nfa& n) {
assert(n.accept.size() == 1);
assert(n.states.size() == 2 * count_without_concat(r));
assert(n.states.size() <= 2 * size(r));
std::map<std::string, std::size_t> out;
for (const auto& [key, targets] : n.delta) {
out[key.first] += targets.size();
assert(targets.count(n.start) == 0);
}
for (const std::string& q : n.states) {
assert(out[q] <= 2);
}
assert(out[*n.accept.begin()] == 0);
}
// Compara L(r) con el predicado sobre todas las cadenas de longitud a lo sumo max_len.
static std::size_t check_language(const std::string& text, const std::vector<char>& alphabet, std::size_t max_len,
const Predicate& in_language) {
RegexPtr r = parse_regex(text);
Nfa n = thompson(r, alphabet);
check_shape(r, n);
std::vector<std::string> words = all_strings(alphabet, max_len);
for (const std::string& w : words) {
assert(accepts(n, w) == in_language(w));
}
return words.size();
}
// Dos expresiones describen el mismo lenguaje, hasta longitud max_len.
static void check_same(const std::string& text1, const std::string& text2, const std::vector<char>& alphabet,
std::size_t max_len) {
Nfa n1 = thompson(parse_regex(text1), alphabet);
Nfa n2 = thompson(parse_regex(text2), alphabet);
for (const std::string& w : all_strings(alphabet, max_len)) {
assert(accepts(n1, w) == accepts(n2, w));
}
}
static std::size_t test_examples() {
std::vector<char> binary = {'0', '1'};
std::size_t count = 0;
auto check = [&](const std::string& text, const Predicate& in_language) {
check_language(text, binary, 9, in_language);
count++;
};
// Las tres expresiones que se leen en la sesión A.
check("(0|1)*1", [](const std::string& w) { return !w.empty() && w.back() == '1'; });
check("((0|1)(0|1))*", [](const std::string& w) { return w.size() % 2 == 0; });
check("0*10*10*", [](const std::string& w) { return count_of(w, '1') == 2; });
// Las que se escriben: número par de ceros, sin 11.
check("1*(01*01*)*", [](const std::string& w) { return count_of(w, '0') % 2 == 0; });
check("(1|01*0)*", [](const std::string& w) { return count_of(w, '0') % 2 == 0; });
check("(0|10)*(%|1)", [](const std::string& w) { return !contains(w, "11"); });
// Los dos intentos fallidos de "sin 11": uno describe de menos y el otro de más.
check("(0|10)*", [](const std::string& w) { return !contains(w, "11") && (w.empty() || w.back() == '0'); });
check("(0|10)*1*", [](const std::string& w) {
// Sin 11 antes de la cola final de unos: quitando esa cola, queda vacío o termina en 0 sin 11.
std::size_t end = w.size();
while (end > 0 && w[end - 1] == '1') {
end--;
}
return !contains(w.substr(0, end), "11");
});
// Las de las preguntas de repaso de la guía.
check("(0|%)1*", [](const std::string& w) { return !contains(w.substr(w.empty() ? 0 : 1), "0"); });
check("(01)*|(10)*", [](const std::string& w) { return is_power_of(w, "01") || is_power_of(w, "10"); });
check("(1|01*01*0)*", [](const std::string& w) { return count_of(w, '0') % 3 == 0; });
// Σ*, y las cadenas que contienen 101.
check("(0|1)*", [](const std::string&) { return true; });
check("(0|1)*101(0|1)*", [](const std::string& w) { return contains(w, "101"); });
// (ab ∪ a)*: no empieza con b y no tiene bb.
check_language("(ab|a)*", {'a', 'b'}, 9,
[](const std::string& w) { return (w.empty() || w[0] == 'a') && !contains(w, "bb"); });
count++;
// Los enteros sin ceros a la izquierda, sobre los diez dígitos.
check_language("0|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*",
{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}, 3,
[](const std::string& w) { return w == "0" || (!w.empty() && w[0] != '0'); });
count++;
return count;
}
static void test_cases_of_the_definition() {
std::vector<char> binary = {'0', '1'};
check_language("@", binary, 6, [](const std::string&) { return false; });
check_language("%", binary, 6, [](const std::string& w) { return w.empty(); });
check_language("0", binary, 6, [](const std::string& w) { return w == "0"; });
check_language("0|1", binary, 6, [](const std::string& w) { return w == "0" || w == "1"; });
check_language("01", binary, 6, [](const std::string& w) { return w == "01"; });
check_language("0*", binary, 6, [](const std::string& w) { return count_of(w, '1') == 0; });
}
static void test_identities() {
std::vector<char> binary = {'0', '1'};
std::vector<std::string> some = {"0", "(0|1)*1", "0*10*10*", "(01)*|(10)*", "%", "@"};
for (const std::string& r : some) {
std::string p = "(" + r + ")";
check_same(p + "|@", r, binary, 6); // R ∪ ∅ = R
check_same(p + "@", "@", binary, 6); // R∅ = ∅
check_same("@" + p, "@", binary, 6); // ∅R = ∅
check_same(p + "%", r, binary, 6); // Rε = R
check_same("%" + p, r, binary, 6); // εR = R
check_same(p + "|" + p, r, binary, 6); // R ∪ R = R
check_same(p + "**", p + "*", binary, 6); // (R*)* = R*
}
// ∅* = {ε}: la estrella de ∅ no es ∅.
check_same("@*", "%", binary, 6);
check_same("%*", "%", binary, 6);
// Las dos trampas: R ∪ ε no es R, y Rε no es ∅.
Nfa with_eps = thompson(parse_regex("0|%"), binary);
assert(accepts(with_eps, "") && accepts(with_eps, "0"));
assert(!accepts(thompson(parse_regex("0"), binary), ""));
// Otras igualdades que se usan en los apuntes.
check_same("(0|1)*", "(0*1*)*", binary, 9);
check_same("1*(01*01*)*", "(1|01*0)*", binary, 9);
check_same("(0|10)*(%|1)", "(%|1)(0|01)*", binary, 9);
// Las abreviaturas de las herramientas, escritas con las tres operaciones.
check_language("00*", binary, 7, [](const std::string& w) { return !w.empty() && count_of(w, '1') == 0; });
check_language("(01)(01)((01)|%)", binary, 7, [](const std::string& w) { return w == "0101" || w == "010101"; });
}
static void test_run() {
// La ejecución que copian los apuntes: (0|1)*1 con 011.
RegexPtr r = parse_regex("(0|1)*1");
Nfa n = thompson(r);
assert(n.states.size() == 10);
assert(n.start == "q0" && n.accept == StateSet{"q9"});
std::vector<StateSet> sets = run(n, "011");
assert(sets.size() == 4);
assert(show_set(n, sets[0]) == "{q0, q1, q2, q4, q7, q8}");
assert(show_set(n, sets[1]) == "{q1, q2, q3, q4, q6, q7, q8}");
assert(show_set(n, sets[2]) == "{q1, q2, q4, q5, q6, q7, q8, q9}");
assert(show_set(n, sets[3]) == "{q1, q2, q4, q5, q6, q7, q8, q9}");
assert(accepts(n, "011") && !accepts(n, "010") && !accepts(n, ""));
// El archivo de machines/ es lo que escribe la construcción, y se vuelve a leer igual.
Nfa from_file = load_nfa("machines/ends_in_1.nfa");
std::ostringstream written;
std::ostringstream built;
write_nfa(written, from_file);
write_nfa(built, n);
assert(written.str() == built.str());
// (ab ∪ a)*, el de las preguntas de repaso.
Nfa second = load_nfa("machines/ab_or_a_star.nfa");
std::ostringstream written2;
std::ostringstream built2;
write_nfa(written2, second);
write_nfa(built2, thompson(parse_regex("(ab|a)*")));
assert(written2.str() == built2.str());
assert(second.states.size() == 10);
// Todo .dfa es un .nfa válido.
Nfa from_dfa = load_nfa("machines/even_ones.dfa");
for (const std::string& w : all_strings({'0', '1'}, 8)) {
assert(accepts(from_dfa, w) == (count_of(w, '1') % 2 == 0));
}
}
static void test_closure_with_cycles() {
// (a*)* tiene un ciclo de transiciones ε: la clausura debe terminar.
Nfa n = thompson(parse_regex("(a*)*b"), {'a', 'b'});
for (const std::string& w : all_strings({'a', 'b'}, 8)) {
bool expected = !w.empty() && w.back() == 'b' && count_of(w, 'b') == 1;
assert(accepts(n, w) == expected);
}
}
int main() {
test_cases_of_the_definition();
std::size_t examples = test_examples();
test_identities();
test_run();
test_closure_with_cycles();
std::printf("test_thompson: ok (%zu expresiones contra su predicado)\n", examples);
}Laboratorio
Archivos de partida del laboratorio de la semana.
TIEMPO = 2
include ../../../lab.mk# Un grep pequeño
`grep` recibe un patrón y un texto, y dice qué líneas del texto coinciden con el patrón. En este laboratorio
escriben la parte central de esa herramienta: reciben una expresión regular y una lista de líneas, y dicen por
cada línea si la expresión la describe **completa**.
Son las tres construcciones de la sesión A, una detrás de otra: el árbol de la expresión, el NFA de Thompson
y la simulación con el conjunto de estados activos.
## Entrada
La primera línea es la expresión regular. Después viene el bloque de cadenas de
[`code/formats.md`](../../../formats.md): una línea `strings: k` y $k$ líneas, una cadena por línea.
```text
(a|b)*abb
strings: 5
abb
babb
ab
abba
```
La expresión se escribe con la sintaxis del código de la semana, sin $\varepsilon$ ni $\emptyset$:
- Un **símbolo** es una letra minúscula de `a` a `z` o un dígito de `0` a `9`.
- La **unión** es `|`, la **concatenación** no se escribe y la **estrella** es `*`.
- Los **paréntesis** agrupan.
- **Precedencia:** primero la estrella, después la concatenación, al final la unión. `ab|cd*` es
$(\mathtt{ab}) \cup (\mathtt{c}(\mathtt{d}^*))$.
Con más precisión, la expresión sigue esta gramática, y no tiene espacios:
```text
unión → concatenación ( '|' concatenación )*
concatenación → estrella estrella*
estrella → átomo '*'*
átomo → símbolo | '(' unión ')'
```
Entonces una estrella puede llevar otra encima, `a**`, y puede haber paréntesis de más, `((a))`. No hay
alternativas vacías ni paréntesis vacíos: `a||b`, `(a|)` y `()` no aparecen.
Sobre las cadenas:
- **Una línea vacía es la cadena vacía $\varepsilon$**, y también hay que responder por ella.
- Las cadenas están formadas solo por letras minúsculas y dígitos. Pueden tener símbolos que no aparecen en
la expresión: una cadena así nunca coincide.
- En esta entrada no hay comentarios: ninguna línea empieza con `#`.
## Salida
Una línea por cada cadena, en el mismo orden: `acepta` si la expresión describe la cadena completa, y
`rechaza` si no.
Un `grep` de verdad imprimiría las líneas que coinciden. Aquí se imprime un veredicto por línea por una razón
práctica: el juez compara la salida palabra por palabra, sin mirar los saltos de línea, y una línea vacía que
coincide no dejaría ninguna huella en la salida. Con un veredicto por cadena, la respuesta a la cadena vacía
se ve, y un programa que no imprime nada falla siempre.
## Límites
- La expresión tiene entre 1 y 200 caracteres, y siempre está bien formada: no tienen que detectar errores.
- $1 \leq k \leq 20\,000$.
- Las longitudes de las cadenas suman a lo sumo 100 000. Una sola cadena puede tener esa longitud.
## Ejemplo
Para la entrada de arriba, la salida es:
```text
acepta
acepta
rechaza
rechaza
rechaza
```
La expresión describe las cadenas de letras `a` y `b` que terminan en `abb`. La tercera cadena es la vacía. La
última contiene `abb`, pero no termina ahí: la expresión tiene que describir la línea completa, como con
`grep -x`.
## Tiempo
2 segundos por caso. Se compila con `g++ -Wall -Wextra -std=c++20 -O2`.
El NFA de Thompson de una expresión de 200 caracteres tiene a lo sumo 400 estados. Simularlo con el conjunto
de estados activos cuesta, por cada símbolo de la cadena, una pasada por los estados activos: en total, del
orden de $100\,000 \cdot 400$ pasos en el peor caso, que entra con holgura.
Lo que **no** entra es el backtracking: probar una alternativa y, si falla, volver atrás y probar la otra. Uno
de los casos es la expresión `(a|a)*b` contra una línea de 50 000 letras `a`. No hay ninguna `b`, así que la
respuesta es `rechaza`, y una búsqueda con backtracking la encuentra después de probar las $2^{50\,000}$
maneras de elegir una rama para cada letra. Otros casos tienen estrellas dentro de estrellas, como
`(a*b*)*c`, que hacen lo mismo.
Dos cuidados más:
- **Los ciclos de transiciones $\varepsilon$.** Una estrella sobre algo que puede ser vacío, como `(a*)*`, da
un NFA en el que se puede volver al mismo estado sin leer nada. La clausura $\varepsilon$ tiene que marcar
los estados ya visitados, o no termina.
- **No construyan el DFA completo.** Uno de los casos es "el símbolo que está 38 posiciones antes del último
es una `a`", y su DFA tiene más de $2^{38}$ estados. El NFA tiene menos de 400.
## Qué se practica aquí
En `code/week-03` están `regex.h`, `thompson.h` y `nfa.h`, que hacen estos tres pasos para los ejemplos de los
apuntes, y pueden leerlos cuanto quieran. `solution.cpp` se escribe **sin incluirlos**: el juez compila ese
único archivo. Tampoco conviene copiarlos tal cual. Están escritos para parecerse a las definiciones, con los
estados guardados por su nombre en un `std::set`, y así la simulación no alcanza a pasar el caso más grande.
El trabajo del laboratorio es escribir los tres pasos de forma que el tercero cueste lo que dice el análisis:
- Los estados son **números** de 0 a $m - 1$, y $\delta$ son arreglos indexados por el estado. En el NFA de
Thompson, de cada estado sale una flecha con un símbolo, o una o dos transiciones $\varepsilon$, o nada: no
hace falta ninguna estructura más complicada.
- El conjunto de estados activos es una **lista** de estados más un arreglo de marcas, que dice si un estado
ya está en la lista. Así agregar un estado y preguntar si ya está cuestan tiempo constante. Un
`std::set<int>` también pasa, más justo.
## Cómo avanzar
```sh
make # compila solution.cpp en build/
make test # corre el juez con todos los casos
```
Los cuatro casos grandes no están guardados: `make test` los genera con los programas `casos/gen_NN.cpp`.
1. **Leer la entrada.** El esqueleto ya lee la expresión, la línea `strings:` y las cadenas, con
`std::getline`: una línea vacía es una cadena, y `>>` se la saltaría.
2. **El árbol de la expresión.** Escriban el parser con una función por cada línea de la gramática:
`parse_union` llama a `parse_concat`, que llama a `parse_star`, que llama a `parse_atom`. Cada función
devuelve el nodo que construyó. El esqueleto trae un `struct Node` como propuesta. Antes de seguir,
comprueben a mano el árbol de `ab|cd*` y el de `(a|b)*abb`.
3. **El NFA de Thompson.** Recorran el árbol de las hojas a la raíz. Cada nodo devuelve su pieza: el estado de
entrada y el de salida. Un símbolo crea dos estados y una flecha. La unión y la estrella crean dos estados
y cuatro transiciones $\varepsilon$. La concatenación no crea estados: une las dos piezas con una
transición $\varepsilon$.
4. **La simulación.** Empiecen con la clausura $\varepsilon$ del estado inicial. Por cada símbolo de la línea,
armen la lista siguiente: para cada estado activo que tenga una flecha con ese símbolo, agreguen el destino
y su clausura $\varepsilon$. Al final, la respuesta es si el estado de aceptación está entre los activos.
Si la lista queda vacía a mitad de la línea, ya pueden responder `rechaza`.
5. **Los casos de borde.** Antes de correr el juez, respondan a mano: ¿qué responde `a*` con la línea vacía?
¿Y `a`? ¿Qué pasa en su clausura $\varepsilon$ con `(a*)*`?
6. **El caso grande.** Corran `casos/11.in`, que es `(a|a)*b` con líneas de unas decenas de letras, y después
el juez completo.
Para probar una expresión propia sin escribir un archivo:
```sh
printf '(0|1)*1\nstrings: 3\n011\n\n010\n' | build/solution
```
Debe imprimir `acepta`, `rechaza`, `rechaza`.
Mientras desarrollan, compilen con sanitizers, como explica [`labs/README.md`](../../../../labs/README.md).
## Para seguir
Opcional, sin casos en el juez.
- Agreguen las abreviaturas `+` y `?` al parser, sin agregar tipos de nodo: `R+` es $RR^*$ y `R?` necesita
una pieza para $\varepsilon$.
- Hagan que el programa busque como `grep` sin `-x`: que acepte una línea si la expresión describe **alguna
subcadena** suya. No hace falta cambiar la simulación: basta cambiar el autómata. ¿Cómo?
- Guarden cada conjunto de estados activos la primera vez que aparece, con un número, y también a qué
conjunto lleva con cada símbolo. Es la construcción de subconjuntos de la semana pasada hecha sobre la
marcha. Midan cuántos conjuntos distintos aparecen en `casos/14.in`.// Un grep pequeño. Lee una expresión regular y una lista de líneas, e imprime por cada línea
// si la expresión la describe completa.
#include <iostream>
#include <string>
#include <vector>
// Un nodo del árbol de la expresión. Es una propuesta: pueden cambiarla.
// Los nodos se guardan en un std::vector y los hijos son posiciones en ese vector, así no
// hacen falta punteros.
struct Node {
char kind; // 'a' un símbolo, '|' unión, '.' concatenación, '*' estrella
char symbol; // solo si kind == 'a'
int left; // el hijo izquierdo, o el único hijo de una estrella; -1 si no tiene
int right; // el hijo derecho; -1 si no tiene
};
// El NFA de Thompson, también como propuesta. De cada estado sale una sola flecha con un
// símbolo o, como mucho, dos transiciones ε: δ cabe en tres arreglos indexados por el estado.
struct Nfa {
std::vector<char> symbol; // el símbolo de la flecha que sale del estado, o '\0' si no hay
std::vector<int> next; // a dónde lleva esa flecha
std::vector<int> eps1; // destinos de las transiciones ε, o -1
std::vector<int> eps2;
int start = 0;
int accept = 0;
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::string expression;
std::getline(std::cin, expression);
std::vector<Node> nodes;
// Por hacer (paso 2): el árbol de expression, respetando la precedencia.
Nfa n;
// Por hacer (paso 3): el NFA de Thompson del árbol.
std::string line;
std::getline(std::cin, line); // strings: k
int k = std::stoi(line.substr(line.find(':') + 1));
for (int i = 0; i < k; i++) {
std::getline(std::cin, line); // una línea vacía es la cadena ε
// Por hacer (paso 4): simular n con line, llevando el conjunto de estados activos,
// e imprimir acepta o rechaza.
}
// Este esqueleto no imprime nada, así que el juez da WA en todos los casos.
return static_cast<int>(nodes.size() + n.symbol.size());
}Compilación
Cómo se compilan y ejecutan los ejemplos.
# Semana 3: expresiones regulares, construcción de Thompson y eliminación de estados.
# Se usa dentro del entorno del curso.
#
# make compila los programas de la clase en build/
# make test corre las pruebas de los ejemplos, con sanitizers
# make bench compara el backtracking con la simulación del NFA (compila con -O2)
# make clean borra lo generado
#
# Las pruebas leen los autómatas de machines/, así que se corren desde esta carpeta.
# El laboratorio está en lab/mini_grep y tiene su propio Makefile: estas reglas no lo tocan.
CXX = g++
CXXFLAGS = -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined
BENCHFLAGS = -Wall -Wextra -std=c++20 -O2
BUILD = build
PROGRAMS = regex_tree regex_lang regex_diff thompson run_nfa eliminate orders growth backtrack
TESTS = test_regex test_thompson test_elimination test_backtrack
HEADERS = regex.h nfa.h dfa.h thompson.h gnfa.h backtrack.h words.h
.PHONY: all test bench clean
all: $(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%) $(BUILD)/matchers_bench
$(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(HEADERS) | $(BUILD)
$(CXX) $(CXXFLAGS) $< -o $@
# Las mediciones se compilan con -O2 y sin sanitizers, como el juez.
$(BUILD)/matchers_bench: matchers_bench.cpp $(HEADERS) | $(BUILD)
$(CXX) $(BENCHFLAGS) $< -o $@
$(BUILD):
mkdir -p $@
test: $(TESTS:%=$(BUILD)/%) $(PROGRAMS:%=$(BUILD)/%)
@for t in $(TESTS); do $(BUILD)/$$t || exit 1; done
@echo "Todas las pruebas pasaron."
bench: $(BUILD)/matchers_bench
$(BUILD)/matchers_bench
clean:
rm -rf $(BUILD)