// El NFA de "el k-ésimo símbolo desde el final es 1", con k + 1 estados.
#ifndef KTH_H
#define KTH_H

#include <string>

#include "nfa.h"

// q0 espera y, al leer un 1, puede adivinar que ese es el k-ésimo desde el final y pasar a q1.
// De q1 a qk se avanza con cualquier símbolo, y de qk no sale nada.
// Con k = 3 es la máquina de machines/third_from_end.nfa.
inline Nfa kth_from_end(int k) {
    Nfa n;
    n.alphabet = {'0', '1'};
    for (int i = 0; i <= k; i++) {
        n.states.push_back("q" + std::to_string(i));
    }
    n.start = "q0";
    n.accept = {"q" + std::to_string(k)};
    n.delta[{"q0", '0'}] = {"q0"};
    n.delta[{"q0", '1'}] = {"q0", "q1"};
    for (int i = 1; i < k; i++) {
        n.delta[{n.states[i], '0'}] = {n.states[i + 1]};
        n.delta[{n.states[i], '1'}] = {n.states[i + 1]};
    }
    return n;
}

#endif
