Semana 1 — Lenguajes y autómatas finitos
Objetivos
- Expresar un problema de decisión como un lenguaje: el conjunto de las entradas con respuesta sí.
- Definir un DFA como quíntupla, seguir su ejecución con una cadena y decir qué lenguaje reconoce.
- Diseñar un DFA pensando en qué necesita recordar, y demostrar que reconoce el lenguaje pedido.
- Combinar dos DFA con la construcción del producto.
Sesión A — Presentación · Cadenas, lenguajes y problemas de decisión
Lectura: Apuntes, semana 1.
Apoyo: Sipser, capítulo 0, la parte sobre cadenas y lenguajes. Erickson, Models of Computation, nota 1 (Strings).
Temas:
- Las tres preguntas del curso: qué es calcular, qué no se puede calcular y qué cuesta demasiado. El mapa de las cuatro partes.
- Alfabeto, cadena, longitud, concatenación, cadena vacía . Prefijo, sufijo y subcadena.
- Lenguaje: un conjunto de cadenas, casi siempre infinito. , y no son lo mismo.
- Operaciones sobre lenguajes: unión, intersección, complemento, concatenación y estrella.
- De problema a lenguaje: “¿es primo?” es el lenguaje de las representaciones de los primos. Por qué basta estudiar problemas de decisión.
- Inducción sobre la longitud de una cadena, con un ejemplo corto: .
- Hay más lenguajes que programas: un argumento de conteo, sin formalizar todavía. Vuelve en la semana 9.
- Error común: confundir , la cadena sin símbolos, con , el lenguaje sin cadenas.
Sesión B — Autómatas finitos deterministas · Construcción del producto
Lectura: Apuntes, semana 1.
Apoyo: Sipser, sec. 1.1 (Finite Automata). Erickson, Models of Computation, nota 3 (Finite-state automata).
Temas:
- Una máquina con memoria fija: la puerta automática, el torniquete, y un DFA que acepta las cadenas binarias con una cantidad par de unos.
- Definición formal: . El diagrama de estados y la tabla dicen lo mismo.
- La función de transición extendida y la definición de aceptar. .
- Diseñar un DFA: decidir qué hay que recordar, y que cada estado sea un hecho sobre lo leído. Ejemplos: termina en , contiene , múltiplos de 3 en binario.
- Demostrar que un DFA es correcto: una afirmación por estado, por inducción sobre la longitud.
- Lenguaje regular: el que algún DFA reconoce.
- Construcción del producto: correr dos DFA a la vez. Unión e intersección con la misma máquina y distinto . Complemento intercambiando .
- Error común: olvidar el estado trampa y dejar transiciones sin definir. En un DFA, es total.
Laboratorio — Un simulador de DFA
- Leer la descripción de un DFA y una lista de cadenas, y responder por cada una si la acepta.
- Representar el autómata con los cinco componentes de la definición, con los mismos nombres.
- Pasar los casos de borde: la cadena vacía, un DFA sin estados de aceptación y uno que acepta todo.
- Escribir en el formato del curso los tres DFA diseñados en clase y comprobarlos con su simulador.
- Opcional: con la construcción del producto, producir el DFA de la intersección de dos DFA.
Preguntas de repaso
- ¿Cuántas cadenas tiene ? ¿Y ? ¿Qué es ?
- Den un DFA para las cadenas sobre que no contienen
aa. ¿Qué recuerda cada estado? - ¿Por qué un DFA con estados no puede “contar” hasta ? Den la intuición; la demostración llega en la semana 4.
- Si tiene 3 estados y tiene 4, ¿cuántos tiene el producto? ¿Todos son siempre alcanzables?
- Dado un DFA para , ¿cómo se obtiene uno para el complemento de ? ¿Qué falla si faltaba el estado trampa?
Código de la semana
Compilar y probar dentro del contenedor del curso con make y make test.
Ejemplos (14)Errores (3)Pruebas (3)Laboratorio (3)Compilación (1)
Ejemplos
Los programas que usan los apuntes y la clase.
// Complemento: complement A.dfa
// Escribe en formato .dfa la misma máquina con los estados de aceptación intercambiados.
#include <iostream>
#include <stdexcept>
#include "dfa.h"
int main(int argc, char** argv) {
if (argc != 2) {
std::cerr << "uso: complement A.dfa\n";
return 2;
}
try {
Dfa m = complement(load_dfa(argv[1]));
std::cout << "# Complemento de " << argv[1] << ".\n";
write_dfa(std::cout, m);
} 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.
#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// Operaciones sobre lenguajes con ejemplos finitos, y la diferencia entre ∅ y {ε}.
// De la estrella y del complemento se muestran solo las cadenas cortas.
#include <iostream>
#include <vector>
#include "languages.h"
int main() {
std::vector<char> binary = {'0', '1'};
Language a = {"0", "01"};
Language b = {"", "1", "01"};
Language empty = {};
Language only_eps = {""};
std::cout << "A = " << show(a) << " B = " << show(b) << "\n\n";
std::cout << "A ∪ B = " << show(unite(a, b)) << '\n';
std::cout << "A ∩ B = " << show(intersect(a, b)) << '\n';
std::cout << "AB = " << show(concat(a, b)) << '\n';
std::cout << "BA = " << show(concat(b, a)) << '\n';
std::cout << "A² = " << show(power(a, 2)) << '\n';
std::cout << "A*, hasta longitud 3: " << show(star_up_to(a, 3)) << '\n';
std::cout << "complemento de A, hasta longitud 2: " << show(complement_up_to(a, binary, 2)) << "\n\n";
std::cout << "|∅| = " << empty.size() << " |{ε}| = " << only_eps.size() << '\n';
std::cout << "∅A = " << show(concat(empty, a)) << '\n';
std::cout << "{ε}A = " << show(concat(only_eps, a)) << '\n';
std::cout << "∅ ∪ A = " << show(unite(empty, a)) << '\n';
std::cout << "∅* = " << show(star_up_to(empty, 3)) << '\n';
std::cout << "{ε}* = " << show(star_up_to(only_eps, 3)) << '\n';
std::cout << "∅⁰ = " << show(power(empty, 0)) << " ∅¹ = " << show(power(empty, 1)) << '\n';
}// Cadenas y lenguajes finitos, para comprobar con ejemplos pequeños las definiciones de la
// sesión A. Una cadena es un std::string y un lenguaje finito es un std::set<std::string>.
// Un lenguaje infinito no cabe en un set: de la estrella y del complemento solo se calcula la
// parte con cadenas de longitud acotada.
#ifndef LANGUAGES_H
#define LANGUAGES_H
#include <algorithm>
#include <cstddef>
#include <set>
#include <string>
#include <vector>
using Language = std::set<std::string>;
// 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;
}
inline Language prefixes(const std::string& w) {
Language result;
for (std::size_t len = 0; len <= w.size(); len++) {
result.insert(w.substr(0, len));
}
return result;
}
inline Language suffixes(const std::string& w) {
Language result;
for (std::size_t from = 0; from <= w.size(); from++) {
result.insert(w.substr(from));
}
return result;
}
inline Language substrings(const std::string& w) {
Language result;
for (std::size_t from = 0; from <= w.size(); from++) {
for (std::size_t len = 0; from + len <= w.size(); len++) {
result.insert(w.substr(from, len));
}
}
return result;
}
inline Language unite(const Language& a, const Language& b) {
Language result = a;
result.insert(b.begin(), b.end());
return result;
}
inline Language intersect(const Language& a, const Language& b) {
Language result;
for (const std::string& w : a) {
if (b.count(w) > 0) {
result.insert(w);
}
}
return result;
}
// AB = { uv : u ∈ A, v ∈ B }
inline Language concat(const Language& a, const Language& b) {
Language result;
for (const std::string& u : a) {
for (const std::string& v : b) {
result.insert(u + v);
}
}
return result;
}
// A^0 = {ε} y A^(k+1) = A^k A
inline Language power(const Language& a, int k) {
Language result = {""};
for (int i = 0; i < k; i++) {
result = concat(result, a);
}
return result;
}
// Las cadenas de A* con longitud a lo sumo max_len.
inline Language star_up_to(const Language& a, std::size_t max_len) {
Language result = {""};
std::vector<std::string> pending = {""};
while (!pending.empty()) {
std::string u = pending.back();
pending.pop_back();
for (const std::string& v : a) {
std::string w = u + v;
if (w.size() <= max_len && result.insert(w).second) {
pending.push_back(w);
}
}
}
return result;
}
// Las cadenas del complemento de A, respecto de Σ*, con longitud a lo sumo max_len.
inline Language complement_up_to(const Language& a, const std::vector<char>& alphabet, std::size_t max_len) {
Language result;
for (const std::string& w : all_strings(alphabet, max_len)) {
if (a.count(w) == 0) {
result.insert(w);
}
}
return result;
}
// Para imprimir: la cadena vacía se muestra como ε.
inline std::string show(const std::string& w) {
return w.empty() ? "ε" : w;
}
// Un lenguaje finito, con las cadenas más cortas primero. El lenguaje sin cadenas se muestra como ∅.
inline std::string show(const Language& a) {
std::vector<std::string> words(a.begin(), a.end());
std::stable_sort(words.begin(), words.end(),
[](const std::string& x, const std::string& y) { return x.size() < y.size(); });
if (a.empty()) {
return "∅";
}
std::string text = "{";
for (std::size_t i = 0; i < words.size(); i++) {
text += (i > 0 ? ", " : "") + show(words[i]);
}
return text + "}";
}
#endif// Construcción del producto: product (inter|union) A.dfa B.dfa
// Escribe en la salida estándar, en formato .dfa, el autómata que corre A y B a la vez.
// Con --alcanzables al final, deja solo los estados alcanzables desde el inicial.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include "dfa.h"
int main(int argc, char** argv) {
std::string mode = argc >= 2 ? argv[1] : "";
bool only_reachable = argc == 5 && std::string(argv[4]) == "--alcanzables";
if ((argc != 4 && !only_reachable) || (mode != "inter" && mode != "union")) {
std::cerr << "uso: product (inter|union) A.dfa B.dfa [--alcanzables]\n";
return 2;
}
try {
Dfa a = load_dfa(argv[2]);
Dfa b = load_dfa(argv[3]);
Dfa m = product(a, b, mode == "inter" ? Combine::Intersection : Combine::Union);
std::size_t total = m.states.size();
if (only_reachable) {
m = remove_unreachable(m);
}
std::cout << "# Producto de " << argv[2] << " y " << argv[3] << ": "
<< (mode == "inter" ? "intersección" : "unión") << ".\n";
std::cout << "# " << a.states.size() << " × " << b.states.size() << " = " << total << " estados";
if (only_reachable) {
std::cout << ", " << m.states.size() << " alcanzables";
}
std::cout << ".\n";
write_dfa(std::cout, m);
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Sigue un DFA con una o más cadenas: run_dfa ARCHIVO.dfa CADENA...
// Con - en lugar del archivo, lee la descripción de la entrada estándar.
// La cadena vacía se pasa como '' en la terminal.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include "dfa.h"
int main(int argc, char** argv) {
if (argc < 3) {
std::cerr << "uso: run_dfa ARCHIVO.dfa CADENA...\n";
return 2;
}
try {
std::string path = argv[1];
Dfa m = (path == "-") ? read_dfa(std::cin) : load_dfa(path);
for (int i = 2; i < argc; i++) {
std::string w = argv[i];
std::vector<std::string> sequence = run(m, w);
std::cout << "w = " << (w.empty() ? "ε" : w) << "\n " << sequence[0];
for (std::size_t k = 0; k < w.size(); k++) {
std::cout << " -" << w[k] << "-> " << sequence[k + 1];
}
const std::string& last = sequence.back();
bool ok = m.accept.count(last) > 0;
std::cout << "\n termina en " << last << (ok ? ", que está en F: acepta" : ", que no está en F: rechaza")
<< '\n';
}
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Muestra un DFA como quíntupla y como tabla de transiciones: show_dfa ARCHIVO.dfa
// En la tabla, -> marca el estado inicial y * los estados de aceptación.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include "dfa.h"
static std::string padded(const std::string& text, std::size_t width) {
return text + std::string(width > text.size() ? width - text.size() : 0, ' ');
}
int main(int argc, char** argv) {
if (argc != 2) {
std::cerr << "uso: show_dfa ARCHIVO.dfa\n";
return 2;
}
try {
Dfa m = load_dfa(argv[1]);
std::cout << "Q = {";
for (std::size_t i = 0; i < m.states.size(); i++) {
std::cout << (i > 0 ? ", " : "") << m.states[i];
}
std::cout << "}\nΣ = {";
for (std::size_t i = 0; i < m.alphabet.size(); i++) {
std::cout << (i > 0 ? ", " : "") << m.alphabet[i];
}
std::cout << "}\nq0 = " << m.start << "\nF = {";
bool first = true;
for (const std::string& state : m.states) {
if (m.accept.count(state) > 0) {
std::cout << (first ? "" : ", ") << state;
first = false;
}
}
std::cout << "}\n\n";
std::size_t width = 1;
for (const std::string& state : m.states) {
width = std::max(width, state.size());
}
// La última columna va sin relleno, para no dejar espacios al final de la línea.
std::cout << " " << padded("δ", width + 1); // δ ocupa dos bytes y una columna
for (std::size_t i = 0; i < m.alphabet.size(); i++) {
std::string symbol(1, m.alphabet[i]);
std::cout << " " << (i + 1 < m.alphabet.size() ? padded(symbol, width) : symbol);
}
std::cout << '\n';
for (const std::string& state : m.states) {
std::cout << (state == m.start ? "-> " : " ") << (m.accept.count(state) > 0 ? "* " : " ")
<< padded(state, width);
for (std::size_t i = 0; i < m.alphabet.size(); i++) {
const std::string& target = step(m, state, m.alphabet[i]);
std::cout << " " << (i + 1 < m.alphabet.size() ? padded(target, width) : target);
}
std::cout << '\n';
}
std::cout << "\nestados alcanzables desde " << m.start << ": " << reachable(m).size() << " de "
<< m.states.size() << '\n';
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Las definiciones sobre cadenas, con ejemplos: las primeras cadenas de Σ*, cuántas hay de cada
// longitud, y los prefijos, sufijos y subcadenas de una cadena.
// strings_demo [CADENA] (por defecto, abba)
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>
#include "languages.h"
int main(int argc, char** argv) {
std::vector<char> binary = {'0', '1'};
std::vector<std::string> first = all_strings(binary, 3);
std::cout << "Σ = {0, 1}. Las cadenas de Σ* con longitud a lo sumo 3, en orden:\n ";
for (const std::string& w : first) {
std::cout << ' ' << show(w);
}
std::cout << "\n\n";
std::cout << " n cadenas de longitud n cadenas de longitud ≤ n\n";
std::size_t before = 0;
for (std::size_t n = 0; n <= 10; n++) {
std::size_t upto = all_strings(binary, n).size();
std::cout.width(2);
std::cout << n;
std::cout.width(18);
std::cout << upto - before;
std::cout.width(25);
std::cout << upto << '\n';
before = upto;
}
std::string w = argc > 1 ? argv[1] : "abba";
std::cout << "\nw = " << show(w) << ", |w| = " << w.size() << '\n';
Language p = prefixes(w);
Language s = suffixes(w);
Language sub = substrings(w);
std::cout << "prefijos (" << p.size() << "): " << show(p) << '\n';
std::cout << "sufijos (" << s.size() << "): " << show(s) << '\n';
std::cout << "subcadenas (" << sub.size() << "): " << show(sub) << '\n';
}# Cadenas binarias que contienen 101 como subcadena.
# q0, q1, q2: todavía no apareció 101, y lo leído termina con 0, 1 o 2 símbolos de 101 ya avanzados.
# q3: ya apareció 101.
states: q0 q1 q2 q3
alphabet: 0 1
start: q0
accept: q3
delta:
q0 0 q0
q0 1 q1
q1 0 q2
q1 1 q1
q2 0 q0
q2 1 q3
q3 0 q3
q3 1 q3# 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 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 empiezan con 1. El estado trampa recoge las que empiezan con 0.
states: q0 q1 trampa
alphabet: 0 1
start: q0
accept: q1
delta:
q0 0 trampa
q0 1 q1
q1 0 q1
q1 1 q1
trampa 0 trampa
trampa 1 trampa# Un torniquete. Símbolos: m, entra una moneda; e, alguien empuja.
# Acepta las secuencias que lo dejan bloqueado.
states: bloqueado libre
alphabet: m e
start: bloqueado
accept: bloqueado
delta:
bloqueado m libre
bloqueado e bloqueado
libre m libre
libre e bloqueadoErrores
Ejemplos con errores a propósito: no compilan, fallan o dan un resultado incorrecto. Los apuntes explican cada uno.
# Error: "empieza con 1" sin estado trampa. Falta δ(q0, 0), así que δ no es una función total
# y esto no es un DFA.
states: q0 q1
alphabet: 0 1
start: q0
accept: q1
delta:
q0 1 q1
q1 0 q1
q1 1 q1# Error: dos transiciones para el mismo estado y el mismo símbolo. Un DFA tiene exactamente una.
# (Una máquina así es un NFA, el tema de la semana 2.)
states: q0 q1 q2
alphabet: 0 1
start: q0
accept: q2
delta:
q0 0 q0
q0 0 q1
q0 1 q0
q1 0 q1
q1 1 q2
q2 0 q1
q2 1 q0# Error: una transición va a un estado que no está en states.
states: par impar
alphabet: 0 1
start: par
accept: par
delta:
par 0 par
par 1 impar
impar 0 impar
impar 1 paresPruebas
Comprueban lo que afirman los apuntes; se ejecutan con make test.
// Pruebas de lo que los apuntes afirman sobre los DFA del capítulo (sesión B).
// Cada autómata de machines/ se compara con una función de C++ que decide el mismo lenguaje
// mirando la cadena completa, sobre todas las cadenas de longitud a lo sumo 12.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <functional>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
#include "dfa.h"
#include "languages.h"
static 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;
}
static bool contains(const std::string& w, const std::string& piece) {
return w.find(piece) != std::string::npos;
}
static int count_ones(const std::string& w) {
int ones = 0;
for (char c : w) {
ones += (c == '1');
}
return ones;
}
// El valor de w como número en base 2. La cadena vacía vale 0.
static unsigned long binary_value(const std::string& w) {
return w.empty() ? 0 : std::stoul(w, nullptr, 2);
}
// Cuántas cadenas de longitud a lo sumo 12 se revisaron con cada máquina.
static std::size_t check_language(const std::string& path, const std::vector<char>& alphabet,
const std::function<bool(const std::string&)>& in_language) {
Dfa m = load_dfa(path);
std::vector<std::string> words = all_strings(alphabet, 12);
for (const std::string& w : words) {
assert(accepts(m, w) == in_language(w));
}
return words.size();
}
static std::size_t test_languages_of_machines() {
std::vector<char> binary = {'0', '1'};
std::size_t n = 0;
n = check_language("machines/even_ones.dfa", binary, [](const std::string& w) { return count_ones(w) % 2 == 0; });
n = check_language("machines/ends_01.dfa", binary, [](const std::string& w) { return ends_with(w, "01"); });
n = check_language("machines/contains_101.dfa", binary, [](const std::string& w) { return contains(w, "101"); });
n = check_language("machines/multiple_of_3.dfa", binary,
[](const std::string& w) { return binary_value(w) % 3 == 0; });
n = check_language("machines/starts_with_1.dfa", binary,
[](const std::string& w) { return !w.empty() && w[0] == '1'; });
// El torniquete queda bloqueado si no pasó nada o si lo último fue un empujón.
n = check_language("machines/turnstile.dfa", {'m', 'e'},
[](const std::string& w) { return w.empty() || w.back() == 'e'; });
return n;
}
// La afirmación de cada estado: en qué estado queda la máquina dice un hecho sobre lo leído.
static void test_state_claims() {
std::vector<std::string> words = all_strings({'0', '1'}, 12);
Dfa even = load_dfa("machines/even_ones.dfa");
for (const std::string& w : words) {
assert(delta_star(even, even.start, w) == (count_ones(w) % 2 == 0 ? "par" : "impar"));
}
Dfa ends = load_dfa("machines/ends_01.dfa");
for (const std::string& w : words) {
std::string expected = ends_with(w, "01") ? "q2" : ends_with(w, "0") ? "q1" : "q0";
assert(delta_star(ends, ends.start, w) == expected);
}
Dfa has = load_dfa("machines/contains_101.dfa");
for (const std::string& w : words) {
std::string expected = contains(w, "101") ? "q3" : ends_with(w, "10") ? "q2" : ends_with(w, "1") ? "q1" : "q0";
assert(delta_star(has, has.start, w) == expected);
}
Dfa three = load_dfa("machines/multiple_of_3.dfa");
for (const std::string& w : words) {
assert(delta_star(three, three.start, w) == "r" + std::to_string(binary_value(w) % 3));
}
// val(wb) = 2·val(w) + b, la cuenta de la que sale δ.
for (const std::string& w : all_strings({'0', '1'}, 10)) {
assert(binary_value(w + "0") == 2 * binary_value(w));
assert(binary_value(w + "1") == 2 * binary_value(w) + 1);
}
}
// Las trazas que los apuntes muestran.
static void test_traces() {
Dfa even = load_dfa("machines/even_ones.dfa");
assert(run(even, "1101") == (std::vector<std::string>{"par", "impar", "par", "par", "impar"}));
assert(run(even, "") == (std::vector<std::string>{"par"}));
assert(!accepts(even, "1101") && accepts(even, "") && accepts(even, "0110"));
Dfa ends = load_dfa("machines/ends_01.dfa");
assert(run(ends, "110101") == (std::vector<std::string>{"q0", "q0", "q0", "q1", "q2", "q1", "q2"}));
assert(accepts(ends, "01") && !accepts(ends, "1") && !accepts(ends, "") && !accepts(ends, "010"));
Dfa has = load_dfa("machines/contains_101.dfa");
assert(run(has, "1100101") ==
(std::vector<std::string>{"q0", "q1", "q1", "q2", "q0", "q1", "q2", "q3"}));
assert(run(has, "11011") == (std::vector<std::string>{"q0", "q1", "q1", "q2", "q3", "q3"}));
assert(!accepts(has, "110011"));
Dfa three = load_dfa("machines/multiple_of_3.dfa");
assert(run(three, "10101") == (std::vector<std::string>{"r0", "r1", "r2", "r2", "r1", "r0"})); // 21
assert(run(three, "1101") == (std::vector<std::string>{"r0", "r1", "r0", "r0", "r1"})); // 13
assert(accepts(three, "") && accepts(three, "0") && accepts(three, "0011") && !accepts(three, "0100"));
Dfa turnstile = load_dfa("machines/turnstile.dfa");
assert(run(turnstile, "emme") ==
(std::vector<std::string>{"bloqueado", "bloqueado", "libre", "libre", "bloqueado"}));
}
// δ*(q, uv) = δ*(δ*(q, u), v), para todo estado y todas las cadenas cortas.
static void test_delta_star() {
Dfa has = load_dfa("machines/contains_101.dfa");
std::vector<std::string> words = all_strings({'0', '1'}, 5);
for (const std::string& q : has.states) {
assert(delta_star(has, q, "") == q);
for (const std::string& u : words) {
for (const std::string& v : words) {
assert(delta_star(has, q, u + v) == delta_star(has, delta_star(has, q, u), v));
}
}
}
// La secuencia de estados termina en δ*(q0, w) y tiene |w| + 1 estados.
for (const std::string& w : words) {
std::vector<std::string> sequence = run(has, w);
assert(sequence.size() == w.size() + 1);
assert(sequence.back() == delta_star(has, has.start, w));
}
}
static bool fails_with(const std::string& path, const std::string& piece) {
try {
load_dfa(path);
} catch (const std::runtime_error& error) {
return std::string(error.what()).find(piece) != std::string::npos;
}
return false;
}
static void test_reader() {
// Lo que no es un DFA no se carga.
assert(fails_with("errors/missing_trap.dfa", "falta la transición δ(q0, 0)"));
assert(fails_with("errors/two_transitions.dfa", "transición repetida para δ(q0, 0)"));
assert(fails_with("errors/unknown_state.dfa", "pares"));
assert(fails_with("machines/no_existe.dfa", "no se pudo abrir"));
// Lo que write_dfa escribe, read_dfa lo lee igual.
for (const char* path : {"machines/even_ones.dfa", "machines/ends_01.dfa", "machines/contains_101.dfa",
"machines/multiple_of_3.dfa", "machines/starts_with_1.dfa", "machines/turnstile.dfa"}) {
Dfa m = load_dfa(path);
std::stringstream text;
write_dfa(text, m);
Dfa again = read_dfa(text);
assert(again.states == m.states && again.alphabet == m.alphabet && again.delta == m.delta);
assert(again.start == m.start && again.accept == m.accept);
assert(m.delta.size() == m.states.size() * m.alphabet.size()); // δ es total
assert(reachable(m).size() == m.states.size()); // en estos seis, todo estado se alcanza
}
// accept: puede quedar vacío. Con F = ∅ no se acepta nada, y con F = Q se acepta todo.
std::istringstream nothing("states: a b\nalphabet: 0 1\nstart: a\naccept:\ndelta:\na 0 b\na 1 a\nb 0 a\nb 1 b\n");
Dfa none = read_dfa(nothing);
Dfa all = none;
all.accept = {"a", "b"};
for (const std::string& w : all_strings({'0', '1'}, 8)) {
assert(!accepts(none, w) && accepts(all, w));
}
}
int main() {
std::size_t n = test_languages_of_machines();
test_state_claims();
test_traces();
test_delta_star();
test_reader();
std::printf("test_dfa: ok (6 autómatas, %zu cadenas cada uno)\n", n);
}// Pruebas de lo que los apuntes afirman sobre cadenas y lenguajes (sesión A).
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <string>
#include <vector>
#include "languages.h"
static void test_sigma_star() {
std::vector<char> binary = {'0', '1'};
// Hay 2^n cadenas binarias de longitud n, y 2^(n+1) - 1 de longitud a lo sumo n.
for (std::size_t n = 0; n <= 12; n++) {
std::vector<std::string> words = all_strings(binary, n);
assert(words.size() == (std::size_t{1} << (n + 1)) - 1);
std::size_t exact = 0;
for (const std::string& w : words) {
exact += (w.size() == n);
}
assert(exact == std::size_t{1} << n);
}
// El orden: primero las más cortas, y cada cadena aparece una sola vez.
std::vector<std::string> first = all_strings(binary, 3);
std::vector<std::string> expected = {"", "0", "1", "00", "01", "10", "11", "000",
"001", "010", "011", "100", "101", "110", "111"};
assert(first == expected);
// Con tres símbolos: 1 + 3 + 9 + 27 = 40.
assert(all_strings({'a', 'b', 'c'}, 3).size() == 40);
}
static void test_concatenation() {
std::vector<std::string> words = all_strings({'a', 'b'}, 4);
for (const std::string& u : words) {
assert(u + "" == u && "" + u == u); // ε es el neutro
for (const std::string& v : words) {
assert((u + v).size() == u.size() + v.size()); // |uv| = |u| + |v|
}
}
assert(std::string("ab") + "ba" != std::string("ba") + "ab"); // no es conmutativa
for (const std::string& u : all_strings({'a', 'b'}, 2)) {
for (const std::string& v : all_strings({'a', 'b'}, 2)) {
for (const std::string& w : all_strings({'a', 'b'}, 2)) {
assert((u + v) + w == u + (v + w)); // es asociativa
}
}
}
}
static void test_parts() {
// El ejemplo de los apuntes.
std::string w = "abba";
assert(prefixes(w) == (Language{"", "a", "ab", "abb", "abba"}));
assert(suffixes(w) == (Language{"", "a", "ba", "bba", "abba"}));
assert(substrings(w) == (Language{"", "a", "b", "ab", "bb", "ba", "abb", "bba", "abba"}));
// Una cadena de longitud n tiene n + 1 prefijos y n + 1 sufijos; ε y w están entre ellos.
// Todo prefijo y todo sufijo es una subcadena.
for (const std::string& x : all_strings({'a', 'b'}, 7)) {
Language p = prefixes(x);
Language s = suffixes(x);
Language sub = substrings(x);
assert(p.size() == x.size() + 1 && s.size() == x.size() + 1);
assert(p.count("") == 1 && p.count(x) == 1 && s.count("") == 1 && s.count(x) == 1);
assert(unite(unite(p, s), sub) == sub);
assert(sub.size() <= x.size() * (x.size() + 1) / 2 + 1);
}
// Con todos los símbolos distintos se alcanza el máximo: n(n + 1)/2 + 1.
assert(substrings("abcd").size() == 11);
assert(substrings("aaaa").size() == 5);
}
static void test_language_operations() {
Language a = {"0", "01"};
Language b = {"", "1", "01"};
Language empty = {};
Language only_eps = {""};
// Los valores que imprime languages_demo y que los apuntes copian.
assert(unite(a, b) == (Language{"", "0", "1", "01"}));
assert(intersect(a, b) == (Language{"01"}));
assert(concat(a, b) == (Language{"0", "01", "001", "011", "0101"}));
assert(concat(b, a) == (Language{"0", "01", "10", "101", "010", "0101"}));
assert(concat(a, b) != concat(b, a));
assert(concat(a, b).size() == 5); // menos de 2 × 3: 0·1 y 01·ε dan la misma cadena
assert(power(a, 2) == (Language{"00", "001", "010", "0101"}));
assert(star_up_to(a, 3) == (Language{"", "0", "00", "01", "000", "001", "010"}));
assert(complement_up_to(a, {'0', '1'}, 2) == (Language{"", "1", "00", "10", "11"}));
// ∅ y {ε} no son lo mismo.
assert(empty.size() == 0 && only_eps.size() == 1 && empty != only_eps);
assert(concat(empty, a) == empty && concat(a, empty) == empty);
assert(concat(only_eps, a) == a && concat(a, only_eps) == a);
assert(unite(empty, a) == a);
assert(star_up_to(empty, 5) == only_eps);
assert(star_up_to(only_eps, 5) == only_eps);
assert(power(empty, 0) == only_eps && power(empty, 1) == empty);
// A* es la unión de las potencias, tiene a ε, y (A*)* = A*.
Language powers;
for (int k = 0; k <= 6; k++) {
for (const std::string& w : power(a, k)) {
if (w.size() <= 6) {
powers.insert(w);
}
}
}
Language star = star_up_to(a, 6);
assert(star == powers);
assert(star.count("") == 1);
assert(star_up_to(star, 6) == star);
// {0, 1}* son todas las cadenas binarias.
assert(star_up_to({"0", "1"}, 6).size() == 127);
// De Morgan, mirando las cadenas de longitud a lo sumo 4.
std::vector<char> binary = {'0', '1'};
Language left = complement_up_to(unite(a, b), binary, 4);
Language right = intersect(complement_up_to(a, binary, 4), complement_up_to(b, binary, 4));
assert(left == right);
}
int main() {
test_sigma_star();
test_concatenation();
test_parts();
test_language_operations();
std::printf("test_languages: ok\n");
}// Pruebas de la construcción del producto y del complemento.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <stdexcept>
#include <string>
#include <vector>
#include "dfa.h"
#include "languages.h"
// ¿M1 y M2 aceptan las mismas cadenas de longitud a lo sumo max_len?
static bool same_up_to(const Dfa& m1, const Dfa& m2, std::size_t max_len) {
for (const std::string& w : all_strings(m1.alphabet, max_len)) {
if (accepts(m1, w) != accepts(m2, w)) {
return false;
}
}
return true;
}
static void test_product_of_notes() {
Dfa even = load_dfa("machines/even_ones.dfa");
Dfa ends = load_dfa("machines/ends_01.dfa");
Dfa both = product(even, ends, Combine::Intersection);
Dfa either = product(even, ends, Combine::Union);
// 2 × 3 = 6 estados, y en este producto los 6 se alcanzan.
assert(both.states.size() == 6 && either.states.size() == 6);
assert(reachable(both).size() == 6);
// La misma máquina con distinto F.
assert(both.states == either.states && both.delta == either.delta && both.start == either.start);
assert(both.start == "(par,q0)");
assert(both.accept == (std::set<std::string>{"(par,q2)"}));
assert(either.accept == (std::set<std::string>{"(par,q0)", "(par,q1)", "(par,q2)", "(impar,q2)"}));
// El lema: δ*((p, q), w) = (δ1*(p, w), δ2*(q, w)), desde cualquier par.
for (const std::string& p : even.states) {
for (const std::string& q : ends.states) {
for (const std::string& w : all_strings({'0', '1'}, 7)) {
assert(delta_star(both, pair_name(p, q), w) ==
pair_name(delta_star(even, p, w), delta_star(ends, q, w)));
}
}
}
// Y lo que importa: reconoce la intersección y la unión.
for (const std::string& w : all_strings({'0', '1'}, 12)) {
assert(accepts(both, w) == (accepts(even, w) && accepts(ends, w)));
assert(accepts(either, w) == (accepts(even, w) || accepts(ends, w)));
}
// La traza de los apuntes.
assert(run(both, "1101") ==
(std::vector<std::string>{"(par,q0)", "(impar,q0)", "(par,q0)", "(par,q1)", "(impar,q2)"}));
assert(!accepts(both, "1101") && accepts(either, "1101"));
assert(accepts(both, "1001") && accepts(both, "0101") && !accepts(both, "001"));
}
static void test_complement() {
for (const char* path : {"machines/even_ones.dfa", "machines/ends_01.dfa", "machines/contains_101.dfa",
"machines/multiple_of_3.dfa", "machines/starts_with_1.dfa"}) {
Dfa m = load_dfa(path);
Dfa c = complement(m);
assert(c.accept.size() + m.accept.size() == m.states.size());
for (const std::string& w : all_strings({'0', '1'}, 12)) {
assert(accepts(c, w) != accepts(m, w));
}
assert(complement(c).accept == m.accept);
}
// De Morgan con máquinas: A ∪ B es el complemento de (complemento de A) ∩ (complemento de B).
Dfa a = load_dfa("machines/contains_101.dfa");
Dfa b = load_dfa("machines/multiple_of_3.dfa");
Dfa left = product(a, b, Combine::Union);
Dfa right = complement(product(complement(a), complement(b), Combine::Intersection));
assert(left.accept == right.accept); // no solo el mismo lenguaje: el mismo F
assert(same_up_to(left, right, 12));
}
// Cuántos estados del producto se alcanzan, en los ejemplos de los apuntes.
static void test_reachable() {
Dfa even = load_dfa("machines/even_ones.dfa");
Dfa ends = load_dfa("machines/ends_01.dfa");
Dfa has = load_dfa("machines/contains_101.dfa");
Dfa three = load_dfa("machines/multiple_of_3.dfa");
// Una máquina consigo misma: solo se alcanzan los pares (q, q).
Dfa twice = product(even, even, Combine::Intersection);
assert(twice.states.size() == 4 && reachable(twice).size() == 2);
assert(same_up_to(twice, even, 12));
Dfa trimmed = remove_unreachable(twice);
assert(trimmed.states.size() == 2 && same_up_to(trimmed, even, 12));
// 3 × 4 = 12 estados, de los que se alcanzan 8.
Dfa twelve = product(ends, has, Combine::Intersection);
assert(twelve.states.size() == 12);
assert(reachable(twelve).size() == 8);
assert(same_up_to(remove_unreachable(twelve), twelve, 12));
// Tres propiedades a la vez: el producto de un producto. 4 × 3 × 2 = 24.
Dfa triple = product(product(has, three, Combine::Intersection), even, Combine::Intersection);
assert(triple.states.size() == 24);
assert(reachable(triple).size() == 24);
for (const std::string& w : all_strings({'0', '1'}, 12)) {
assert(accepts(triple, w) == (accepts(has, w) && accepts(three, w) && accepts(even, w)));
}
}
static void test_alphabets() {
Dfa even = load_dfa("machines/even_ones.dfa");
Dfa turnstile = load_dfa("machines/turnstile.dfa");
bool failed = false;
try {
product(even, turnstile, Combine::Union);
} catch (const std::runtime_error&) {
failed = true;
}
assert(failed);
}
int main() {
test_product_of_notes();
test_complement();
test_reachable();
test_alphabets();
std::printf("test_product: ok\n");
}Laboratorio
Archivos de partida del laboratorio de la semana.
TIEMPO = 2
include ../../../lab.mk# Un simulador de DFA
El primer programa del curso es el que van a usar todo el semestre para probar sus autómatas: recibe la
descripción de un autómata finito determinista (DFA) y una lista de cadenas, y dice por cada cadena si el
autómata la acepta.
Un DFA es $M = (Q, \Sigma, \delta, q_0, F)$. Acepta una cadena $w$ si, empezando en $q_0$ y siguiendo $\delta$
con cada símbolo de $w$, de izquierda a derecha, termina en un estado de $F$.
## Entrada
La descripción de un DFA en el formato `.dfa` de [`code/formats.md`](../../../formats.md), seguida del bloque
de cadenas del mismo documento:
```text
# 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
strings: 3
0110
111
```
- Una línea que empieza con `#` es un comentario. Puede haber comentarios en cualquier línea anterior a
`strings:`, también entre las transiciones.
- Puede haber líneas vacías antes de `delta:`. Entre `delta:` y `strings:` no hay líneas vacías.
- `states:`, `alphabet:`, `start:`, `accept:` y `delta:` vienen siempre en ese orden. `accept:` puede no
tener ningún estado.
- Después de `delta:` hay exactamente una línea `estado símbolo destino` por cada par de estado y símbolo, en
cualquier orden.
- `strings: k` dice cuántas cadenas siguen, una por línea. **Una línea vacía es la cadena vacía
$\varepsilon$.** Después de `strings:` ya no hay comentarios.
## Salida
Una línea por cada cadena, en el mismo orden: `acepta` si el autómata la acepta y `rechaza` si no.
## Límites
- $1 \leq |Q| \leq 2000$ y $1 \leq |\Sigma| \leq 26$.
- 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 (`q1` y `q10`), y puede ser igual a un símbolo (un estado `0` y
un símbolo `0`).
- Un símbolo es un solo carácter visible, distinto de `#`.
- $1 \leq k \leq 100\,000$. Las longitudes de las cadenas suman a lo sumo 1 000 000.
- Todas las cadenas están formadas solo por símbolos del alfabeto.
- La entrada siempre describe un DFA válido: no tienen que detectar errores en la descripción.
## Ejemplo
Para la entrada de arriba, la salida es:
```text
acepta
acepta
rechaza
```
`0110` tiene dos unos. La segunda cadena es la vacía, que tiene cero unos, y cero es par. `111` tiene tres.
## Tiempo
2 segundos por caso. Se compila con `g++ -Wall -Wextra -std=c++20 -O2`.
Con los límites de arriba, $\delta$ puede tener 52 000 transiciones y hay que seguir hasta 1 000 000 de símbolos.
Si por cada símbolo recorren la lista de transiciones hasta encontrar la que toca, son demasiadas
comparaciones y el juez da `TLE`. Guarden $\delta$ de modo que seguir una transición no dependa de cuántas hay: una
tabla indexada por el número del estado y el del símbolo, o un `std::map`.
## Qué se practica aquí
En `code/week-01/dfa.h` ya hay un `struct Dfa` y una función que lee un archivo `.dfa` y lo ejecuta: es lo
que usan los ejemplos de los apuntes, y pueden leerlo cuanto quieran. Simular un DFA son tres líneas, y no es
lo difícil de este laboratorio. El trabajo está en **leer el formato sin tropezar** y en **los casos de
borde**, y por eso `solution.cpp` se escribe **sin incluir `dfa.h`**: el juez compila ese único archivo, y el
lector de `dfa.h` no entiende el bloque `strings:`.
Los casos traen, entre otros: la cadena vacía (también como última línea de la entrada), un DFA sin estados
de aceptación, uno que acepta todo, estados inalcanzables, comentarios entre las transiciones, transiciones
desordenadas, nombres que son prefijo de otros y nombres iguales a los símbolos.
## Cómo avanzar
```sh
make # compila solution.cpp en build/
make test # corre el juez con todos los casos
```
Los tres casos grandes no están guardados: `make test` los genera con los programas `casos/gen_NN.cpp`.
1. Lean la descripción y las cadenas, y respondan por cada una. Empiecen con `casos/01.in`. Lean por líneas,
con `std::getline`: `>>` se salta las líneas vacías, y aquí una línea vacía es una cadena.
2. Representen el autómata con los cinco componentes de la definición, con los mismos nombres: `states`,
`alphabet`, `delta`, `start` y `accept`. El esqueleto trae un `struct Dfa` con una propuesta de tipos.
3. Pasen los casos de borde. Antes de correr el juez, respondan a mano: ¿qué responde un DFA sin estados de
aceptación con la cadena vacía? ¿Y uno con un solo estado, que es de aceptación?
4. Prueben con su simulador los DFA de la clase, que están en `../../machines/`. A un archivo `.dfa` le falta
solo el bloque de cadenas:
```sh
{ cat ../../machines/ends_01.dfa; printf 'strings: 3\n01\n\n110\n'; } | build/solution
```
Debe imprimir `acepta`, `rechaza`, `rechaza`. Después escriban ustedes, en el mismo formato, un DFA de los
ejercicios de los apuntes (por ejemplo, las cadenas sobre $\{\mathtt{a}, \mathtt{b}\}$ que no contienen `aa`) y pruébenlo con
cadenas que hayan resuelto antes a mano.
Mientras desarrollan, compilen con sanitizers, como explica [`labs/README.md`](../../../../labs/README.md).
## Para seguir
Opcional, sin casos en el juez. Escriban un segundo programa que lea **dos** DFA con el mismo alfabeto, uno
después del otro, y escriba en formato `.dfa` el autómata de la construcción del producto que reconoce la
**intersección** de sus lenguajes: sus estados son los pares $(p, q)$, y con cada símbolo avanza en los dos a
la vez.
- El nombre de un estado no puede llevar espacios: `(par,q0)` sirve.
- Para comprobarlo, pásenle la salida a su simulador con algunas cadenas y comparen con lo que responden los
dos autómatas por separado. El caso `casos/10.in` es un producto escrito así.
- ¿Cuántos estados tiene el resultado si los autómatas tienen 3 y 4 estados? Agreguen una opción para
escribir solo los estados a los que se llega desde el inicial, y cuenten otra vez.
- Cambien solo los estados de aceptación para obtener la **unión**.// Un simulador de DFA. Lee la descripción de un autómata y una lista de cadenas, e imprime
// por cada cadena si el autómata la acepta.
#include <iostream>
#include <string>
#include <vector>
// Los cinco componentes de M = (Q, Σ, δ, q0, F), con los nombres del formato.
// Los tipos son una propuesta: cada estado y cada símbolo se guarda por su posición en la
// lista, para que seguir una transición no dependa de buscar un nombre. Pueden cambiarlos.
struct Dfa {
std::vector<std::string> states; // Q: los nombres, en el orden de la entrada
std::vector<char> alphabet; // Σ
std::vector<std::vector<int>> delta; // δ: delta[i][j] es el estado al que va states[i] con alphabet[j]
int start = 0; // q0, como posición en states
std::vector<bool> accept; // F: accept[i] dice si states[i] es de aceptación
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Dfa m;
std::string line;
// Por hacer: leer la descripción línea por línea con std::getline, hasta la línea strings:.
// Después, leer las cadenas (una línea vacía es ε) y responder por cada una.
while (std::getline(std::cin, line)) {
}
// Este esqueleto no imprime nada, así que el juez da WA en todos los casos.
return static_cast<int>(m.states.size());
}Compilación
Cómo se compilan y ejecutan los ejemplos.
# Semana 1: cadenas, lenguajes y autómatas finitos deterministas.
# 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/dfa_sim 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 = strings_demo languages_demo show_dfa run_dfa product complement
TESTS = test_languages test_dfa test_product
HEADERS = languages.h dfa.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)