Struct enso_automata::nfa::Nfa

pub struct Nfa {
    pub start: State,
    // some fields omitted
}

The definition of a NFA for a given set of symbols, states, and transitions (specifically a NFA with ε-moves).

A NFA is a finite state automaton that accepts or rejects a given sequence of symbols. In contrast with a DFA, the NFA may transition between states without reading any new symbol through use of epsilon links.

 ┌───┐  'N'  ┌───┐    ┌───┐  'F'  ┌───┐    ┌───┐  'A'  ┌───┐
 │ 0 │ ----> │ 1 │ -> │ 2 │ ----> │ 3 │ -> │ 3 │ ----> │ 3 │
 └───┘       └───┘ ε  └───┘       └───┘ ε  └───┘       └───┘

Fields

start: State

Implementations

impl Nfa

pub fn new() -> Self

Constructor.

pub fn new_state(&mut self) -> State

Adds a new state to the NFA and returns its identifier.

pub fn new_state_exported(&mut self) -> State

Adds a new state to the NFA, marks it as an exported state, and returns its identifier.

pub fn states(&self) -> &Vec<Data>

Get a reference to the states for this automaton.

pub fn alphabet(&self) -> &Segmentation

Get a reference to the alphabet for this automaton.

pub fn connect(&mut self, source: State, target: State)

Creates an epsilon transition between two states.

Whenever the automaton happens to be in source state it can immediately transition to the target state. It is, however, not required to do so.

pub fn connect_via(
    &mut self,
    source: State,
    target: State,
    symbols: &RangeInclusive<Symbol>
)

Creates an ordinary transition for a range of symbols.

If any symbol from such range happens to be the input when the automaton is in the source state, it will immediately transition to the target state.

pub fn new_pattern(
    &mut self,
    source: State,
    pattern: impl AsRef<Pattern>
) -> State

Transforms a pattern to connected NFA states by using the algorithm described here. The asymptotic complexity is linear in number of symbols.

pub fn new_pattern_to(
    &mut self,
    source: State,
    target: State,
    pattern: impl AsRef<Pattern>
)

Transforms a pattern to connected NFA states by using the algorithm described here. This function is similar to new_pattern, but it consumes an explicit target state. The asymptotic complexity is linear in number of symbols.

pub fn eps_matrix(&self) -> Vec<StateSetId>

Merges states that are connected by epsilon links, using an algorithm based on the one shown here.

pub fn nfa_matrix(&self) -> Matrix<State>

Computes a transition matrix (state, symbol) => state for the Nfa, ignoring epsilon links.

pub fn as_graphviz_code(&self) -> String

Convert the automata to a GraphViz Dot code for the deubgging purposes.

Trait Implementations

impl Clone for Nfa

fn clone(&self) -> Nfa

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Nfa

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for Nfa

fn default() -> Self

Returns the “default value” for a type.

impl From<&'_ Nfa> for Dfa

fn from(nfa: &Nfa) -> Self

Transforms an Nfa into a Dfa, based on the algorithm described here. The asymptotic complexity is quadratic in number of states.

impl Index<State<Nfa>> for Nfa

type Output = Data

The returned type after indexing.

fn index(&self, state: State) -> &Self::Output

Performs the indexing (container[index]) operation.

impl IndexMut<State<Nfa>> for Nfa

fn index_mut(&mut self, state: State) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl PartialEq<Nfa> for Nfa

fn eq(&self, other: &Nfa) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Nfa) -> bool

This method tests for !=.

impl Eq for Nfa

impl StructuralEq for Nfa

impl StructuralPartialEq for Nfa