Semana 6 — Autómatas de pila y los límites de las gramáticas
Objetivos
- Definir un autómata de pila y diseñar uno para un lenguaje libre de contexto.
- Explicar por qué las gramáticas y los autómatas de pila reconocen los mismos lenguajes.
- Demostrar que un lenguaje no es libre de contexto con su lema de bombeo.
- Decir bajo qué operaciones son cerrados los lenguajes libres de contexto y bajo cuáles no.
Sesión A — Autómatas de pila · Equivalencia con las gramáticas
Lectura: Apuntes, semana 6.
Apoyo: Sipser, sec. 2.2 (Pushdown Automata).
Temas:
- Un NFA con una pila: memoria sin límite, pero solo se ve la cima.
- Definición formal: , con transiciones “leer , sacar , poner ”, donde cada uno puede ser .
- Ejemplos: , palíndromos de longitud par (el autómata adivina la mitad), paréntesis balanceados.
- Marcar el fondo de la pila con un símbolo especial.
- De gramática a PDA: la pila guarda lo que falta derivar. Se hace completo, con un ejemplo.
- De PDA a gramática: la idea de las variables , “ir de a dejando la pila como estaba”. Se explica la idea y se muestra un ejemplo pequeño; la demostración queda en los apuntes.
- Todo lenguaje regular es libre de contexto.
- El PDA determinista reconoce menos: los palíndromos necesitan adivinar. Aquí el no determinismo sí agrega poder, a diferencia de los autómatas finitos.
- Error común: usar la pila como un contador de dos cosas a la vez. Una pila compara una sola pareja.
Sesión B — Lema de bombeo para lenguajes libres de contexto · ✂️ Cómo trabaja un parser real
Lectura: Apuntes, semana 6.
Apoyo: Sipser, sec. 2.3 (Non-Context-Free Languages). Para la parte ✂️, sec. 2.4 (Deterministic Context-Free Languages), solo como consulta.
Temas:
- Un lenguaje que pide comparar tres cosas: .
- La idea: en un árbol de derivación muy alto, alguna variable se repite en un camino, y ese tramo se puede repetir.
- Enunciado: , con , y . Demostración con el árbol.
- Ejemplos: , , . El análisis por casos según dónde caen e .
- Cierre: unión, concatenación y estrella sí. Intersección y complemento no, con como contraejemplo. La intersección con un lenguaje regular sí.
- El mapa hasta ahora: regulares libres de contexto, con un lenguaje que separa cada nivel.
- ✂️ Cómo trabaja un parser real: lexer con expresiones regulares, parser descendente recursivo para una gramática sin ambigüedad, tiempo lineal. La conexión con el intérprete de Introducción a la Programación.
- Error común: en el lema de bombeo, olvidar el caso en que o abarca dos tipos de símbolos.
Laboratorio — Práctica 2 · Opcional: un simulador de PDA
La sesión es para la Práctica 2 (semanas 4 y 5). Como ejercicio opcional:
- Leer la descripción de un PDA y una lista de cadenas, y decir cuáles acepta.
- Explorar las configuraciones (estado, posición, pila) con una búsqueda, porque el PDA es no determinista.
- Respetar el límite de configuraciones del enunciado, para los autómatas con ciclos de transiciones .
- Escribir el PDA de los palíndromos de longitud par y probarlo.
Preguntas de repaso
- Diseñen un PDA para . ¿Dónde usa el no determinismo?
- Conviertan la gramática en un PDA con la construcción de la clase y síganlo con
aabb. - Demuestren que no es libre de contexto.
- Con y , muestren que los lenguajes libres de contexto no son cerrados bajo intersección.
- Ubiquen en el mapa: , , , , . ¿Cuáles son regulares, cuáles libres de contexto y cuáles ninguno?
Código de la semana
Compilar y probar dentro del contenedor del curso con make y make test.
Ejemplos (31)Errores (2)Pruebas (4)Laboratorio (3)Compilación (1)
Ejemplos
Los programas que usan los apuntes y la clase.
// Las cadenas que genera una gramática, hasta una longitud: cfg_strings ARCHIVO.cfg N
#include <cstddef>
#include <iostream>
#include <set>
#include <stdexcept>
#include <string>
#include <vector>
#include "cfg.h"
#include "pda.h"
int main(int argc, char** argv) {
if (argc != 3) {
std::cerr << "uso: cfg_strings ARCHIVO.cfg N\n";
return 2;
}
try {
Cfg g = load_cfg(argv[1]);
std::size_t n = std::stoul(argv[2]);
std::set<std::string> language = strings_up_to(g, n);
std::cout << language.size() << " cadenas de longitud a lo sumo " << n << ":\n ";
// En el orden de siempre: primero las más cortas.
for (const std::string& w : all_strings(g.terminals, n)) {
if (language.count(w) > 0) {
std::cout << ' ' << (w.empty() ? "ε" : w);
}
}
std::cout << '\n';
} catch (const std::exception& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// De gramática a PDA: cfg_to_pda ARCHIVO.cfg
// Escribe en formato .pda el autómata de la construcción de la clase.
#include <iostream>
#include <stdexcept>
#include <string>
#include "cfg.h"
#include "convert.h"
#include "pda.h"
int main(int argc, char** argv) {
if (argc != 2) {
std::cerr << "uso: cfg_to_pda ARCHIVO.cfg\n";
return 2;
}
try {
Cfg g = load_cfg(argv[1]);
Pda p = cfg_to_pda(g);
std::cout << "# PDA de la gramática " << argv[1] << ".\n";
write_pda(std::cout, p);
} catch (const std::exception& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Gramática libre de contexto. El struct tiene los cuatro componentes de la definición
// G = (V, Σ, R, S), con los nombres del formato .cfg de code/formats.md.
// Además: leer y escribir ese formato, quitar las variables que no sirven, y las cadenas que
// genera una gramática hasta una longitud dada.
#ifndef CFG_H
#define CFG_H
#include <algorithm>
#include <cstddef>
#include <fstream>
#include <istream>
#include <map>
#include <ostream>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
// Una regla A → X1 X2 … Xk. Cada símbolo del lado derecho es el nombre de una variable o un
// terminal (una cadena de un solo carácter). La regla A → ε tiene el lado derecho vacío.
struct Rule {
std::string head;
std::vector<std::string> body;
bool operator==(const Rule& other) const = default;
};
struct Cfg {
std::vector<std::string> variables; // V, en el orden del archivo
std::vector<char> terminals; // Σ
std::vector<Rule> rules; // R
std::string start; // S ∈ V
};
inline bool is_variable(const Cfg& g, const std::string& symbol) {
return std::find(g.variables.begin(), g.variables.end(), symbol) != g.variables.end();
}
inline bool is_terminal(const Cfg& g, const std::string& symbol) {
return symbol.size() == 1 && std::find(g.terminals.begin(), g.terminals.end(), symbol[0]) != g.terminals.end();
}
// Lanza std::runtime_error si g no cumple la definición.
inline void check_cfg(const Cfg& g) {
std::set<std::string> v(g.variables.begin(), g.variables.end());
std::set<char> sigma(g.terminals.begin(), g.terminals.end());
if (g.variables.empty()) {
throw std::runtime_error("V no puede ser vacío");
}
if (v.size() != g.variables.size()) {
throw std::runtime_error("hay una variable repetida en variables");
}
if (sigma.size() != g.terminals.size()) {
throw std::runtime_error("hay un terminal repetido en terminals");
}
for (const std::string& name : g.variables) {
if (name == "eps" || name == "->" || name == "|") {
throw std::runtime_error("una variable no puede llamarse " + name);
}
if (name.size() == 1 && sigma.count(name[0]) > 0) {
throw std::runtime_error(name + " es variable y terminal a la vez: V y Σ no comparten símbolos");
}
}
if (sigma.count('|') > 0) {
throw std::runtime_error("el terminal | se confunde con el separador de alternativas");
}
if (v.count(g.start) == 0) {
throw std::runtime_error("la variable inicial " + g.start + " no está en variables");
}
for (const Rule& rule : g.rules) {
if (v.count(rule.head) == 0) {
throw std::runtime_error("regla de " + rule.head + ", que no está en variables");
}
for (const std::string& symbol : rule.body) {
bool terminal = symbol.size() == 1 && sigma.count(symbol[0]) > 0;
if (v.count(symbol) == 0 && !terminal) {
throw std::runtime_error("en una regla de " + rule.head + ": " + symbol +
" no es una variable ni un terminal");
}
}
}
}
// ------------------------------------------------------------
// Leer y escribir el formato .cfg
// ------------------------------------------------------------
inline std::vector<std::string> cfg_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 Cfg read_cfg(std::istream& in) {
int number = 0;
auto fail = [&number](const std::string& message) {
throw std::runtime_error("línea " + std::to_string(number) + ": " + message);
};
auto next_line = [&in, &number](std::vector<std::string>& words) {
std::string line;
while (std::getline(in, line)) {
number++;
if (!line.empty() && line[0] == '#') {
continue;
}
words = cfg_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;
};
Cfg g;
g.variables = field("variables");
for (const std::string& word : field("terminals")) {
if (word.size() != 1 || word[0] == '#') {
fail("un terminal es un solo carácter distinto de #: " + word);
}
g.terminals.push_back(word[0]);
}
std::vector<std::string> start = field("start");
if (start.size() != 1) {
fail("start: lleva exactamente una variable");
}
g.start = start[0];
if (!field("rules").empty()) {
fail("después de rules: las reglas van una por línea");
}
std::vector<std::string> words;
while (next_line(words)) {
if (words.size() < 3 || words[1] != "->") {
fail("una regla se escribe: variable -> alternativa | alternativa");
}
Rule rule;
rule.head = words[0];
// Cierra la alternativa que se venía leyendo. eps solo, o nada, es la alternativa vacía.
auto close = [&g, &rule, &fail]() {
if (rule.body.empty()) {
fail("alternativa vacía: la cadena vacía se escribe eps");
}
if (rule.body.size() == 1 && rule.body[0] == "eps") {
rule.body.clear();
}
g.rules.push_back(rule);
rule.body.clear();
};
for (std::size_t i = 2; i < words.size(); i++) {
if (words[i] == "|") {
close();
} else {
rule.body.push_back(words[i]);
}
}
close();
}
try {
check_cfg(g);
} catch (const std::runtime_error& error) {
throw std::runtime_error(std::string("la gramática no es válida: ") + error.what());
}
return g;
}
inline Cfg load_cfg(const std::string& path) {
std::ifstream file(path);
if (!file) {
throw std::runtime_error("no se pudo abrir " + path);
}
try {
return read_cfg(file);
} catch (const std::runtime_error& error) {
throw std::runtime_error(path + ": " + error.what());
}
}
// Escribe g en el formato .cfg, con las alternativas de cada variable en una sola línea.
inline void write_cfg(std::ostream& out, const Cfg& g) {
out << "variables:";
for (const std::string& name : g.variables) {
out << ' ' << name;
}
out << "\nterminals:";
for (char a : g.terminals) {
out << ' ' << a;
}
out << "\nstart: " << g.start << "\nrules:\n";
for (const std::string& name : g.variables) {
bool first = true;
for (const Rule& rule : g.rules) {
if (rule.head != name) {
continue;
}
out << (first ? name + " ->" : " |");
first = false;
if (rule.body.empty()) {
out << " eps";
}
for (const std::string& symbol : rule.body) {
out << ' ' << symbol;
}
}
if (!first) {
out << '\n';
}
}
}
// ------------------------------------------------------------
// Variables que no sirven
// ------------------------------------------------------------
// Las variables que generan alguna cadena de terminales. Se calculan marcando: una variable se
// marca cuando tiene una regla cuyo lado derecho solo tiene terminales y variables marcadas.
inline std::set<std::string> generating_variables(const Cfg& g) {
std::set<std::string> v(g.variables.begin(), g.variables.end());
std::set<std::string> marked;
bool changed = true;
while (changed) {
changed = false;
for (const Rule& rule : g.rules) {
if (marked.count(rule.head) > 0) {
continue;
}
bool all = true;
for (const std::string& symbol : rule.body) {
if (v.count(symbol) > 0 && marked.count(symbol) == 0) {
all = false;
break;
}
}
if (all) {
marked.insert(rule.head);
changed = true;
}
}
}
return marked;
}
// La misma gramática sin las variables que no generan nada y sin las que no se alcanzan desde
// la inicial. Genera el mismo lenguaje. La variable inicial se conserva siempre.
inline Cfg remove_useless(const Cfg& g) {
std::set<std::string> v(g.variables.begin(), g.variables.end());
std::set<std::string> generating = generating_variables(g);
// Primero se quitan las reglas que usan una variable que no genera nada.
std::vector<Rule> kept;
for (const Rule& rule : g.rules) {
bool ok = generating.count(rule.head) > 0;
for (const std::string& symbol : rule.body) {
if (v.count(symbol) > 0 && generating.count(symbol) == 0) {
ok = false;
}
}
if (ok) {
kept.push_back(rule);
}
}
// Después, las variables a las que no se llega desde la inicial con las reglas que quedan.
std::set<std::string> reached = {g.start};
bool changed = true;
while (changed) {
changed = false;
for (const Rule& rule : kept) {
if (reached.count(rule.head) == 0) {
continue;
}
for (const std::string& symbol : rule.body) {
if (v.count(symbol) > 0 && reached.insert(symbol).second) {
changed = true;
}
}
}
}
Cfg result;
result.terminals = g.terminals;
result.start = g.start;
for (const std::string& name : g.variables) {
if (reached.count(name) > 0) {
result.variables.push_back(name);
}
}
for (const Rule& rule : kept) {
if (reached.count(rule.head) > 0) {
result.rules.push_back(rule);
}
}
return result;
}
// ------------------------------------------------------------
// Las cadenas que genera una gramática
// ------------------------------------------------------------
// Para cada variable A, el conjunto de las cadenas de terminales w con A ⇒* w y |w| ≤ n.
// Se calcula por punto fijo: se empieza con conjuntos vacíos y se aplican las reglas, A → X1 … Xk
// agrega a A las concatenaciones de una cadena de cada Xi, hasta que ningún conjunto crece.
// Termina porque hay una cantidad finita de cadenas de longitud a lo sumo n. Es correcto para
// cualquier gramática, también con reglas ε y con recursión por la izquierda.
inline std::map<std::string, std::set<std::string>> languages_up_to(const Cfg& g, std::size_t n) {
std::set<std::string> v(g.variables.begin(), g.variables.end());
std::map<std::string, std::set<std::string>> table;
for (const std::string& name : g.variables) {
table[name];
}
bool changed = true;
while (changed) {
changed = false;
for (const Rule& rule : g.rules) {
std::set<std::string> partial = {""};
for (const std::string& symbol : rule.body) {
std::set<std::string> next;
if (v.count(symbol) > 0) {
for (const std::string& left : partial) {
for (const std::string& right : table[symbol]) {
if (left.size() + right.size() <= n) {
next.insert(left + right);
}
}
}
} else {
for (const std::string& left : partial) {
if (left.size() + 1 <= n) {
next.insert(left + symbol);
}
}
}
partial = next;
if (partial.empty()) {
break;
}
}
std::set<std::string>& target = table[rule.head];
for (const std::string& w : partial) {
if (target.insert(w).second) {
changed = true;
}
}
}
}
return table;
}
// Las cadenas de L(G) de longitud a lo sumo n.
inline std::set<std::string> strings_up_to(const Cfg& g, std::size_t n) {
return languages_up_to(g, n)[g.start];
}
#endif// Las construcciones de cierre con gramáticas: unión, concatenación y estrella.
// Las tres agregan una variable inicial nueva y una o dos reglas.
#ifndef CLOSURE_H
#define CLOSURE_H
#include <set>
#include <stdexcept>
#include <string>
#include <vector>
#include "cfg.h"
// Una copia de g con el sufijo dado en el nombre de cada variable, para que dos gramáticas
// no compartan variables aunque las dos usen S.
inline Cfg rename_variables(const Cfg& g, const std::string& suffix) {
Cfg result;
result.terminals = g.terminals;
result.start = g.start + suffix;
for (const std::string& name : g.variables) {
result.variables.push_back(name + suffix);
}
for (const Rule& rule : g.rules) {
Rule renamed;
renamed.head = rule.head + suffix;
for (const std::string& symbol : rule.body) {
renamed.body.push_back(is_variable(g, symbol) ? symbol + suffix : symbol);
}
result.rules.push_back(renamed);
}
return result;
}
// Junta las variables y las reglas de dos gramáticas ya renombradas, y agrega la variable
// inicial S0. Quien llama agrega las reglas de S0.
inline Cfg join(const Cfg& g1, const Cfg& g2) {
Cfg g;
g.start = "S0";
g.variables = {"S0"};
g.variables.insert(g.variables.end(), g1.variables.begin(), g1.variables.end());
g.variables.insert(g.variables.end(), g2.variables.begin(), g2.variables.end());
std::set<char> seen;
for (const Cfg* part : {&g1, &g2}) {
for (char a : part->terminals) {
if (seen.insert(a).second) {
g.terminals.push_back(a);
}
}
}
g.rules = g1.rules;
g.rules.insert(g.rules.end(), g2.rules.begin(), g2.rules.end());
return g;
}
// L(g) = L(g1) ∪ L(g2): la regla nueva es S0 → S1 | S2.
inline Cfg cfg_union(const Cfg& g1, const Cfg& g2) {
Cfg a = rename_variables(g1, "_1");
Cfg b = rename_variables(g2, "_2");
Cfg g = join(a, b);
g.rules.insert(g.rules.begin(), {Rule{"S0", {a.start}}, Rule{"S0", {b.start}}});
check_cfg(g);
return g;
}
// L(g) = L(g1) L(g2): la regla nueva es S0 → S1 S2.
inline Cfg cfg_concat(const Cfg& g1, const Cfg& g2) {
Cfg a = rename_variables(g1, "_1");
Cfg b = rename_variables(g2, "_2");
Cfg g = join(a, b);
g.rules.insert(g.rules.begin(), Rule{"S0", {a.start, b.start}});
check_cfg(g);
return g;
}
// L(g) = L(g1)*: las reglas nuevas son S0 → S1 S0 | ε.
inline Cfg cfg_star(const Cfg& g1) {
Cfg a = rename_variables(g1, "_1");
Cfg g;
g.start = "S0";
g.variables = {"S0"};
g.variables.insert(g.variables.end(), a.variables.begin(), a.variables.end());
g.terminals = a.terminals;
g.rules = {Rule{"S0", {a.start, "S0"}}, Rule{"S0", {}}};
g.rules.insert(g.rules.end(), a.rules.begin(), a.rules.end());
check_cfg(g);
return g;
}
#endif// Las dos construcciones que demuestran que las gramáticas libres de contexto y los autómatas
// de pila describen los mismos lenguajes:
// cfg_to_pda de una gramática a un PDA: la pila guarda lo que falta derivar
// pda_to_cfg de un PDA normalizado a una gramática: las variables A(p,q)
// normalize_pda lleva cualquier PDA a la forma que pda_to_cfg necesita
#ifndef CONVERT_H
#define CONVERT_H
#include <algorithm>
#include <cstddef>
#include <set>
#include <stdexcept>
#include <string>
#include <tuple>
#include <vector>
#include "cfg.h"
#include "pda.h"
// ------------------------------------------------------------
// De gramática a PDA
// ------------------------------------------------------------
// Construye un PDA que reconoce L(g). Tiene los estados q_start, q_begin, q_loop y q_accept,
// y los intermedios rN_J, que ponen en la pila el lado derecho de la regla número N, de
// derecha a izquierda, un símbolo por transición.
// q_start --ε, ε → $--> q_begin --ε, ε → S--> q_loop
// q_loop: para cada regla A → X1 … Xk, sacar A y poner X1 … Xk (X1 queda en la cima)
// q_loop: para cada terminal a, leer a y sacar a
// q_loop --ε, $ → ε--> q_accept
// Los símbolos de la pila son un solo carácter, así que las variables de g deben tener nombres
// de un carácter, y $ no puede ser un símbolo de g.
inline Pda cfg_to_pda(const Cfg& g) {
check_cfg(g);
Pda p;
p.states = {"q_start", "q_begin", "q_loop", "q_accept"};
p.alphabet = g.terminals;
p.start = "q_start";
p.accept = {"q_accept"};
p.stack = g.terminals;
for (const std::string& name : g.variables) {
if (name.size() != 1) {
throw std::runtime_error("la variable " + name + " debe tener un nombre de un solo carácter para ir en la pila");
}
p.stack.push_back(name[0]);
}
if (std::find(p.stack.begin(), p.stack.end(), '$') != p.stack.end()) {
throw std::runtime_error("el símbolo $ marca el fondo de la pila: la gramática no puede usarlo");
}
p.stack.push_back('$');
add_move(p, "q_start", EPS, EPS, "q_begin", '$');
add_move(p, "q_begin", EPS, EPS, "q_loop", g.start[0]);
for (std::size_t n = 0; n < g.rules.size(); n++) {
const Rule& rule = g.rules[n];
char head = rule.head[0];
std::size_t k = rule.body.size();
if (k == 0) {
add_move(p, "q_loop", EPS, head, "q_loop", EPS);
continue;
}
// Sacar A y poner Xk; después X(k-1), …, y al final X1, que vuelve a q_loop.
std::string from = "q_loop";
char pop = head;
for (std::size_t j = k; j >= 1; j--) {
std::string to = "q_loop";
if (j > 1) {
to = "r" + std::to_string(n + 1) + "_" + std::to_string(k - j + 1);
p.states.push_back(to);
}
add_move(p, from, EPS, pop, to, rule.body[j - 1][0]);
from = to;
pop = EPS;
}
}
for (char a : g.terminals) {
add_move(p, "q_loop", a, a, "q_loop", EPS);
}
add_move(p, "q_loop", EPS, '$', "q_accept", EPS);
check_pda(p);
return p;
}
// ------------------------------------------------------------
// Normalizar un PDA
// ------------------------------------------------------------
// Las condiciones que se pueden comprobar mirando la descripción: un solo estado de aceptación,
// y cada transición saca un símbolo o pone un símbolo, pero no las dos cosas ni ninguna.
// La tercera condición, que la pila esté vacía al aceptar, depende de las ejecuciones.
inline bool has_normal_shape(const Pda& p) {
if (p.accept.size() != 1) {
return false;
}
for (const auto& [key, moves] : p.delta) {
bool pops = std::get<2>(key) != EPS;
for (const Move& move : moves) {
bool pushes = move.push != EPS;
if (pops == pushes) {
return false;
}
}
}
return true;
}
// Un PDA que reconoce el mismo lenguaje que p y cumple las tres condiciones:
// 1. tiene un solo estado de aceptación, n_accept;
// 2. cuando llega a n_accept la pila está vacía;
// 3. cada transición saca un símbolo o pone un símbolo, y no las dos cosas ni ninguna.
// Agrega un estado inicial que pone una marca de fondo nueva, un estado n_drain que vacía la
// pila después de un estado de aceptación de p, y un estado intermedio por cada transición que
// se parte en dos.
inline Pda normalize_pda(const Pda& p) {
check_pda(p);
std::set<std::string> used(p.states.begin(), p.states.end());
auto fresh_state = [&used](std::string name) {
while (used.count(name) > 0) {
name += "'";
}
used.insert(name);
return name;
};
std::set<char> gamma(p.stack.begin(), p.stack.end());
auto fresh_symbol = [&gamma]() {
for (char c : std::string("@%&!?~^=+*<>")) {
if (gamma.insert(c).second) {
return c;
}
}
throw std::runtime_error("no queda un carácter libre para un símbolo nuevo de la pila");
};
Pda result;
std::string start = fresh_state("n_start");
std::string drain = fresh_state("n_drain");
std::string accept = fresh_state("n_accept");
char bottom = fresh_symbol(); // la marca de fondo nueva
char filler = fresh_symbol(); // el símbolo que se pone y se saca donde p no tocaba la pila
result.states = p.states;
result.states.insert(result.states.begin(), start);
result.states.push_back(drain);
result.states.push_back(accept);
result.alphabet = p.alphabet;
result.stack = p.stack;
result.stack.push_back(bottom);
result.stack.push_back(filler);
result.start = start;
result.accept = {accept};
// Las transiciones antes de partirlas: (desde, lee, saca, hacia, pone).
std::vector<std::tuple<std::string, char, char, std::string, char>> raw;
raw.push_back({start, EPS, EPS, p.start, bottom});
for (const std::string& state : p.states) {
for (const auto& [key, moves] : p.delta) {
if (std::get<0>(key) != state) {
continue;
}
for (const Move& move : moves) {
raw.push_back({state, std::get<1>(key), std::get<2>(key), move.target, move.push});
}
}
if (p.accept.count(state) > 0) {
raw.push_back({state, EPS, EPS, drain, EPS});
}
}
for (char c : p.stack) {
raw.push_back({drain, EPS, c, drain, EPS});
}
raw.push_back({drain, EPS, bottom, accept, EPS});
std::size_t counter = 0;
for (const auto& [from, read, pop, to, push] : raw) {
if ((pop == EPS) != (push == EPS)) {
add_move(result, from, read, pop, to, push);
continue;
}
std::string middle = fresh_state("n" + std::to_string(++counter));
result.states.insert(result.states.end() - 2, middle);
if (pop != EPS) {
// Saca y pone: primero saca, después pone.
add_move(result, from, read, pop, middle, EPS);
add_move(result, middle, EPS, EPS, to, push);
} else {
// Ni saca ni pone: pone el símbolo de relleno y lo saca enseguida.
add_move(result, from, read, EPS, middle, filler);
add_move(result, middle, EPS, filler, to, EPS);
}
}
check_pda(result);
return result;
}
// ------------------------------------------------------------
// De PDA a gramática
// ------------------------------------------------------------
inline std::string pair_variable(const std::string& p, const std::string& q) {
return "A(" + p + "," + q + ")";
}
// Construye la gramática de las variables A(p,q): A(p,q) genera las cadenas que llevan al
// autómata del estado p con la pila vacía al estado q con la pila vacía.
// A(p,p) → ε para cada estado p
// A(p,q) → A(p,r) A(r,q) para cada terna de estados p, q, r
// A(p,q) → a A(r,s) b si (r, u) ∈ δ(p, a, ε) y (q, ε) ∈ δ(s, b, u): el mismo
// símbolo u se pone al principio y se saca al final
// La variable inicial es A(q0, q_accept). El autómata debe estar normalizado: las condiciones
// 1 y 3 se comprueban aquí; la 2 (pila vacía al aceptar) la garantiza quien llama.
inline Cfg pda_to_cfg(const Pda& p) {
check_pda(p);
if (!has_normal_shape(p)) {
throw std::runtime_error("el PDA no está normalizado: pasarlo antes por normalize_pda");
}
Cfg g;
g.terminals = p.alphabet;
g.start = pair_variable(p.start, *p.accept.begin());
for (const std::string& a : p.states) {
for (const std::string& b : p.states) {
g.variables.push_back(pair_variable(a, b));
}
}
auto add_rule = [&g](const Rule& rule) {
if (std::find(g.rules.begin(), g.rules.end(), rule) == g.rules.end()) {
g.rules.push_back(rule);
}
};
// Las transiciones que ponen y las que sacan, agrupadas por el símbolo de la pila.
for (const auto& [push_key, push_moves] : p.delta) {
if (std::get<2>(push_key) != EPS) {
continue;
}
const std::string& from = std::get<0>(push_key);
char a = std::get<1>(push_key);
for (const Move& push_move : push_moves) {
for (const auto& [pop_key, pop_moves] : p.delta) {
if (std::get<2>(pop_key) != push_move.push) {
continue;
}
const std::string& before = std::get<0>(pop_key);
char b = std::get<1>(pop_key);
for (const Move& pop_move : pop_moves) {
Rule rule;
rule.head = pair_variable(from, pop_move.target);
if (a != EPS) {
rule.body.push_back(std::string(1, a));
}
rule.body.push_back(pair_variable(push_move.target, before));
if (b != EPS) {
rule.body.push_back(std::string(1, b));
}
add_rule(rule);
}
}
}
}
for (const std::string& a : p.states) {
for (const std::string& b : p.states) {
for (const std::string& r : p.states) {
g.rules.push_back({pair_variable(a, b), {pair_variable(a, r), pair_variable(r, b)}});
}
}
}
for (const std::string& a : p.states) {
g.rules.push_back({pair_variable(a, a), {}});
}
check_cfg(g);
return g;
}
#endif// Un parser de verdad, en pequeño: expresiones aritméticas con números, +, * y paréntesis.
// Tiene las dos etapas de siempre. El lexer parte el texto en tokens con un autómata finito.
// El parser descendente recursivo tiene una función por variable de la gramática sin ambigüedad
// E → E + T | T T → T * F | F F → ( E ) | número
// y lee cada token una sola vez, de izquierda a derecha.
#ifndef EXPR_H
#define EXPR_H
#include <cstddef>
#include <limits>
#include <stdexcept>
#include <string>
#include <vector>
enum class TokenKind { Number, Plus, Star, LParen, RParen, End };
struct Token {
TokenKind kind = TokenKind::End;
std::string text; // el texto del token: "42", "+", "("
std::size_t pos = 0; // dónde empieza, contando desde 0
};
// El lexer. Es un DFA con dos estados: fuera de un número y dentro de un número.
// Los tokens son los de las expresiones regulares [0-9]+, \+, \*, \( y \); los espacios se saltan.
// Siempre termina la lista con un token End.
inline std::vector<Token> lex(const std::string& text) {
std::vector<Token> tokens;
std::size_t i = 0;
while (i < text.size()) {
char c = text[i];
if (c == ' ') {
i++;
} else if (c >= '0' && c <= '9') {
std::size_t begin = i;
while (i < text.size() && text[i] >= '0' && text[i] <= '9') {
i++;
}
tokens.push_back({TokenKind::Number, text.substr(begin, i - begin), begin});
} else if (c == '+') {
tokens.push_back({TokenKind::Plus, "+", i++});
} else if (c == '*') {
tokens.push_back({TokenKind::Star, "*", i++});
} else if (c == '(') {
tokens.push_back({TokenKind::LParen, "(", i++});
} else if (c == ')') {
tokens.push_back({TokenKind::RParen, ")", i++});
} else {
throw std::runtime_error("columna " + std::to_string(i + 1) + ": el carácter " + std::string(1, c) +
" no forma ningún token");
}
}
tokens.push_back({TokenKind::End, "", text.size()});
return tokens;
}
// Lo que el parser devuelve por cada subexpresión: su valor y su árbol, escrito con todos los paréntesis.
struct Parsed {
long long value = 0;
std::string tree;
};
// El parser. next es la posición del token que toca leer: solo avanza.
struct Parser {
std::vector<Token> tokens;
std::size_t next = 0;
std::size_t calls = 0; // llamadas a expression, term y factor
const Token& peek() const { return tokens[next]; }
[[noreturn]] void fail(const std::string& expected) const {
const Token& token = peek();
std::string got = token.kind == TokenKind::End ? "el final" : token.text;
throw std::runtime_error("columna " + std::to_string(token.pos + 1) + ": se esperaba " + expected +
" y llegó " + got);
}
// E → E + T | T. La recursión por la izquierda se vuelve un ciclo: un T, y después cero o
// más veces "+ T". Cada vuelta agrupa hacia la izquierda, como la regla E → E + T.
Parsed expression() {
calls++;
Parsed left = term();
while (peek().kind == TokenKind::Plus) {
next++;
Parsed right = term();
if (left.value > std::numeric_limits<long long>::max() - right.value) {
throw std::runtime_error("el resultado no cabe en 64 bits");
}
left = {left.value + right.value, "(" + left.tree + " + " + right.tree + ")"};
}
return left;
}
// T → T * F | F, con el mismo ciclo.
Parsed term() {
calls++;
Parsed left = factor();
while (peek().kind == TokenKind::Star) {
next++;
Parsed right = factor();
if (right.value != 0 && left.value > std::numeric_limits<long long>::max() / right.value) {
throw std::runtime_error("el resultado no cabe en 64 bits");
}
left = {left.value * right.value, "(" + left.tree + " * " + right.tree + ")"};
}
return left;
}
// F → ( E ) | número. El token que viene decide la regla: no hay nada que adivinar.
Parsed factor() {
calls++;
if (peek().kind == TokenKind::Number) {
const std::string& text = tokens[next++].text;
if (text.size() > 18) {
throw std::runtime_error("el número " + text + " no cabe en 64 bits");
}
return {std::stoll(text), text};
}
if (peek().kind == TokenKind::LParen) {
next++;
Parsed inside = expression();
if (peek().kind != TokenKind::RParen) {
fail(")");
}
next++;
return inside;
}
fail("un número o (");
}
};
// Analiza la lista completa de tokens. Lanza std::runtime_error si no es una expresión.
inline Parsed parse(const std::vector<Token>& tokens, std::size_t* calls = nullptr) {
Parser parser;
parser.tokens = tokens;
Parsed result = parser.expression();
if (parser.peek().kind != TokenKind::End) {
parser.fail("+, * o el final");
}
if (calls != nullptr) {
*calls = parser.calls;
}
return result;
}
#endif// Normaliza un PDA: normalize_pda ARCHIVO.pda
// Escribe en formato .pda un autómata equivalente con un solo estado de aceptación, que vacía
// la pila antes de aceptar y en el que cada transición pone un símbolo o saca un símbolo.
#include <iostream>
#include <stdexcept>
#include <string>
#include "convert.h"
#include "pda.h"
int main(int argc, char** argv) {
if (argc != 2) {
std::cerr << "uso: normalize_pda ARCHIVO.pda\n";
return 2;
}
try {
Pda p = normalize_pda(load_pda(argv[1]));
std::cout << "# Forma normalizada de " << argv[1] << ".\n";
write_pda(std::cout, p);
} catch (const std::exception& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Analiza y evalúa expresiones aritméticas: parse_expr 'EXPRESIÓN'...
// Muestra los tokens que entrega el lexer, el árbol que arma el parser y el valor.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include "expr.h"
int main(int argc, char** argv) {
if (argc < 2) {
std::cerr << "uso: parse_expr 'EXPRESIÓN'...\n";
return 2;
}
for (int i = 1; i < argc; i++) {
std::string text = argv[i];
std::cout << text << '\n';
try {
std::vector<Token> tokens = lex(text);
std::cout << " tokens: ";
for (const Token& token : tokens) {
if (token.kind == TokenKind::Number) {
std::cout << " NUM(" << token.text << ")";
} else if (token.kind != TokenKind::End) {
std::cout << ' ' << token.text;
}
}
std::cout << '\n';
std::size_t calls = 0;
Parsed result = parse(tokens, &calls);
std::cout << " árbol: " << result.tree << '\n';
std::cout << " valor: " << result.value << '\n';
std::cout << " " << tokens.size() - 1 << " tokens, " << calls << " llamadas a las funciones del parser\n";
} catch (const std::runtime_error& error) {
std::cout << " error: " << error.what() << '\n';
}
}
}// De PDA a gramática: pda_to_cfg [--todo] ARCHIVO.pda
// El autómata debe estar normalizado (ver normalize_pda). Escribe en formato .cfg la gramática
// de las variables A(p,q), sin las variables que no generan nada o no se alcanzan.
// Con --todo escribe la gramática completa, tal como sale de la construcción.
#include <iostream>
#include <stdexcept>
#include <string>
#include "cfg.h"
#include "convert.h"
#include "pda.h"
int main(int argc, char** argv) {
bool everything = argc == 3 && std::string(argv[1]) == "--todo";
if (argc != 2 && !everything) {
std::cerr << "uso: pda_to_cfg [--todo] ARCHIVO.pda\n";
return 2;
}
try {
std::string path = argv[argc - 1];
Cfg full = pda_to_cfg(load_pda(path));
Cfg useful = remove_useless(full);
std::cout << "# Gramática del PDA " << path << ".\n";
std::cout << "# La construcción da " << full.variables.size() << " variables y " << full.rules.size()
<< " reglas.\n# Sirven " << useful.variables.size() << " variables y " << useful.rules.size()
<< " reglas.\n";
write_cfg(std::cout, everything ? full : useful);
} catch (const std::exception& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Autómata de pila. El struct tiene los seis componentes de la definición
// P = (Q, Σ, Γ, δ, q0, F), con los nombres del formato .pda de code/formats.md.
// Además: leer y escribir ese formato, y simular el autómata con una búsqueda sobre sus
// configuraciones (estado, posición en la entrada, pila).
// Las funciones que leen líneas siguen el esquema de code/week-01/dfa.h.
#ifndef PDA_H
#define PDA_H
#include <algorithm>
#include <compare>
#include <cstddef>
#include <fstream>
#include <istream>
#include <map>
#include <ostream>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <tuple>
#include <vector>
// ε en una transición: no leer, no sacar o no poner. Ningún símbolo de un archivo vale '\0'.
const char EPS = '\0';
// Un elemento de δ(q, a, b): el estado de destino y lo que se pone en la pila (un símbolo o ε).
struct Move {
std::string target;
char push;
bool operator==(const Move& other) const = default;
};
struct Pda {
std::vector<std::string> states; // Q, en el orden del archivo
std::vector<char> alphabet; // Σ
std::vector<char> stack; // Γ
// δ : Q × Σε × Γε → P(Q × Γε). La clave es (estado, lee, saca), con EPS donde va ε.
std::map<std::tuple<std::string, char, char>, std::vector<Move>> delta;
std::string start; // q0
std::set<std::string> accept; // F ⊆ Q
};
// Cómo se escribe un símbolo o ε en un archivo.
inline std::string symbol_name(char c) {
return c == EPS ? "eps" : std::string(1, c);
}
// Cómo se muestra en una traza.
inline std::string symbol_shown(char c) {
return c == EPS ? "ε" : std::string(1, c);
}
// Agrega (target, push) a δ(state, read, pop), sin repetirlo.
inline void add_move(Pda& p, const std::string& state, char read, char pop, const std::string& target, char push) {
std::vector<Move>& moves = p.delta[{state, read, pop}];
Move move = {target, push};
if (std::find(moves.begin(), moves.end(), move) == moves.end()) {
moves.push_back(move);
}
}
// ------------------------------------------------------------
// Comprobar que la séxtupla es un PDA
// ------------------------------------------------------------
// Lanza std::runtime_error si p no cumple la definición.
inline void check_pda(const Pda& p) {
std::set<std::string> q(p.states.begin(), p.states.end());
std::set<char> sigma(p.alphabet.begin(), p.alphabet.end());
std::set<char> gamma(p.stack.begin(), p.stack.end());
if (p.states.empty()) {
throw std::runtime_error("Q no puede ser vacío");
}
if (q.size() != p.states.size()) {
throw std::runtime_error("hay un estado repetido en states");
}
if (sigma.size() != p.alphabet.size()) {
throw std::runtime_error("hay un símbolo repetido en alphabet");
}
if (gamma.size() != p.stack.size()) {
throw std::runtime_error("hay un símbolo repetido en stack");
}
if (q.count(p.start) == 0) {
throw std::runtime_error("el estado inicial " + p.start + " no está en states");
}
for (const std::string& f : p.accept) {
if (q.count(f) == 0) {
throw std::runtime_error("el estado de aceptación " + f + " no está en states");
}
}
for (const auto& [key, moves] : p.delta) {
const auto& [state, read, pop] = key;
if (q.count(state) == 0) {
throw std::runtime_error("transición desde " + state + ", que no está en states");
}
if (read != EPS && sigma.count(read) == 0) {
throw std::runtime_error("transición que lee " + symbol_name(read) + ", que no está en alphabet");
}
if (pop != EPS && gamma.count(pop) == 0) {
throw std::runtime_error("transición que saca " + symbol_name(pop) + ", que no está en stack");
}
for (const Move& move : moves) {
if (q.count(move.target) == 0) {
throw std::runtime_error("transición hacia " + move.target + ", que no está en states");
}
if (move.push != EPS && gamma.count(move.push) == 0) {
throw std::runtime_error("transición que pone " + symbol_name(move.push) + ", que no está en stack");
}
}
}
}
// ------------------------------------------------------------
// Leer y escribir el formato .pda
// ------------------------------------------------------------
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 Pda read_pda(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;
};
// Un símbolo de un alfabeto: un solo carácter distinto de #.
auto symbol = [&fail](const std::string& word) {
if (word.size() != 1 || word[0] == '#') {
fail("un símbolo es un solo carácter distinto de #: " + word);
}
return word[0];
};
// Lo mismo, o eps.
auto symbol_or_eps = [&symbol](const std::string& word) { return word == "eps" ? EPS : symbol(word); };
Pda p;
p.states = field("states");
for (const std::string& word : field("alphabet")) {
p.alphabet.push_back(symbol(word));
}
for (const std::string& word : field("stack")) {
p.stack.push_back(symbol(word));
}
std::vector<std::string> start = field("start");
if (start.size() != 1) {
fail("start: lleva exactamente un estado");
}
p.start = start[0];
for (const std::string& state : field("accept")) {
p.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() != 6 || words[3] != "->") {
fail("una transición se escribe: estado lee saca -> destino pone (cada uno, un símbolo o eps)");
}
add_move(p, words[0], symbol_or_eps(words[1]), symbol_or_eps(words[2]), words[4], symbol_or_eps(words[5]));
}
check_pda(p);
return p;
}
inline Pda load_pda(const std::string& path) {
std::ifstream file(path);
if (!file) {
throw std::runtime_error("no se pudo abrir " + path);
}
try {
return read_pda(file);
} catch (const std::runtime_error& error) {
throw std::runtime_error(path + ": " + error.what());
}
}
// Escribe p en el formato .pda: lo que escribe se puede volver a leer con read_pda.
// Las transiciones salen agrupadas por estado, en el orden de states.
inline void write_pda(std::ostream& out, const Pda& p) {
out << "states:";
for (const std::string& state : p.states) {
out << ' ' << state;
}
out << "\nalphabet:";
for (char a : p.alphabet) {
out << ' ' << a;
}
out << "\nstack:";
for (char c : p.stack) {
out << ' ' << c;
}
out << "\nstart: " << p.start << "\naccept:";
for (const std::string& state : p.states) {
if (p.accept.count(state) > 0) {
out << ' ' << state;
}
}
out << "\ndelta:\n";
for (const std::string& state : p.states) {
for (const auto& [key, moves] : p.delta) {
if (std::get<0>(key) != state) {
continue;
}
for (const Move& move : moves) {
out << state << ' ' << symbol_name(std::get<1>(key)) << ' ' << symbol_name(std::get<2>(key)) << " -> "
<< move.target << ' ' << symbol_name(move.push) << '\n';
}
}
}
}
inline std::size_t count_transitions(const Pda& p) {
std::size_t total = 0;
for (const auto& [key, moves] : p.delta) {
total += moves.size();
}
return total;
}
// ------------------------------------------------------------
// Simular
// ------------------------------------------------------------
// Una configuración: el estado, cuántos símbolos de la entrada ya se leyeron, y la pila, con la
// cima en stack[0]. La configuración inicial es (q0, 0, ε).
struct Config {
std::string state;
std::size_t pos = 0;
std::string stack;
auto operator<=>(const Config& other) const = default;
};
// Un paso de una ejecución: la transición que se usó (lee, saca → pone) y adónde llevó.
struct Step {
char read = EPS;
char pop = EPS;
char push = EPS;
Config config;
};
// Las configuraciones a las que se llega en un paso desde c, con la entrada w.
// Una transición (q, a, b) → (r, c) se puede usar si a es ε o el siguiente símbolo de w, y
// si b es ε o la cima de la pila. Con la pila vacía solo sirven las que no sacan nada.
inline std::vector<Step> successors(const Pda& p, const std::string& w, const Config& c) {
std::vector<Step> result;
std::vector<char> reads = {EPS};
if (c.pos < w.size()) {
reads.push_back(w[c.pos]);
}
std::vector<char> pops = {EPS};
if (!c.stack.empty()) {
pops.push_back(c.stack[0]);
}
for (char read : reads) {
for (char pop : pops) {
auto it = p.delta.find({c.state, read, pop});
if (it == p.delta.end()) {
continue;
}
for (const Move& move : it->second) {
Step step;
step.read = read;
step.pop = pop;
step.push = move.push;
step.config.state = move.target;
step.config.pos = c.pos + (read == EPS ? 0 : 1);
step.config.stack = c.stack.substr(pop == EPS ? 0 : 1);
if (move.push != EPS) {
step.config.stack.insert(step.config.stack.begin(), move.push);
}
result.push_back(step);
}
}
}
return result;
}
enum class Verdict { Accept, Reject, Limit };
struct Search {
Verdict verdict = Verdict::Reject;
std::vector<Step> run; // si acepta: una ejecución de aceptación, desde la configuración inicial
std::size_t explored = 0; // configuraciones distintas que la búsqueda llegó a descubrir
};
// Sin tope de altura de pila.
const std::size_t NO_STACK_BOUND = static_cast<std::size_t>(-1);
// Decide si p acepta w con una búsqueda por niveles sobre las configuraciones.
// - Accept: se llegó a una configuración con toda la entrada leída y el estado en F.
// run es una ejecución de aceptación con la menor cantidad de pasos.
// - Reject: se exploraron todas las configuraciones alcanzables y ninguna es de aceptación.
// - Limit: se descubrieron más de max_configs configuraciones distintas sin aceptar. Pasa
// con los autómatas que tienen ciclos de transiciones ε que hacen crecer la pila.
// El conjunto seen evita explorar dos veces la misma configuración: sin él, un ciclo de
// transiciones ε que no cambia la pila no terminaría nunca.
// Si max_stack no es NO_STACK_BOUND, se descartan las configuraciones con una pila más alta.
// Eso solo es correcto cuando se sabe que ninguna ejecución de aceptación las necesita.
inline Search simulate(const Pda& p, const std::string& w, std::size_t max_configs = 100000,
std::size_t max_stack = NO_STACK_BOUND) {
auto accepting = [&p, &w](const Config& c) { return c.pos == w.size() && p.accept.count(c.state) > 0; };
std::vector<Step> found; // found[i]: la configuración i y la transición que la descubrió
std::vector<std::size_t> parent; // de cuál se llegó a la configuración i
std::set<Config> seen;
// Reconstruye la ejecución que termina en la configuración i.
auto path_to = [&found, &parent](std::size_t i) {
std::vector<Step> run;
while (true) {
run.push_back(found[i]);
if (parent[i] == i) {
break;
}
i = parent[i];
}
std::reverse(run.begin(), run.end());
return run;
};
Step first;
first.config.state = p.start;
found.push_back(first);
parent.push_back(0);
seen.insert(first.config);
Search search;
if (accepting(first.config)) {
search.verdict = Verdict::Accept;
search.run = path_to(0);
search.explored = 1;
return search;
}
for (std::size_t head = 0; head < found.size(); head++) {
Config current = found[head].config;
for (const Step& step : successors(p, w, current)) {
if (max_stack != NO_STACK_BOUND && step.config.stack.size() > max_stack) {
continue;
}
if (!seen.insert(step.config).second) {
continue;
}
found.push_back(step);
parent.push_back(head);
if (accepting(step.config)) {
search.verdict = Verdict::Accept;
search.run = path_to(found.size() - 1);
search.explored = found.size();
return search;
}
if (found.size() > max_configs) {
search.verdict = Verdict::Limit;
search.explored = found.size();
return search;
}
}
}
search.verdict = Verdict::Reject;
search.explored = found.size();
return search;
}
// p acepta w. Lanza si la búsqueda llega al límite: quien llama debe saber que no pasará.
inline bool accepts(const Pda& p, const std::string& w, std::size_t max_configs = 100000) {
Search search = simulate(p, w, max_configs);
if (search.verdict == Verdict::Limit) {
throw std::runtime_error("la búsqueda llegó al límite de configuraciones con la cadena " + w);
}
return search.verdict == Verdict::Accept;
}
// Todas las cadenas sobre sigma de longitud a lo sumo n, primero las más cortas.
inline std::vector<std::string> all_strings(const std::vector<char>& sigma, std::size_t n) {
std::vector<std::string> result = {""};
std::size_t begin = 0;
for (std::size_t length = 1; length <= n; length++) {
std::size_t end = result.size();
for (std::size_t i = begin; i < end; i++) {
for (char a : sigma) {
result.push_back(result[i] + a);
}
}
begin = end;
}
return result;
}
#endif// Los lenguajes de los autómatas de machines/, como funciones que miran la cadena completa.
// Las pruebas comparan cada autómata y cada gramática con su función.
#ifndef PREDICATES_H
#define PREDICATES_H
#include <algorithm>
#include <cstddef>
#include <string>
#include "pumping.h"
// { w w^R }: los palíndromos de longitud par.
inline bool is_even_palindrome(const std::string& w) {
std::string reversed(w.rbegin(), w.rend());
return w.size() % 2 == 0 && w == reversed;
}
// Paréntesis balanceados: ningún prefijo cierra más de lo que abrió, y al final no queda nada abierto.
inline bool is_balanced(const std::string& w) {
long open = 0;
for (char c : w) {
open += (c == '(') ? 1 : -1;
if (open < 0) {
return false;
}
}
return open == 0;
}
// La misma cantidad de a que de b.
inline bool has_equal_ab(const std::string& w) {
return std::count(w.begin(), w.end(), 'a') == std::count(w.begin(), w.end(), 'b');
}
// { a^n b^n c^m }
inline bool is_anbn_cm(const std::string& w) {
std::size_t i = 0;
std::size_t a = block(w, i, 'a');
std::size_t b = block(w, i, 'b');
block(w, i, 'c');
return i == w.size() && a == b;
}
// { a^m b^n c^n }
inline bool is_am_bncn(const std::string& w) {
std::size_t i = 0;
block(w, i, 'a');
std::size_t b = block(w, i, 'b');
std::size_t c = block(w, i, 'c');
return i == w.size() && b == c;
}
// { a^i b^j c^k : i = j o j = k }
inline bool is_ij_or_jk(const std::string& w) {
return is_anbn_cm(w) || is_am_bncn(w);
}
// Cantidad par de unos.
inline bool has_even_ones(const std::string& w) {
return std::count(w.begin(), w.end(), '1') % 2 == 0;
}
#endif// Funciones para mostrar autómatas de pila y sus ejecuciones en la terminal.
#ifndef PRINT_H
#define PRINT_H
#include <cstddef>
#include <ostream>
#include <string>
#include <vector>
#include "pda.h"
// Cuántas columnas ocupa un texto en UTF-8: los bytes de continuación no cuentan.
inline std::size_t width_of(const std::string& text) {
std::size_t width = 0;
for (unsigned char c : text) {
if ((c & 0xC0) != 0x80) {
width++;
}
}
return width;
}
// El texto, completado con espacios a la derecha hasta ocupar width columnas.
inline std::string pad(const std::string& text, std::size_t width) {
std::size_t used = width_of(text);
return used >= width ? text : text + std::string(width - used, ' ');
}
inline std::string shown(const std::string& w) {
return w.empty() ? "ε" : w;
}
// La etiqueta de una transición, como en los diagramas: "lee, saca → pone".
inline std::string label_of(const Step& step) {
return symbol_shown(step.read) + ", " + symbol_shown(step.pop) + " → " + symbol_shown(step.push);
}
// Una ejecución como tabla: una fila por configuración, con la transición que llevó a ella.
// La pila se escribe con la cima a la izquierda.
inline void print_run(std::ostream& out, const std::string& w, const std::vector<Step>& run) {
std::size_t state_width = 6;
std::size_t rest_width = 10;
for (const Step& step : run) {
state_width = std::max(state_width, width_of(step.config.state));
rest_width = std::max(rest_width, w.size() - step.config.pos);
}
out << " paso transición " << pad("estado", state_width) << " " << pad("falta leer", rest_width) << " pila\n";
for (std::size_t i = 0; i < run.size(); i++) {
const Step& step = run[i];
std::string number = std::to_string(i);
out << " " << std::string(4 - std::min<std::size_t>(4, number.size()), ' ') << number << " "
<< pad(i == 0 ? "" : label_of(step), 10) << " " << pad(step.config.state, state_width) << " "
<< pad(shown(w.substr(step.config.pos)), rest_width) << " " << shown(step.config.stack) << '\n';
}
}
#endif// Juega el lema de bombeo completo con cadenas cortas: pump_demo [P_MAX]
// Para cada lenguaje y cada p, lista todas las divisiones s = uvxyz con |vy| > 0 y |vxy| ≤ p,
// y cuenta cuántas salen del lenguaje con i = 2, cuántas necesitan i = 0 y cuántas sobreviven.
// Es una comprobación con p pequeños, no una demostración: la demostración vale para todo p.
#include <cstddef>
#include <functional>
#include <iomanip>
#include <iostream>
#include <string>
#include "pumping.h"
namespace {
void table(const std::string& title, const std::function<bool(const std::string&)>& in_language,
const std::function<std::string(std::size_t)>& choose, std::size_t p_max) {
std::cout << title << '\n';
std::cout << " p |s| divisiones fuera con i=2 solo con i=0 sobreviven\n";
for (std::size_t p = 1; p <= p_max; p++) {
std::string s = choose(p);
PumpReport report = pump_report(in_language, s, p);
std::cout << std::setw(4) << p << std::setw(6) << s.size() << std::setw(12) << report.total << std::setw(15)
<< report.out_with_2 << std::setw(14) << report.out_with_0 << std::setw(12) << report.survive
<< '\n';
if (p == p_max && report.survive > 0) {
const Division& d = report.example;
auto part = [&s](std::size_t from, std::size_t length) {
return length == 0 ? std::string("ε") : s.substr(from, length);
};
std::cout << " una división que sobrevive con p = " << p << ": u = " << part(0, d.u)
<< ", v = " << part(d.u, d.v) << ", x = " << part(d.u + d.v, d.x)
<< ", y = " << part(d.u + d.v + d.x, d.y) << ", z = "
<< part(d.u + d.v + d.x + d.y, s.size() - d.u - d.v - d.x - d.y) << '\n';
}
}
std::cout << '\n';
}
std::string repeat(char c, std::size_t n) {
return std::string(n, c);
}
} // namespace
int main(int argc, char** argv) {
std::size_t p_max = argc > 1 ? std::stoul(argv[1]) : 6;
table("{ 0^n 1^n }, s = 0^p 1^p (libre de contexto: tiene que haber divisiones que sobreviven)", is_zeros_ones,
[](std::size_t p) { return repeat('0', p) + repeat('1', p); }, p_max);
table("{ a^n b^n c^n }, s = a^p b^p c^p", is_anbncn,
[](std::size_t p) { return repeat('a', p) + repeat('b', p) + repeat('c', p); }, p_max);
table("{ ww }, s = 0^p 1 0^p 1 (una mala elección)", is_ww,
[](std::size_t p) { return repeat('0', p) + "1" + repeat('0', p) + "1"; }, p_max);
table("{ ww }, s = 0^p 1^p 0^p 1^p", is_ww,
[](std::size_t p) { return repeat('0', p) + repeat('1', p) + repeat('0', p) + repeat('1', p); }, p_max);
table("{ a^i b^j c^k : i ≤ j ≤ k }, s = a^p b^p c^p", is_ordered_abc,
[](std::size_t p) { return repeat('a', p) + repeat('b', p) + repeat('c', p); }, p_max);
}// El lema de bombeo para lenguajes libres de contexto, como un juego que se puede jugar
// completo cuando la cadena es corta: se listan todas las divisiones s = uvxyz que el
// adversario puede elegir, y para cada una se busca un exponente que saque la cadena del lenguaje.
#ifndef PUMPING_H
#define PUMPING_H
#include <cstddef>
#include <functional>
#include <string>
#include <vector>
// Una división s = uvxyz, dada por las longitudes de u, v, x e y. Lo que sobra es z.
struct Division {
std::size_t u = 0;
std::size_t v = 0;
std::size_t x = 0;
std::size_t y = 0;
};
// La cadena u v^i x y^i z.
inline std::string pump(const std::string& s, const Division& d, std::size_t i) {
std::string u = s.substr(0, d.u);
std::string v = s.substr(d.u, d.v);
std::string x = s.substr(d.u + d.v, d.x);
std::string y = s.substr(d.u + d.v + d.x, d.y);
std::string z = s.substr(d.u + d.v + d.x + d.y);
std::string result = u;
for (std::size_t k = 0; k < i; k++) {
result += v;
}
result += x;
for (std::size_t k = 0; k < i; k++) {
result += y;
}
return result + z;
}
// Todas las divisiones de s que cumplen las condiciones del lema: |vy| > 0 y |vxy| ≤ p.
inline std::vector<Division> divisions(const std::string& s, std::size_t p) {
std::vector<Division> result;
for (std::size_t u = 0; u <= s.size(); u++) {
for (std::size_t v = 0; u + v <= s.size() && v <= p; v++) {
for (std::size_t x = 0; u + v + x <= s.size() && v + x <= p; x++) {
for (std::size_t y = 0; u + v + x + y <= s.size() && v + x + y <= p; y++) {
if (v + y > 0) {
result.push_back({u, v, x, y});
}
}
}
}
}
return result;
}
// Cómo le va a cada división de s contra el lenguaje.
struct PumpReport {
std::size_t total = 0; // divisiones que el adversario puede elegir
std::size_t out_with_2 = 0; // u v² x y² z ya no está en el lenguaje
std::size_t out_with_0 = 0; // con i = 2 sigue en el lenguaje, pero u x z no está
std::size_t survive = 0; // sigue en el lenguaje con todos los i de 0 a max_i
Division example; // una de las que sobreviven, si hay
};
inline PumpReport pump_report(const std::function<bool(const std::string&)>& in_language, const std::string& s,
std::size_t p, std::size_t max_i = 4) {
PumpReport report;
for (const Division& d : divisions(s, p)) {
report.total++;
if (!in_language(pump(s, d, 2))) {
report.out_with_2++;
continue;
}
if (!in_language(pump(s, d, 0))) {
report.out_with_0++;
continue;
}
bool all = true;
for (std::size_t i = 0; i <= max_i; i++) {
all = all && in_language(pump(s, d, i));
}
if (all) {
if (report.survive == 0) {
report.example = d;
}
report.survive++;
}
}
return report;
}
// ------------------------------------------------------------
// Los lenguajes de los ejemplos, como funciones que miran la cadena completa
// ------------------------------------------------------------
// Cuenta un bloque de símbolos c a partir de la posición i, y avanza i.
inline std::size_t block(const std::string& w, std::size_t& i, char c) {
std::size_t count = 0;
while (i < w.size() && w[i] == c) {
i++;
count++;
}
return count;
}
// { 0^n 1^n : n ≥ 0 }
inline bool is_zeros_ones(const std::string& w) {
std::size_t i = 0;
std::size_t zeros = block(w, i, '0');
std::size_t ones = block(w, i, '1');
return i == w.size() && zeros == ones;
}
// { a^n b^n c^n : n ≥ 0 }
inline bool is_anbncn(const std::string& w) {
std::size_t i = 0;
std::size_t a = block(w, i, 'a');
std::size_t b = block(w, i, 'b');
std::size_t c = block(w, i, 'c');
return i == w.size() && a == b && b == c;
}
// { a^i b^j c^k : i ≤ j ≤ k }
inline bool is_ordered_abc(const std::string& w) {
std::size_t i = 0;
std::size_t a = block(w, i, 'a');
std::size_t b = block(w, i, 'b');
std::size_t c = block(w, i, 'c');
return i == w.size() && a <= b && b <= c;
}
// { ww : w es cualquier cadena }
inline bool is_ww(const std::string& w) {
if (w.size() % 2 != 0) {
return false;
}
std::size_t half = w.size() / 2;
return w.substr(0, half) == w.substr(half);
}
#endif// Simula un PDA con una o más cadenas: run_pda [--limite N] ARCHIVO.pda CADENA...
// Con - en lugar del archivo, lee la descripción de la entrada estándar.
// Si el autómata acepta, muestra una ejecución de aceptación, configuración por configuración.
// La cadena vacía se pasa como '' en la terminal.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include "pda.h"
#include "print.h"
int main(int argc, char** argv) {
std::size_t limit = 100000;
int first = 1;
if (argc >= 3 && std::string(argv[1]) == "--limite") {
limit = std::stoul(argv[2]);
first = 3;
}
if (argc < first + 2) {
std::cerr << "uso: run_pda [--limite N] ARCHIVO.pda CADENA...\n";
return 2;
}
try {
std::string path = argv[first];
Pda p = (path == "-") ? read_pda(std::cin) : load_pda(path);
for (int i = first + 1; i < argc; i++) {
std::string w = argv[i];
Search search = simulate(p, w, limit);
std::cout << "w = " << shown(w) << '\n';
if (search.verdict == Verdict::Accept) {
print_run(std::cout, w, search.run);
std::cout << " acepta en " << search.run.back().config.state << " (configuraciones exploradas: "
<< search.explored << ")\n";
} else if (search.verdict == Verdict::Reject) {
std::cout << " rechaza: " << search.explored << " configuraciones alcanzables, ninguna acepta\n";
} else {
std::cout << " límite: más de " << limit << " configuraciones, sin aceptar\n";
}
}
} catch (const std::exception& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Muestra un archivo .pda como la séxtupla (Q, Σ, Γ, δ, q0, F): show_pda ARCHIVO.pda
// De δ solo se listan los valores que no son vacíos.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include "pda.h"
#include "print.h"
int main(int argc, char** argv) {
if (argc != 2) {
std::cerr << "uso: show_pda ARCHIVO.pda\n";
return 2;
}
try {
Pda p = load_pda(argv[1]);
std::cout << "Q = {";
for (std::size_t i = 0; i < p.states.size(); i++) {
std::cout << (i > 0 ? ", " : "") << p.states[i];
}
std::cout << "}\nΣ = {";
for (std::size_t i = 0; i < p.alphabet.size(); i++) {
std::cout << (i > 0 ? ", " : "") << p.alphabet[i];
}
std::cout << "}\nΓ = {";
for (std::size_t i = 0; i < p.stack.size(); i++) {
std::cout << (i > 0 ? ", " : "") << p.stack[i];
}
std::cout << "}\nq0 = " << p.start << "\nF = {";
bool first = true;
for (const std::string& state : p.states) {
if (p.accept.count(state) > 0) {
std::cout << (first ? "" : ", ") << state;
first = false;
}
}
std::cout << "}\n\n";
for (const std::string& state : p.states) {
for (const auto& [key, moves] : p.delta) {
if (std::get<0>(key) != state) {
continue;
}
std::cout << "δ(" << state << ", " << symbol_shown(std::get<1>(key)) << ", "
<< symbol_shown(std::get<2>(key)) << ") = {";
for (std::size_t i = 0; i < moves.size(); i++) {
std::cout << (i > 0 ? ", " : "") << "(" << moves[i].target << ", " << symbol_shown(moves[i].push)
<< ")";
}
std::cout << "}\n";
}
}
std::cout << "\n" << p.states.size() << " estados, " << count_transitions(p) << " transiciones\n";
} catch (const std::exception& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}# { a^m b^n c^n : m, n >= 0 }
variables: S A Y
terminals: a b c
start: S
rules:
S -> A Y
A -> a A | eps
Y -> b Y c | eps# { a^n b^n c^m : n, m >= 0 }
variables: S X C
terminals: a b c
start: S
rules:
S -> X C
X -> a X b | eps
C -> c C | eps# { a^n b^n c^m : n, m >= 0 }
# El intento de reconocer a^n b^n c^n: después de comparar las a con las b la pila quedó
# vacía, y no hay con qué contar las c.
states: q0 q1 q2 q3
alphabet: a b c
stack: a $
start: q0
accept: q3
delta:
q0 eps eps -> q1 $
q1 a eps -> q1 a
q1 eps eps -> q2 eps
q2 b a -> q2 eps
q2 eps $ -> q3 eps
q3 c eps -> q3 eps# Paréntesis balanceados.
variables: S
terminals: ( )
start: S
rules:
S -> ( S ) S | eps# Paréntesis balanceados.
states: q0 q1 q2
alphabet: ( )
stack: ( $
start: q0
accept: q2
delta:
q0 eps eps -> q1 $
q1 ( eps -> q1 (
q1 ) ( -> q1 eps
q1 eps $ -> q2 eps# Cadenas sobre {a, b} con la misma cantidad de a que de b.
variables: S
terminals: a b
start: S
rules:
S -> a S b S | b S a S | eps# Cadenas sobre {a, b} con la misma cantidad de a que de b.
# La pila guarda lo que sobra: cada a se cancela con una b, en cualquier orden.
states: q0 q1 q2
alphabet: a b
stack: a b $
start: q0
accept: q2
delta:
q0 eps eps -> q1 $
q1 a eps -> q1 a
q1 a b -> q1 eps
q1 b eps -> q1 b
q1 b a -> q1 eps
q1 eps $ -> q2 eps# Cadenas binarias con una cantidad par de unos: el DFA de la semana 1 escrito como PDA.
# Ninguna transición saca ni pone nada, así que el alfabeto de la pila puede quedar vacío.
states: par impar
alphabet: 0 1
stack:
start: par
accept: par
delta:
par 0 eps -> par eps
par 1 eps -> impar eps
impar 0 eps -> impar eps
impar 1 eps -> par eps# { w w^R : w en {0,1}* }: los palíndromos de longitud par.
variables: S
terminals: 0 1
start: S
rules:
S -> 0 S 0 | 1 S 1 | eps# { w w^R : w en {0,1}* }: los palíndromos de longitud par.
# En q1 guarda la primera mitad; con la transición eps de q1 a q2 adivina que llegó al medio.
states: q0 q1 q2 q3
alphabet: 0 1
stack: 0 1 $
start: q0
accept: q3
delta:
q0 eps eps -> q1 $
q1 0 eps -> q1 0
q1 1 eps -> q1 1
q1 eps eps -> q2 eps
q2 0 0 -> q2 eps
q2 1 1 -> q2 eps
q2 eps $ -> q3 eps# Expresiones aritméticas con suma, producto y paréntesis, sin ambigüedad.
# E es una suma de términos, T un producto de factores, y F un factor. El terminal a es un número.
variables: E T F
terminals: a + * ( )
start: E
rules:
E -> E + T | T
T -> T * F | F
F -> ( E ) | a# { a^i b^j c^k : i = j o j = k }
# Desde q1 elige, sin leer nada, cuál de las dos comparaciones va a hacer.
states: q0 q1 q2 q3 q4 q5 q6 q7 q8
alphabet: a b c
stack: a b $
start: q0
accept: q4 q8
delta:
q0 eps eps -> q1 $
# Rama i = j: guarda las a, las cancela con las b, y deja pasar las c.
q1 eps eps -> q2 eps
q2 a eps -> q2 a
q2 eps eps -> q3 eps
q3 b a -> q3 eps
q3 eps $ -> q4 eps
q4 c eps -> q4 eps
# Rama j = k: deja pasar las a, guarda las b y las cancela con las c.
q1 eps eps -> q5 eps
q5 a eps -> q5 eps
q5 eps eps -> q6 eps
q6 b eps -> q6 b
q6 eps eps -> q7 eps
q7 c b -> q7 eps
q7 eps $ -> q8 eps# { 0^n 1^n : n >= 0 }, en la forma que pide la construcción de PDA a gramática:
# un solo estado de aceptación, la pila vacía al aceptar, y cada transición pone un
# símbolo o saca un símbolo.
states: q0 q1 q2 q3
alphabet: 0 1
stack: 0 $
start: q0
accept: q3
delta:
q0 eps eps -> q1 $
q1 0 eps -> q1 0
q1 1 0 -> q2 eps
q2 1 0 -> q2 eps
q1 eps $ -> q3 eps
q2 eps $ -> q3 eps# { 0^n 1^n : n >= 0 }
variables: S
terminals: 0 1
start: S
rules:
S -> 0 S 1 | eps# { 0^n 1^n : n >= 0 }
states: q0 q1 q2 q3
alphabet: 0 1
stack: 0 $
start: q0
accept: q0 q3
delta:
q0 eps eps -> q1 $
q1 0 eps -> q1 0
q1 1 0 -> q2 eps
q2 1 0 -> q2 eps
q2 eps $ -> q3 epsErrores
Ejemplos con errores a propósito: no compilan, fallan o dan un resultado incorrecto. Los apuntes explican cada uno.
# No es un archivo .pda válido: la segunda transición quiere poner dos símbolos de una vez.
# Una transición pone un símbolo o ninguno. Para poner dos hace falta un estado intermedio.
states: q0 q1
alphabet: a
stack: x $
start: q0
accept: q1
delta:
q0 eps eps -> q1 $
q1 a eps -> q1 x x# No es un PDA: la última transición saca el símbolo 1, que no está en el alfabeto de la pila.
states: q0 q1 q2
alphabet: 0 1
stack: 0 $
start: q0
accept: q2
delta:
q0 eps eps -> q1 $
q1 0 eps -> q1 0
q1 1 1 -> q2 epsPruebas
Comprueban lo que afirman los apuntes; se ejecutan con make test.
// Pruebas de las construcciones: el PDA de una gramática acepta exactamente lo que la gramática
// genera; la gramática de un PDA genera exactamente lo que el PDA acepta; normalizar no cambia
// el lenguaje; y las construcciones de cierre.
#include <cassert>
#include <cstddef>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#include "cfg.h"
#include "closure.h"
#include "convert.h"
#include "pda.h"
#include "predicates.h"
namespace {
// Las cadenas de longitud a lo sumo n que el autómata acepta.
std::set<std::string> accepted_up_to(const Pda& p, std::size_t n) {
std::set<std::string> result;
for (const std::string& w : all_strings(p.alphabet, n)) {
if (accepts(p, w)) {
result.insert(w);
}
}
return result;
}
// Las cadenas de longitud a lo sumo n que cumplen la función.
std::set<std::string> filter(const std::vector<char>& sigma, std::size_t n,
const std::function<bool(const std::string&)>& expected) {
std::set<std::string> result;
for (const std::string& w : all_strings(sigma, n)) {
if (expected(w)) {
result.insert(w);
}
}
return result;
}
std::set<std::string> intersect(const std::set<std::string>& a, const std::set<std::string>& b) {
std::set<std::string> result;
for (const std::string& w : a) {
if (b.count(w) > 0) {
result.insert(w);
}
}
return result;
}
} // namespace
int main() {
// --- De gramática a PDA -------------------------------------------------------------
struct Case {
std::string name;
std::function<bool(const std::string&)> expected;
std::size_t n;
};
std::vector<Case> grammars = {
{"zeros_ones", is_zeros_ones, 10}, {"balanced", is_balanced, 10}, {"even_palindromes", is_even_palindrome, 10},
{"equal_ab", has_equal_ab, 8}, {"anbn_cm", is_anbn_cm, 7}, {"am_bncn", is_am_bncn, 7},
};
for (const Case& c : grammars) {
Cfg g = load_cfg("machines/" + c.name + ".cfg");
std::set<std::string> generated = strings_up_to(g, c.n);
// La gramática genera el lenguaje que dicen los apuntes…
assert(generated == filter(g.terminals, c.n, c.expected));
// … y el PDA construido acepta exactamente las mismas cadenas.
Pda p = cfg_to_pda(g);
assert(accepted_up_to(p, c.n) == generated);
// Cuatro estados fijos, y k − 1 intermedios por cada regla con k ≥ 2 símbolos a la derecha.
std::size_t states = 4;
for (const Rule& rule : g.rules) {
states += rule.body.size() >= 2 ? rule.body.size() - 1 : 0;
}
assert(p.states.size() == states);
}
// El ejemplo de los apuntes: la gramática de los paréntesis da 7 estados y 10 transiciones,
// y la ejecución de aceptación de () tiene 12 configuraciones.
Pda balanced = cfg_to_pda(load_cfg("machines/balanced.cfg"));
assert(balanced.states.size() == 7 && count_transitions(balanced) == 10);
Search search = simulate(balanced, "()");
assert(search.verdict == Verdict::Accept && search.run.size() == 12);
assert(search.run[6].config.stack == "(S)S$" && search.run[6].config.state == "q_loop");
assert(simulate(balanced, "(()").verdict == Verdict::Reject);
// La gramática de expresiones es recursiva por la izquierda: el PDA tiene configuraciones
// sin fin, y la búsqueda sin tope no puede rechazar. Como la gramática no tiene reglas ε,
// cada símbolo de la pila genera al menos un terminal, y una ejecución de aceptación nunca
// tiene más de |w| + 1 símbolos en la pila (el + 1 es por $). Con ese tope la búsqueda decide.
Cfg expr = load_cfg("machines/expr.cfg");
Pda expr_pda = cfg_to_pda(expr);
assert(expr_pda.states.size() == 10);
std::set<std::string> expressions = strings_up_to(expr, 5);
assert(expressions.size() == 15);
for (const std::string& w : all_strings(expr.terminals, 5)) {
Search bounded = simulate(expr_pda, w, 100000, w.size() + 1);
assert(bounded.verdict != Verdict::Limit);
assert((bounded.verdict == Verdict::Accept) == (expressions.count(w) > 0));
}
// --- Normalizar, y de PDA a gramática --------------------------------------------------
std::vector<std::string> machines = {"zeros_ones", "zeros_ones_norm", "even_palindromes", "balanced",
"equal_ab", "even_ones", "anbn_cm", "ij_or_jk"};
for (const std::string& name : machines) {
Pda p = load_pda("machines/" + name + ".pda");
std::size_t n = p.alphabet.size() == 2 ? 6 : 5;
std::set<std::string> language = accepted_up_to(p, n);
Pda normal = normalize_pda(p);
assert(has_normal_shape(normal));
for (const std::string& w : all_strings(p.alphabet, n)) {
Search run = simulate(normal, w);
assert(run.verdict != Verdict::Limit);
assert((run.verdict == Verdict::Accept) == (language.count(w) > 0));
// Al aceptar, la pila está vacía.
assert(run.verdict != Verdict::Accept || run.run.back().config.stack.empty());
}
Cfg g = pda_to_cfg(normal);
assert(g.variables.size() == normal.states.size() * normal.states.size());
assert(strings_up_to(remove_useless(g), n) == language);
}
// El ejemplo de los apuntes, sin pasar por normalize_pda porque ya está normalizado.
Pda small = load_pda("machines/zeros_ones_norm.pda");
assert(has_normal_shape(small));
assert(!has_normal_shape(load_pda("machines/zeros_ones.pda")));
Cfg from_small = pda_to_cfg(small);
assert(from_small.variables.size() == 16 && from_small.rules.size() == 72);
Cfg useful = remove_useless(from_small);
assert(useful.variables.size() == 6 && useful.rules.size() == 16);
assert(from_small.start == "A(q0,q3)");
// Sin limpiar genera lo mismo: quitar las variables que no sirven no cambia el lenguaje.
assert(strings_up_to(from_small, 10) == filter(small.alphabet, 10, is_zeros_ones));
assert(strings_up_to(useful, 10) == filter(small.alphabet, 10, is_zeros_ones));
// Lo que cada variable genera, como dice la demostración: A(q1,q2) son las cadenas 0^n 1^n con n ≥ 1.
std::map<std::string, std::set<std::string>> table = languages_up_to(from_small, 8);
assert((table["A(q1,q2)"] == std::set<std::string>{"01", "0011", "000111", "00001111"}));
assert(table["A(q1,q1)"] == std::set<std::string>{""});
assert(table["A(q2,q1)"].empty());
// --- Cierre ----------------------------------------------------------------------------
Cfg first = load_cfg("machines/anbn_cm.cfg");
Cfg second = load_cfg("machines/am_bncn.cfg");
std::size_t n = 7;
std::set<std::string> a = strings_up_to(first, n);
std::set<std::string> b = strings_up_to(second, n);
// Unión.
std::set<std::string> both = a;
both.insert(b.begin(), b.end());
assert(strings_up_to(cfg_union(first, second), n) == both);
assert(both == filter(first.terminals, n, is_ij_or_jk));
// Concatenación.
std::set<std::string> products;
for (const std::string& u : a) {
for (const std::string& v : b) {
if (u.size() + v.size() <= n) {
products.insert(u + v);
}
}
}
assert(strings_up_to(cfg_concat(first, second), n) == products);
// Estrella, con { 0^n 1^n }: las concatenaciones de cero o más cadenas del lenguaje.
Cfg zeros_ones = load_cfg("machines/zeros_ones.cfg");
std::set<std::string> base = strings_up_to(zeros_ones, 8);
std::set<std::string> star = {""};
for (bool grew = true; grew;) {
grew = false;
for (const std::string& u : std::set<std::string>(star)) {
for (const std::string& v : base) {
if (u.size() + v.size() <= 8 && star.insert(u + v).second) {
grew = true;
}
}
}
}
assert(strings_up_to(cfg_star(zeros_ones), 8) == star);
assert(star.count("0101") > 0 && star.count("010011") > 0 && star.count("0110") == 0);
// La intersección de los dos lenguajes libres de contexto es { a^n b^n c^n }.
assert(intersect(a, b) == filter(first.terminals, n, is_anbncn));
assert(intersect(a, b) == (std::set<std::string>{"", "abc", "aabbcc"}));
std::cout << "test_convert: ok (7 gramáticas a PDA, 8 autómatas normalizados y pasados a gramática)\n";
}// Pruebas de la parte opcional: el parser descendente recursivo acepta exactamente las cadenas
// de tokens que genera la gramática machines/expr.cfg, respeta la precedencia y lee cada token
// una vez.
#include <cassert>
#include <cstddef>
#include <iostream>
#include <set>
#include <stdexcept>
#include <string>
#include <vector>
#include "cfg.h"
#include "expr.h"
#include "pda.h"
namespace {
// Una cadena sobre {a, +, *, (, )} como lista de tokens: cada a es un número.
std::vector<Token> tokens_of(const std::string& w) {
std::vector<Token> tokens;
for (std::size_t i = 0; i < w.size(); i++) {
switch (w[i]) {
case 'a': tokens.push_back({TokenKind::Number, "1", i}); break;
case '+': tokens.push_back({TokenKind::Plus, "+", i}); break;
case '*': tokens.push_back({TokenKind::Star, "*", i}); break;
case '(': tokens.push_back({TokenKind::LParen, "(", i}); break;
default: tokens.push_back({TokenKind::RParen, ")", i}); break;
}
}
tokens.push_back({TokenKind::End, "", w.size()});
return tokens;
}
bool parses(const std::vector<Token>& tokens) {
try {
parse(tokens);
} catch (const std::runtime_error&) {
return false;
}
return true;
}
Parsed evaluate(const std::string& text) {
return parse(lex(text));
}
} // namespace
int main() {
// El parser y la gramática coinciden en todas las cadenas de tokens de longitud a lo sumo 6.
Cfg g = load_cfg("machines/expr.cfg");
std::size_t n = 6;
std::set<std::string> generated = strings_up_to(g, n);
std::size_t total = 0;
for (const std::string& w : all_strings(g.terminals, n)) {
assert(parses(tokens_of(w)) == (generated.count(w) > 0));
total++;
}
// El lexer.
std::vector<Token> tokens = lex(" 12+(3 *45) ");
assert(tokens.size() == 8);
assert(tokens[0].kind == TokenKind::Number && tokens[0].text == "12" && tokens[0].pos == 1);
assert(tokens[5].kind == TokenKind::Number && tokens[5].text == "45");
assert(tokens[7].kind == TokenKind::End);
assert(lex("").size() == 1);
// Precedencia y agrupación: los ejemplos de los apuntes.
assert(evaluate("2 + 3 * 4").value == 14 && evaluate("2 + 3 * 4").tree == "(2 + (3 * 4))");
assert(evaluate("(2 + 3) * 4").value == 20 && evaluate("(2 + 3) * 4").tree == "((2 + 3) * 4)");
assert(evaluate("2 + 3 + 4").tree == "((2 + 3) + 4)");
assert(evaluate("2 * 3 * 4").tree == "((2 * 3) * 4)");
assert(evaluate("((7))").value == 7 && evaluate("((7))").tree == "7");
assert(evaluate("2*(3+4)*5+1").value == 71);
// Tiempo lineal: la cantidad de llamadas se cuenta a partir de los tokens, sin retroceder.
// Son 3 por la expresión completa y por cada paréntesis que abre, 2 por cada + y 1 por cada *.
for (const std::string& w : generated) {
std::size_t calls = 0;
parse(tokens_of(w), &calls);
std::size_t open = 0;
std::size_t plus = 0;
std::size_t star = 0;
for (char c : w) {
open += c == '(';
plus += c == '+';
star += c == '*';
}
assert(calls == 3 * (1 + open) + 2 * plus + star);
assert(calls <= 3 * w.size());
}
// Errores.
for (const std::string text : {"", "2 +", "+ 2", "2 + * 3", "(2 + 3", "2 3", "()", "2 )"}) {
assert(!parses(lex(text)));
}
bool thrown = false;
try {
lex("2 $ 3");
} catch (const std::runtime_error&) {
thrown = true;
}
assert(thrown);
std::cout << "test_expr: ok (" << total << " cadenas de tokens contra la gramática)\n";
}// Pruebas de la sesión A: cada autómata de machines/ contra una función que decide el mismo
// lenguaje mirando la cadena completa, las ejecuciones copiadas en los apuntes, y los tres
// finales de la búsqueda (acepta, rechaza, límite).
#include <cassert>
#include <cstddef>
#include <functional>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
#include "cfg.h"
#include "convert.h"
#include "pda.h"
#include "predicates.h"
namespace {
// Compara el autómata con la función en todas las cadenas de longitud a lo sumo n.
std::size_t check_language(const std::string& path, const std::function<bool(const std::string&)>& expected,
std::size_t n) {
Pda p = load_pda(path);
std::size_t total = 0;
for (const std::string& w : all_strings(p.alphabet, n)) {
assert(accepts(p, w) == expected(w));
total++;
}
return total;
}
std::vector<std::string> states_of(const std::vector<Step>& run) {
std::vector<std::string> states;
for (const Step& step : run) {
states.push_back(step.config.state);
}
return states;
}
bool throws(const std::string& path) {
try {
load_pda(path);
} catch (const std::runtime_error&) {
return true;
}
return false;
}
} // namespace
int main() {
// Cada autómata reconoce el lenguaje que dicen los apuntes.
std::size_t strings = 0;
strings += check_language("machines/zeros_ones.pda", is_zeros_ones, 10);
strings += check_language("machines/zeros_ones_norm.pda", is_zeros_ones, 10);
strings += check_language("machines/even_palindromes.pda", is_even_palindrome, 10);
strings += check_language("machines/balanced.pda", is_balanced, 10);
strings += check_language("machines/equal_ab.pda", has_equal_ab, 10);
strings += check_language("machines/even_ones.pda", has_even_ones, 10);
strings += check_language("machines/anbn_cm.pda", is_anbn_cm, 8);
strings += check_language("machines/ij_or_jk.pda", is_ij_or_jk, 8);
// El intento de reconocer a^n b^n c^n acepta de más: no compara las c con nada.
Pda attempt = load_pda("machines/anbn_cm.pda");
assert(accepts(attempt, "aabbcc"));
assert(accepts(attempt, "aabbc"));
assert(accepts(attempt, "aabbccccc"));
assert(!is_anbncn("aabbc"));
// La ejecución de 0011 que está en los apuntes: 7 configuraciones, y la pila sube y baja.
Pda zeros_ones = load_pda("machines/zeros_ones.pda");
Search search = simulate(zeros_ones, "0011");
assert(search.verdict == Verdict::Accept);
assert((states_of(search.run) == std::vector<std::string>{"q0", "q1", "q1", "q1", "q2", "q2", "q3"}));
std::vector<std::string> stacks;
for (const Step& step : search.run) {
stacks.push_back(step.config.stack);
}
assert((stacks == std::vector<std::string>{"", "$", "0$", "00$", "0$", "$", ""}));
assert(search.explored == 7);
// Con ε acepta sin moverse, porque q0 está en F. Con 001 y con 10 rechaza.
assert(simulate(zeros_ones, "").run.size() == 1);
assert(simulate(zeros_ones, "001").verdict == Verdict::Reject);
assert(simulate(zeros_ones, "001").explored == 5);
assert(simulate(zeros_ones, "10").explored == 2);
// 0011 seguido de más símbolos: llega a q3 antes de terminar de leer, y eso no es aceptar.
assert(!accepts(zeros_ones, "00110"));
assert(!accepts(zeros_ones, "0101"));
// Los palíndromos: la ejecución de aceptación de 0110 adivina el medio después de dos símbolos.
Pda palindromes = load_pda("machines/even_palindromes.pda");
search = simulate(palindromes, "0110");
assert(search.verdict == Verdict::Accept);
assert((states_of(search.run) == std::vector<std::string>{"q0", "q1", "q1", "q1", "q2", "q2", "q2", "q3"}));
assert(search.run[4].read == EPS && search.run[4].config.pos == 2);
assert(search.explored == 15);
assert(simulate(palindromes, "011").verdict == Verdict::Reject);
assert(simulate(palindromes, "011").explored == 11);
// Aceptar es por estado: la pila no tiene que estar vacía.
Pda keeps;
keeps.states = {"q0", "q1"};
keeps.alphabet = {'a'};
keeps.stack = {'x'};
keeps.start = "q0";
keeps.accept = {"q1"};
add_move(keeps, "q0", 'a', EPS, "q1", 'x');
add_move(keeps, "q1", 'a', EPS, "q1", 'x');
search = simulate(keeps, "aaa");
assert(search.verdict == Verdict::Accept && search.run.back().config.stack == "xxx");
assert(!accepts(keeps, ""));
// Un ciclo de transiciones ε que no cambia la pila: la búsqueda termina gracias al conjunto
// de configuraciones vistas, y rechaza.
Pda cycle;
cycle.states = {"q0", "q1", "q2"};
cycle.alphabet = {'a'};
cycle.stack = {'x'};
cycle.start = "q0";
cycle.accept = {"q2"};
add_move(cycle, "q0", EPS, EPS, "q1", EPS);
add_move(cycle, "q1", EPS, EPS, "q0", EPS);
add_move(cycle, "q1", 'a', EPS, "q2", EPS);
search = simulate(cycle, "");
assert(search.verdict == Verdict::Reject && search.explored == 2);
assert(accepts(cycle, "a"));
assert(!accepts(cycle, "aa"));
// Un ciclo de transiciones ε que hace crecer la pila: las configuraciones no se acaban.
Pda grows;
grows.states = {"q0", "q1"};
grows.alphabet = {'a'};
grows.stack = {'x'};
grows.start = "q0";
grows.accept = {"q1"};
add_move(grows, "q0", EPS, EPS, "q0", 'x');
add_move(grows, "q0", 'a', EPS, "q1", EPS);
search = simulate(grows, "", 1000);
assert(search.verdict == Verdict::Limit && search.explored == 1001);
// La búsqueda por niveles sí encuentra la aceptación, que está a un paso.
assert(simulate(grows, "a", 1000).verdict == Verdict::Accept);
// El PDA de la gramática de expresiones tiene uno de esos ciclos, por la regla E → E + T.
Pda expr = cfg_to_pda(load_cfg("machines/expr.cfg"));
assert(simulate(expr, "a+a", 5000).verdict == Verdict::Accept);
assert(simulate(expr, "a+", 5000).verdict == Verdict::Limit);
// Leer y escribir: lo que write_pda escribe se vuelve a leer igual.
for (const std::string name : {"zeros_ones", "even_palindromes", "balanced", "equal_ab", "ij_or_jk"}) {
Pda p = load_pda("machines/" + name + ".pda");
std::stringstream text;
write_pda(text, p);
Pda again = read_pda(text);
assert(again.states == p.states && again.alphabet == p.alphabet && again.stack == p.stack);
assert(again.start == p.start && again.accept == p.accept && again.delta == p.delta);
}
assert(load_pda("machines/even_ones.pda").stack.empty());
assert(count_transitions(load_pda("machines/ij_or_jk.pda")) == 14);
// Las descripciones de errors/ no son un PDA.
assert(throws("errors/two_symbols.pda"));
assert(throws("errors/unknown_stack_symbol.pda"));
std::cout << "test_pda: ok (8 autómatas, " << strings << " cadenas en total)\n";
}// Pruebas de la sesión B: los análisis por casos de los apuntes, comprobados división por
// división con p pequeños. Cada demostración dice qué exponente usar en cada caso; aquí se
// revisa que ese exponente saca la cadena del lenguaje en todas las divisiones del caso.
#include <cassert>
#include <cstddef>
#include <iostream>
#include <set>
#include <string>
#include "pumping.h"
namespace {
std::string repeat(char c, std::size_t n) {
return std::string(n, c);
}
// v o y tienen dos símbolos distintos: abarcan el borde entre dos bloques.
bool straddles(const std::string& part) {
return std::set<char>(part.begin(), part.end()).size() >= 2;
}
std::string v_of(const std::string& s, const Division& d) {
return s.substr(d.u, d.v);
}
std::string y_of(const std::string& s, const Division& d) {
return s.substr(d.u + d.v + d.x, d.y);
}
} // namespace
int main() {
// pump y divisions hacen lo que dicen.
Division d = {1, 1, 2, 1}; // a | b | cd | e | f
assert(pump("abcdef", d, 0) == "acdf");
assert(pump("abcdef", d, 1) == "abcdef");
assert(pump("abcdef", d, 3) == "abbbcdeeef");
for (const Division& each : divisions("abcdef", 3)) {
assert(each.v + each.y > 0 && each.v + each.x + each.y <= 3);
assert(pump("abcdef", each, 1) == "abcdef");
}
assert(divisions("abc", 1).size() == 6);
std::size_t checked = 0;
for (std::size_t p = 1; p <= 7; p++) {
// { a^n b^n c^n } con s = a^p b^p c^p: en los dos casos sirve i = 2.
std::string s = repeat('a', p) + repeat('b', p) + repeat('c', p);
for (const Division& each : divisions(s, p)) {
assert(!is_anbncn(pump(s, each, 2)));
checked++;
}
// { a^i b^j c^k : i ≤ j ≤ k } con la misma s.
for (const Division& each : divisions(s, p)) {
std::string v = v_of(s, each);
std::string y = y_of(s, each);
std::string vy = v + y;
if (straddles(v) || straddles(y)) {
assert(!is_ordered_abc(pump(s, each, 2))); // caso 1: queda desordenada
} else if (vy.find('a') == std::string::npos) {
assert(!is_ordered_abc(pump(s, each, 0))); // caso 2a: sin a, hacia abajo
} else {
assert(!is_ordered_abc(pump(s, each, 2))); // caso 2b: con a, hacia arriba
}
checked++;
}
// Bombear solo hacia arriba no alcanza: hay divisiones que con i = 2 siguen en el lenguaje.
PumpReport ordered = pump_report(is_ordered_abc, s, p);
assert(ordered.out_with_0 > 0 && ordered.survive == 0);
assert(ordered.out_with_2 + ordered.out_with_0 == ordered.total);
// { ww } con s = 0^p 1^p 0^p 1^p.
std::string t = repeat('0', p) + repeat('1', p) + repeat('0', p) + repeat('1', p);
for (const Division& each : divisions(t, p)) {
if (straddles(v_of(t, each)) || straddles(y_of(t, each))) {
assert(!is_ww(pump(t, each, 0))); // caso 2: v o y abarca dos bloques, hacia abajo
} else {
assert(!is_ww(pump(t, each, 2))); // caso 1: cada una dentro de un bloque, hacia arriba
}
checked++;
}
// { ww } con la mala elección s = 0^p 1 0^p 1: desde p = 3 el adversario tiene una
// división que sobrevive, la de los apuntes.
if (p >= 3) {
std::string bad = repeat('0', p) + "1" + repeat('0', p) + "1";
Division escape = {p - 1, 1, 1, 1}; // u = 0^(p-1), v = 0, x = 1, y = 0
assert(v_of(bad, escape) == "0" && y_of(bad, escape) == "0");
for (std::size_t i = 0; i <= 8; i++) {
assert(is_ww(pump(bad, escape, i)));
}
assert(pump_report(is_ww, bad, p).survive > 0);
}
// { 0^n 1^n } sí es libre de contexto: para p ≥ 2 alguna división sobrevive.
if (p >= 2) {
std::string zeros_ones = repeat('0', p) + repeat('1', p);
Division middle = {p - 1, 1, 0, 1}; // v = 0, y = 1, pegados al medio
for (std::size_t i = 0; i <= 8; i++) {
assert(is_zeros_ones(pump(zeros_ones, middle, i)));
}
}
}
// Los números de la tabla de los apuntes, con p = 6.
PumpReport report = pump_report(is_anbncn, repeat('a', 6) + repeat('b', 6) + repeat('c', 6), 6);
assert(report.total == 1106 && report.out_with_2 == 1106);
report = pump_report(is_ordered_abc, repeat('a', 6) + repeat('b', 6) + repeat('c', 6), 6);
assert(report.out_with_2 == 843 && report.out_with_0 == 263);
report = pump_report(is_ww, repeat('0', 6) + repeat('1', 6) + repeat('0', 6) + repeat('1', 6), 6);
assert(report.total == 1568 && report.survive == 0);
// El lema de los cuatro bloques: si 0^a 1^b 0^c 1^d = ww con a, b, c, d ≥ 1, entonces a = c y b = d.
for (std::size_t a = 1; a <= 6; a++) {
for (std::size_t b = 1; b <= 6; b++) {
for (std::size_t c = 1; c <= 6; c++) {
for (std::size_t e = 1; e <= 6; e++) {
std::string w = repeat('0', a) + repeat('1', b) + repeat('0', c) + repeat('1', e);
assert(is_ww(w) == (a == c && b == e));
}
}
}
}
std::cout << "test_pumping: ok (" << checked << " divisiones revisadas caso por caso)\n";
}Laboratorio
Archivos de partida del laboratorio de la semana.
TIEMPO = 2
include ../../../lab.mk# Un simulador de PDA
Este problema es opcional: la sesión de laboratorio de la semana 6 es para la práctica. Vale la pena hacerlo
igual, porque es la primera vez que simulan una máquina **no determinista** que además tiene memoria sin límite.
El programa recibe la descripción de un autómata de pila (PDA) y una lista de cadenas, y dice por cada cadena
si el autómata la acepta.
Un PDA es $P = (Q, \Sigma, \Gamma, \delta, q_0, F)$. En cada instante está en una **configuración**: el estado,
cuántos símbolos de la entrada ya leyó, y el contenido de la pila. Empieza en el estado $q_0$, sin haber leído
nada y con la pila vacía. Una transición `p a b -> r c` se puede usar desde una configuración con estado $p$ si
- `a` es `eps`, o es el siguiente símbolo de la entrada, que entonces queda leído; y
- `b` es `eps`, o es el símbolo de la cima de la pila, que entonces se saca.
Después de usarla, el estado es $r$ y, si `c` no es `eps`, el símbolo `c` queda en la cima de la pila. Con la
pila vacía solo se pueden usar las transiciones que sacan `eps`.
El PDA **acepta** la cadena si alguna secuencia de transiciones lo lleva a una configuración con toda la
entrada leída y el estado en $F$. La pila no tiene que quedar vacía. Como desde una configuración puede haber
varias transiciones posibles, o ninguna, no basta con seguir un camino: hay que **buscar** entre todas las
configuraciones alcanzables.
## Entrada
La descripción de un PDA en el formato `.pda` de [`code/formats.md`](../../../formats.md), seguida del bloque
de cadenas del mismo documento:
```text
# { 0^n 1^n : n >= 0 }
states: q0 q1 q2 q3
alphabet: 0 1
stack: 0 $
start: q0
accept: q0 q3
delta:
q0 eps eps -> q1 $
q1 0 eps -> q1 0
q1 1 0 -> q2 eps
q2 1 0 -> q2 eps
q2 eps $ -> q3 eps
strings: 4
0011
001
10
```
- 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:`, `stack:`, `start:`, `accept:` y `delta:` vienen siempre en ese orden. `accept:` puede
no tener ningún estado, y `stack:` puede no tener ningún símbolo.
- Después de `delta:` hay una transición por línea, `estado lee saca -> destino pone`, en cualquier orden.
`lee` es un símbolo de `alphabet` o `eps`; `saca` y `pone` son un símbolo de `stack` o `eps`. Puede no haber
ninguna transición, puede haber varias con el mismo lado izquierdo, y una misma línea puede estar repetida.
- `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, con una de tres palabras. Sea $L = 10\,000$ el **límite de
configuraciones**.
- `acepta` si alguna configuración alcanzable desde la inicial es de aceptación.
- `rechaza` si ninguna lo es y las configuraciones alcanzables distintas son a lo sumo $L$.
- `limite` si ninguna lo es y las configuraciones alcanzables distintas son más de $L$.
Dos configuraciones son la misma si tienen el mismo estado, la misma posición en la entrada y la misma pila. La
configuración inicial cuenta.
En la práctica: su programa explora las configuraciones recordando las que ya vio. Si encuentra una de
aceptación, imprime `acepta` y pasa a la cadena siguiente. Si se le acaban las configuraciones por explorar,
imprime `rechaza`. Si llega a tener **más de $L$ configuraciones distintas** vistas sin haber aceptado, deja de
buscar e imprime `limite`. Con exactamente $L$ todavía no se detiene.
El límite existe porque un PDA puede tener un ciclo de transiciones `eps` que hace crecer la pila, como
`q eps eps -> q x`. Desde ahí hay infinitas configuraciones, una por cada altura de la pila, y una búsqueda
sin límite no terminaría nunca.
**Garantía.** En todos los casos del juez, una cadena que el autómata acepta tiene a lo sumo $L$
configuraciones alcanzables. Por eso la respuesta no depende del orden en que exploren: si la cadena se acepta,
cualquier búsqueda encuentra la aceptación antes de pasar del límite, y si no se acepta, lo que cuenta es
cuántas configuraciones hay, y eso no depende del orden.
## Límites
- $1 \leq |Q| \leq 200$, $1 \leq |\Sigma| \leq 30$ y $0 \leq |\Gamma| \leq 30$. A lo sumo 2000 transiciones.
- El nombre de un estado tiene entre 1 y 20 caracteres visibles, sin espacios. No empieza con `#`, no termina
con `:` y no es `eps`. Un nombre puede ser prefijo de otro (`q1` y `q10`), y puede ser igual a un símbolo (un
estado `0`, un estado `$`).
- Un símbolo, de la entrada o de la pila, es un solo carácter visible distinto de `#`. Un mismo carácter puede
estar en los dos alfabetos.
- $1 \leq k \leq 100$, y cada cadena tiene a lo sumo 200 símbolos, todos del alfabeto de entrada.
- La entrada siempre describe un PDA válido: no tienen que detectar errores en la descripción.
## Ejemplo
Para la entrada de arriba, la salida es:
```text
acepta
acepta
rechaza
rechaza
```
Con `0011` el autómata marca el fondo de la pila con `$`, guarda los dos ceros, los saca con los dos unos y,
al ver otra vez `$`, pasa a `q3`. La segunda cadena es la vacía: el estado inicial `q0` es de aceptación, y
no hace falta moverse. Con `001` sobra un cero en la pila y `q2` no puede pasar a `q3`. Con `10` no hay ningún
cero que sacar cuando llega el `1`.
Un ejemplo con las tres respuestas. Es el autómata del caso `casos/10.in`, con tres de sus cadenas: el de
arriba, ahora con `q3` como único estado de aceptación y con un estado `loco` al que se llega leyendo una `c`.
```text
states: q0 q1 q2 q3 loco
alphabet: 0 1 c
stack: 0 $ x
start: q0
accept: q3
delta:
q0 eps eps -> q1 $
q1 0 eps -> q1 0
q1 1 0 -> q2 eps
q2 1 0 -> q2 eps
q2 eps $ -> q3 eps
q1 c eps -> loco eps
q2 c eps -> loco eps
loco eps eps -> loco x
strings: 3
0011
0c
001
```
```text
acepta
limite
rechaza
```
Con `0c` el autómata llega a `loco`, que pone una `x` tras otra: hay una configuración distinta por cada altura
de la pila, y ninguna es de aceptación. Con `0011` y con `001` nunca se lee una `c`, así que `loco` no se
alcanza y las configuraciones son pocas.
## Tiempo
2 segundos por caso. Se compila con `g++ -Wall -Wextra -std=c++20 -O2`.
Hay dos maneras de hacerlo mal, y los casos traen las dos.
**Sin recordar las configuraciones vistas, la búsqueda puede no terminar.** Un ciclo de transiciones `eps` que
no cambia la pila, como `p eps eps -> q eps` junto con `q eps eps -> p eps`, vuelve a la misma configuración.
Los casos 06 y 07 tienen ciclos así.
**Recordar solo el camino actual no alcanza.** Una búsqueda en profundidad que evita repetir configuraciones
dentro del camino que está siguiendo sí termina, pero vuelve a explorar una configuración cada vez que llega a
ella por un camino distinto. En el caso 15, cada `a` se puede leer de tres maneras y muchas de ellas terminan
en la misma configuración: para `a^30` hay $3^{30}$ caminos y menos de 4000 configuraciones. En el caso 16 son
$2^{100}$ caminos y unas 700 configuraciones. Con un conjunto de configuraciones vistas, compartido por toda
la búsqueda de una cadena, cada configuración se explora una sola vez, y el juez deja de dar `TLE`. Además, sin
ese conjunto no hay cómo contar las configuraciones distintas, que es lo que pide el límite.
Con los límites de arriba alcanza la representación directa: una configuración con una copia de su pila en un
`std::string`, y las vistas en un `std::set`. En el peor caso son 10 001 configuraciones por cadena, con pilas
de hasta 10 001 símbolos.
## Qué se practica aquí
En `code/week-06/pda.h` hay un `struct Pda` y una función `simulate` que hace esta búsqueda: es lo que usan los
ejemplos de los apuntes, y pueden leerla cuanto quieran. `solution.cpp` se escribe **sin incluir `pda.h`**: el
juez compila ese único archivo, y el lector de `pda.h` no entiende el bloque `strings:`. El trabajo está en
tres cosas.
- **Qué es una configuración y cuándo dos son la misma.** Estado, posición y pila completa. Dos caminos que
llegan al mismo estado y a la misma posición con pilas distintas no se pueden juntar.
- **Qué transiciones se pueden usar** desde una configuración: las cuatro combinaciones de leer o no leer y de
sacar o no sacar. Con la entrada terminada solo quedan las que leen `eps`, y con la pila vacía las que sacan
`eps`.
- **Cuándo detenerse**: al aceptar, al quedarse sin configuraciones o al pasar del límite.
Los casos traen, entre otros: la cadena vacía, un PDA sin estados de aceptación, uno sin transiciones y sin
símbolos de pila, uno que acepta con la pila sin vaciar, uno sin marca de fondo que intenta sacar de la pila
vacía, estados inalcanzables, nombres iguales a los símbolos, ciclos de transiciones `eps` de los dos tipos, y
dos autómatas casi iguales que con la misma cadena tienen exactamente 10 000 y 10 001 configuraciones.
## Cómo avanzar
```sh
make # compila solution.cpp en build/
make test # corre el juez con todos los casos
```
1. Lean la descripción y las cadenas. Empiecen con `casos/01.in`. Lean por líneas, con `std::getline`: una
línea vacía es la cadena $\varepsilon$, y `>>` se la salta.
2. Representen el autómata con los seis componentes de la definición, con los mismos nombres: `states`,
`alphabet`, `stack`, `delta`, `start` y `accept`. El esqueleto trae un `struct Pda` y un `struct Config` con
una propuesta de tipos.
3. Escriban la búsqueda con el conjunto de configuraciones vistas. Por niveles o en profundidad: la respuesta
es la misma. Pasen primero los casos 01 a 09, que no llegan al límite.
4. Agreguen el límite y pasen los casos 10 a 14. Antes de correr el juez, respondan a mano con el caso 12: si
con cada `a` el autómata pone un `0` o un `1`, ¿cuántas configuraciones alcanzables hay después de 12
símbolos? ¿Y después de 13?
5. Escriban ustedes, en el mismo formato, el PDA de los palíndromos de longitud par sobre
$\{\mathtt{a}, \mathtt{b}\}$, y pruébenlo con su simulador:
```sh
{ cat palindromos.pda; printf 'strings: 4\nabba\n\naba\nabab\n'; } | build/solution
```
Debe imprimir `acepta`, `acepta`, `rechaza`, `rechaza`. Después prueben los autómatas de la clase, que
están en `../../machines/`: a un archivo `.pda` le falta solo el bloque de cadenas.
Mientras desarrollan, compilen con sanitizers, como explica [`labs/README.md`](../../../../labs/README.md).
## Para seguir
Opcional, sin casos en el juez.
- Cambien el PDA de los palíndromos para que acepte también los de longitud impar. ¿Cuántas transiciones
agregaron?
- Con `build/cfg_to_pda` de la carpeta de la semana, conviertan la gramática `../../machines/expr.cfg` en un
PDA y denle a su simulador las cadenas `a+a*a` y `a+`. ¿Por qué la segunda responde `limite` y no `rechaza`?
¿Qué regla de la gramática produce el ciclo que hace crecer la pila?
- Cuando acepta, hagan que su programa imprima además una ejecución de aceptación: la secuencia de
configuraciones desde la inicial. Hace falta guardar, para cada configuración, desde cuál se llegó a ella.
- Las pilas de dos configuraciones vecinas se diferencian solo en la cima. En lugar de copiar la pila en cada
configuración, guarden cada pila distinta una sola vez, como un par (símbolo de la cima, pila de debajo), y
que la configuración lleve solo su número. ¿Cuánta memoria usa ahora el caso 11?// Un simulador de PDA. Lee la descripción de un autómata de pila y una lista de cadenas, e
// imprime por cada cadena acepta, rechaza o limite.
#include <cstddef>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
const std::size_t LIMIT = 10000; // el límite de configuraciones del enunciado
// Los seis componentes de P = (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 su
// lista, y -1 quiere decir ε. Pueden cambiarlos.
struct Transition {
int read = -1; // posición en alphabet, o -1 si no lee
int pop = -1; // posición en stack, o -1 si no saca
int target = 0; // posición en states
int push = -1; // posición en stack, o -1 si no pone
};
struct Pda {
std::vector<std::string> states; // Q: los nombres, en el orden de la entrada
std::vector<char> alphabet; // Σ
std::vector<char> stack; // Γ
std::vector<std::vector<Transition>> delta; // δ: delta[i] son las transiciones que salen de states[i]
int start = 0; // q0, como posición en states
std::vector<bool> accept; // F: accept[i] dice si states[i] es de aceptación
};
// Una configuración: el estado, cuántos símbolos de la entrada ya se leyeron, y la pila.
struct Config {
int state = 0;
std::size_t pos = 0;
std::string stack; // la cima es el último carácter
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Pda p;
std::string line;
// Por hacer: leer la descripción línea por línea con std::getline, hasta la línea strings:.
// Después, por cada cadena (una línea vacía es ε), buscar entre las configuraciones
// alcanzables desde (q0, 0, pila vacía) una de aceptación, recordando las ya vistas, y
// responder acepta, rechaza o limite.
while (std::getline(std::cin, line)) {
}
// Este esqueleto no imprime nada, así que el juez da WA en todos los casos.
return 0;
}Compilación
Cómo se compilan y ejecutan los ejemplos.
# Semana 6: autómatas de pila, su equivalencia con las gramáticas y el lema de bombeo para
# lenguajes libres de contexto.
# 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 y las gramáticas de machines/ y de errors/, así que se corren
# desde esta carpeta. El laboratorio está en lab/pda_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 = show_pda run_pda cfg_to_pda normalize_pda pda_to_cfg cfg_strings pump_demo parse_expr
TESTS = test_pda test_convert test_pumping test_expr
HEADERS = pda.h cfg.h convert.h closure.h print.h pumping.h predicates.h expr.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)