Struct automata::nfa::Nfa

pub struct Nfa<A: Alphabet> { /* fields omitted */ }

A non-deterministic automaton with epsilon transitions.

Methods

impl<A: Alphabet> Nfa<A>

A non-deterministic finite epsilon automaton.

pub fn from_edges<I, V>(edge_iter: I, finals: V) -> Nfa<A> where
    I: IntoIterator<Item = (usize, Option<A>, usize)>,
    V: IntoIterator<Item = usize>,
    A: Clone + Debug, 

Build a epsilon nfa from the connecting edges and final states.

States are numbered in an arbitrary order, except the start label 0. Emulate multiple start states by creating epsilon transitions from the 0 state. Technically, the final state could also be collapsed into a single state but that is sometimes more tedious to work with (especially when transforming a regex in an nfa).

pub fn to_regex(&self) -> Regex<A>

First collapse all output states (compress the automaton). This is done by adding new initial/final state and epsilon transition to/from the previous states.

Then merge edges into (a+b) as much as possible

                   /–a–\
0 ––a+b–> 1   <  0 |    1
                   \–b–/

Then remove a single state (2), complicated:

0     3          0––(02)s*(23)––>1
 \   /            \             /
  \ /              \––––\ /––––/
   2 = s      >          X
  / \              /––––/ \––––\
 /   \            /             \
1     4          1––(12)s*(24)––>4

relying on 2 not being a final nor initial state, and existance due to existance of two different pathas from inital to end with a common state (transitive paths were removed before). The regex grows by up to a factor or 3! with each remove state.

'2' need not have 4 inputs or a self-loop. Note that 0,1,3,4 need not be unique! When 2 has other than 4 inputs, apply the path transformation to all accordingly. Shortcut all paths through 2 with new regexes combining all of 2s loops. When 2 does not have a self-loop, just treat this as e or ignore it.

=> O(|V|³) length, preprocessing not even included (although its growth factor is smaller).

pub fn into_dfa<I: IntoIterator<Item = A>>(
    self,
    alphabet_extension: I
) -> Dfa<A>

Convert to a dfa using the powerset construction.

Since the alphabet can not be deduced purely from transitions, alphabet_extension provides a way to indicate additional symbols.

pub fn write_to(&self, output: &mut dyn Write) -> Result<()> where
    &'a A: Display, 

Write the nfa into the dot format.

pub fn contains<I: IntoIterator<Item = A>>(&self, sequence: I) -> bool

Checks if the input word is contained in the language.

The check is realized by performing a dynamic powerset construction of the resulting dfa. For simplicity, previous states are not stored anywhere, resulting in abysmal expected runtime for anything but the smallest cases.

Consider converting the nfa to an equivalent dfa before querying, especially when performing multiple successive queries.

Trait Implementations

impl<A: Alphabet> From<Nfa<A>> for NfaRegex<A>

fn from(_automaton: Nfa<A>) -> Self

Performs the conversion.