Namespace mata::nfa::builder

namespace builder

Namespace providing options to build NFAs.

Typedefs

using NameStateMap = std::unordered_map<std::string, State>

Functions

Nfa create_single_word_nfa(const std::vector<Symbol> &word)

Create an automaton accepting only a single word.

Nfa create_single_word_nfa(const std::vector<std::string> &word, Alphabet *alphabet = nullptr)

Create an automaton accepting only a single word.

Parameters:

  • word – Word to accept.

  • alphabet – Alphabet to use in NFA for translating word into symbols. If specified, the alphabet has to contain translations for all of the word symbols. If left empty, a new alphabet with only the symbols of the word will be created.

Nfa create_empty_string_nfa()

Create automaton accepting only epsilon string.

Nfa create_sigma_star_nfa(Alphabet *alphabet = new OnTheFlyAlphabet{})

Create automaton accepting sigma star over the passed alphabet.

Parameters:

alphabet – [in] Alphabet to construct sigma star automaton with. When alphabet is left empty, the default empty alphabet is used, creating an automaton accepting only the empty string.

Nfa create_random_nfa_tabakov_vardi(const size_t num_of_states, const size_t alphabet_size, const double states_trans_ratio_per_symbol, const double final_state_density, const std::optional<unsigned int> &seed = std::nullopt)

Creates Tabakov-Vardi random NFA.

The implementation is based on the paper “Experimental Evaluation of Classical Automata Constructions” by Tabakov and Vardi.

Parameters:

  • num_of_states – Number of states in the automaton.

  • alphabet_size – Size of the alphabet.

  • states_transitions_ratio_per_symbol – Ratio between number of transitions and number of states for each symbol. The value must be in range [0, num_of_states]. A value of 1 means that there will be num_of_states transitions for each symbol. A value of num_of_states means that there will be a transition between every pair of states for each symbol.

  • final_state_density – Density of final states in the automaton. The value must be in range [0, 1]. The state 0 is always final. If the density is 1, every state will be final.

  • seed – Seed for the PRNG used. If no seed is given, the algorithm chooses one uniformly at random.

Nfa construct(const mata::parser::ParsedSection &parsec, Alphabet *alphabet, NameStateMap *state_map = nullptr)

Loads an automaton from Parsed object.

Nfa construct(const mata::IntermediateAut &inter_aut, Alphabet *alphabet, NameStateMap *state_map = nullptr)

Loads an automaton from Parsed object.

void construct(Nfa *result, const mata::IntermediateAut &inter_aut, Alphabet *alphabet, NameStateMap *state_map = nullptr)

Loads an automaton from Parsed object; version for python binding.

template<class ParsedObject>
Nfa construct(const ParsedObject &parsed, Alphabet *alphabet = nullptr, NameStateMap *state_map = nullptr)
Nfa parse_from_mata(std::istream &nfa_stream)

Parse NFA from the mata format in an input stream.

Parameters:

nfa_stream – Input stream containing NFA in mata format.

Throws:

std::runtime_error – Parsing of NFA fails.

Nfa parse_from_mata(const std::string &nfa_in_mata)

Parse NFA from the mata format in a string.

Parameters:

nfa_stream – String containing NFA in mata format.

Throws:

std::runtime_error – Parsing of NFA fails.

Nfa parse_from_mata(const std::filesystem::path &nfa_file)

Parse NFA from the mata format in a file.

Parameters:

nfa_stream – Path to the file containing NFA in mata format.

Throws:

  • std::runtime_error – nfa_file does not exist.

  • std::runtime_error – Parsing of NFA fails.

Nfa create_from_regex(const std::string &regex)

Create NFA from regex.

The created NFA does not contain epsilons, is trimmed and reduced. It uses the parser from RE2, see mata/parser/re2praser.hh for more details and options.

At https://github.com/google/re2/wiki/Syntax, you can find the syntax of regex with following futher limitations: 1) The allowed characters are the first 256 characters of Unicode, i.e., Latin1 encoding (ASCII + 128 more characters). For the full Unicode, check mata/parser/re2praser.hh. 2) The created automaton represents the language of the regex and is not expected to be used in regex matching. Therefore, stuff like ^, $, , etc. are ignored in the regex. For example, the regular expressions a*b and ^a*b will both result in the same NFA accepting the language of multiple ‘a’s followed by one ‘b’. See also issue #494.

See also

mata::parser::create_nfa()

Parameters:

regex – regular expression