Namespace mata::nfa::plumbing

namespace plumbing

Wrappers around various support functions.

Functions

inline void get_elements(StateSet *element_set, const BoolVector &bool_vec)
inline void complement(Nfa *result, const Nfa &aut, const Alphabet &alphabet, const ParameterMap &params = {{"algorithm", "classical"}, {"minimize", "false"}})
inline void minimize(Nfa *res, const Nfa &aut, const ParameterMap &params = {{"algorithm", "brzozowski"}})
inline void determinize(Nfa *result, const Nfa &aut, std::unordered_map<StateSet, State> *subset_map = nullptr)
inline void reduce(Nfa *result, const Nfa &aut, StateRenaming *state_renaming = nullptr, const ParameterMap &params = {{"algorithm", "simulation"}})
inline void revert(Nfa *result, const Nfa &aut)
inline void remove_epsilon(Nfa *result, const Nfa &aut, Symbol epsilon = EPSILON)
template<class ParsedObject>
void construct(Nfa *result, const ParsedObject &parsed, Alphabet *alphabet = nullptr, NameStateMap *state_map = nullptr)

Loads an automaton from Parsed object.

inline void union_nondet(Nfa *unionAutomaton, const Nfa &lhs, const Nfa &rhs)
inline void intersection(Nfa *res, const Nfa &lhs, const Nfa &rhs, Symbol first_epsilon = EPSILON, std::unordered_map<std::pair<State, State>, State> *prod_map = nullptr)

Compute intersection of two NFAs.

Both automata can contain ε-transitions. The product preserves the ε-transitions, i.e., for each each product state (s, t) withs -ε-> p, (s, t) -ε-> (p, t) is created, and vice versa.

Automata must share alphabets.

Parameters:

  • res – [out] The resulting intersection NFA.

  • lhs – [in] Input NFA.

  • rhs – [in] Input NFA.

  • first_epsilon – [in] smallest epsilon.

  • prod_map – [out] Mapping of pairs of the original states (lhs_state, rhs_state) to new product states (not used internally, allocated only when !=nullptr, expensive).

Returns:

NFA as a product of NFAs lhs and rhs with ε-transitions preserved.

inline void concatenate(Nfa *res, const Nfa &lhs, const Nfa &rhs, bool use_epsilon = false, StateRenaming *lhs_result_state_renaming = nullptr, StateRenaming *rhs_result_state_renaming = nullptr)

Concatenate two NFAs.

Parameters:

  • lhs_result_state_renaming – [out] Map mapping lhs states to result states.

  • rhs_result_state_renaming – [out] Map mapping rhs states to result states.

inline void reduce_residual_with(Nfa *res, const Nfa &nfa)

Reduce NFA using residual construction.

The residual construction of the residual automaton and the removal of the covering states is done during the last determinization.

Similar performance to reduce_residual_after(). The output is almost the same except the transitions: transitions may slightly differ, but the number of states is the same for both algorithm types.

inline void reduce_residual_after(Nfa *res, const Nfa &nfa)

Reduce NFA using residual construction.

The residual construction of the residual automaton and the removal of the covering states is done after the final determinization.

Similar performance to reduce_residual_with(). The output is almost the same except the transitions: transitions may slightly differ, but the number of states is the same for both algorithm types.