Class mata::nfa::Delta

class Delta

Delta is a data structure for representing transition relation.

Transition is represented as a triple Trans(source state, symbol, target state). Move is the part (symbol, target state), specified for a single source state. Its underlying data structure is vector of StatePost classes. Each index to the vector corresponds to one source state, that is, a number for a certain state is an index to the vector of state posts. Transition relation (delta) in Mata stores a set of transitions in a four-level hierarchical structure: Delta, StatePost, SymbolPost, and a set of target states. A vector of ‘StatePost’s indexed by a source states on top, where the StatePost for a state ‘q’ (whose number is ‘q’ and it is the index to the vector of ‘StatePost’s) stores a set of ‘Move’s from the source state ‘q’. Namely, ‘StatePost’ has a vector of ‘SymbolPost’s, where each ‘SymbolPost’ stores a symbol ‘a’ and a vector of target states of ‘a’-moves from state ‘q’. ‘SymbolPost’s are ordered by the symbol, target states are ordered by the state number.

Public Functions

inline const StatePost &state_post(const State source) const

Get constant reference to the state post of source.

If we try to access a state post of a source which is present in the automaton as an initial/final state, yet does not have allocated space in Delta, an empty_post is returned. Hence, the function has no side effects (no allocation is performed; iterators remain valid).

Parameters:

source[in] – Source state of a state post to access.

Returns:

State post of source.

inline const StatePost &operator[](const State source) const

Get constant reference to the state post of source.

If we try to access a state post of a source which is present in the automaton as an initial/final state, yet does not have allocated space in Delta, an empty_post is returned. Hence, the function has no side effects (no allocation is performed; iterators remain valid).

Parameters:

source[in] – Source state of a state post to access.

Returns:

State post of source.

StatePost &mutable_state_post(State source)

Get mutable (non-constant) reference to the state post of source.

The function allows modifying the state post.

BEWARE, IT HAS A SIDE EFFECT.

If we try to access a state post of a source which is present in the automaton as an initial/final state, yet does not have allocated space in Delta, a new state post for source will be allocated along with all state posts for all previous states. This in turn may cause that the entire post data structure is re-allocated. Iterators to Delta will get invalidated. Use the constant ‘state_post()’ is possible. Or, to prevent the side effect from causing issues, one might want to make sure that posts of all states in the automaton are allocated, e.g., write an NFA method that allocate Delta for all states of the NFA.

Parameters:

source[in] – Source state of a state post to access.

Returns:

State post of source.

inline void allocate(const size_t num_of_states)

Allocate state posts up to num_of_states states, creating empty StatePost for yet unallocated state posts.

Parameters:

num_of_states – [in] Number of states in Delta to allocate state posts for. Have to be at least num_of_states() + 1.

inline size_t num_of_states() const

Returns:

Number of states in the whole Delta, including both source and target states.

inline bool uses_state(const State state) const

Check whether the state is used in Delta.

size_t num_of_transitions() const

Returns:

Number of transitions in Delta.

bool contains(State source, Symbol symbol, State target) const

Check whether Delta contains a passed transition.

bool contains(const Transition &transition) const

Check whether Delta contains a transition passed as a triple.

bool empty() const

Check whether automaton contains no transitions.

Returns:

True if there are no transitions in the automaton, false otherwise.

inline void append(const std::vector<StatePost> &post_vector)

Append post vector to the delta.

Parameters:

post_vector – Vector of posts to be appended.

std::vector<StatePost> renumber_targets(const std::function<State(State)> &target_renumberer) const

Copy posts of delta and apply a lambda update function on each state from targets.

IMPORTANT: In order to work properly, the lambda function needs to be monotonic, that is, the order of states in targets cannot change.

Parameters:

target_renumberer – Monotonic lambda function mapping states to different states.

Returns:

std::vector<Post> Copied posts.

void add(const State source, const Symbol symbol, const StateSet &targets)

Add transitions to multiple destinations.

Parameters:

• source – From

• symbol – Symbol

• targets – Set of states to

Transitions transitions() const

Iterator over transitions represented as Transition instances.

std::vector<Transition> get_transitions_to(State state_to) const

Get transitions leading to state_to.

Operation is slow, traverses over all symbol posts.

Parameters:

state_to[in] – Target state for transitions to get.

Returns:

Transitions leading to state_to.

std::vector<Transition> get_transitions_between(State state_from, State state_to) const

Get transitions from state_from to state_to.

Operation is slow, traverses over all symbol posts.

Parameters:

• state_from[in] – Source state.

• state_from[in] – Target state.

Returns:

Transitions from source to state_to.

StateSet get_successors(State state) const

Get the set of states that are successors of the given state.

Parameters:

state – [in] State from which successors are checked.

Returns:

Set of states that are successors of the given state.

StatePost::const_iterator epsilon_symbol_posts(State state, Symbol epsilon = EPSILON) const

Iterate over epsilon symbol posts under the given state.

Parameters:

• state – [in] State from which epsilon transitions are checked.

• epsilon – [in] User can define his favourite epsilon or used default.

Returns:

An iterator to SymbolPost with epsilon symbol. End iterator when there are no epsilon transitions.

void add_symbols_to(OnTheFlyAlphabet &target_alphabet) const

Expand target_alphabet by symbols from this delta.

The value of the already existing symbols will NOT be overwritten.

utils::OrdVector<Symbol> get_used_symbols() const

Get the set of symbols used on the transitions in the automaton.

Does not necessarily have to equal the set of symbols in the alphabet used by the automaton.

Returns:

Set of symbols used on the transitions.

Symbol get_max_symbol() const

Get the maximum non-epsilon used symbol.

Public Static Functions

static StatePost::const_iterator epsilon_symbol_posts(const StatePost &state_post, Symbol epsilon = EPSILON)

Iterate over epsilon symbol posts under the given state_post.

Parameters:

• state_post – [in] State post from which epsilon transitions are checked.

• epsilon – [in] User can define his favourite epsilon or used default.

Returns:

An iterator to SymbolPost with epsilon symbol. End iterator when there are no epsilon transitions.

class Transitions

Iterator over transitions represented as Transition instances.

It iterates over triples (State source, Symbol symbol, State target).

class const_iterator

Iterator over transitions.