40 lines
1.2 KiB
C++
40 lines
1.2 KiB
C++
#pragma once
|
|
#include <functional>
|
|
#include <utility>
|
|
#include <vector>
|
|
using std::function;
|
|
using std::pair;
|
|
using std::vector;
|
|
|
|
typedef pair<long, long> Label;
|
|
typedef pair<Label, long> Edge;
|
|
|
|
const Label epsilon{-1L, 0L};
|
|
|
|
struct Fsa {
|
|
long start;
|
|
vector<long> finals; // sorted
|
|
vector<vector<Edge>> adj; // sorted
|
|
|
|
void check() const;
|
|
long n() const { return adj.size(); }
|
|
bool is_final(long x) const;
|
|
bool has(long u, long c) const;
|
|
bool has_call(long u) const;
|
|
bool has_call_or_collapse(long u) const;
|
|
long transit(long u, long c) const;
|
|
void epsilon_closure(vector<long>& src) const;
|
|
Fsa operator~() const;
|
|
// a -> a
|
|
void accessible(const vector<long>* starts, function<void(long)> relate);
|
|
// a -> a
|
|
void co_accessible(const vector<bool>* final, function<void(long)> relate);
|
|
// DFA -> DFA -> DFA
|
|
Fsa intersect(const Fsa& rhs, function<void(long, long)> relate) const;
|
|
// DFA -> DFA -> DFA
|
|
Fsa difference(const Fsa& rhs, function<void(long)> relate) const;
|
|
// DFA -> DFA
|
|
Fsa distinguish(function<void(vector<long>&)> relate) const;
|
|
// * -> DFA
|
|
Fsa determinize(const vector<long>* starts, function<void(long, const vector<long>&)> relate) const;
|
|
};
|