Struct liblet::automaton::Automaton

pub struct Automaton<T> where
    T: Eq + Clone + Ord,  { /* fields omitted */ }

The main type of this module.

This type represents a nondeterministic finite automaton defined as: A = (N,T,transitions,q0,F) where N is the set of states, T is the set of transitions labels, q0 is the starting state and F is the set of final states.

The transitions are the ones defined in this same module: Transitions.

Implementations

impl<T> Automaton<T> where
    T: Eq + Clone + Ord, 

pub fn new<I, F>(transitions: I, f: F) -> Result<Automaton<T>, AutomatonError> where
    I: IntoIterator<Item = Transition<T>>,
    F: IntoIterator,
    F::Item: IntoIterator<Item = T>, 

Creates a new automaton based on the transitions and final states given.

The starting state will be the "from" part of the first transition given.

Errors

Can return an AutomatonError::NoStates error if no transitions are given.

Examples

Automaton of generic type

use liblet::automaton::{Automaton,Transition};
use liblet::symbol::symbol;
use std::collections::BTreeSet;

let t = Transition::new(vec!["0"], symbol("label"), vec!["1"]);
let mut f: BTreeSet<BTreeSet<&str>> = BTreeSet::new();
f.insert(vec!["1"].into_iter().collect());

// automaton with starting state {"0"}
// and final state {"1"}
// and transiton "label" from {"0"} to {"1"}
let a = Automaton::new(vec![t], f);
assert!(a.is_ok());

Automaton of symbols

use liblet::automaton::{Automaton,transitions};
use liblet::symbol::{Symbol,symbol};
use std::collections::BTreeSet;

let t = transitions("A -> label -> B");
let mut f: BTreeSet<BTreeSet<Symbol>> = BTreeSet::new();
f.insert(vec![symbol("B")].into_iter().collect());

// automaton with starting state {"A"}
// and final state {"B"}
// and transiton "label" from {"A"} to {"B"}
let a = Automaton::new(t, f);
assert!(a.is_ok());

pub fn with_q0<I, Q, F>(
    transitions: I,
    f: F,
    q0: Q
) -> Result<Automaton<T>, AutomatonError> where
    I: IntoIterator<Item = Transition<T>>,
    Q: IntoIterator<Item = T>,
    F: IntoIterator,
    F::Item: IntoIterator<Item = T>, 

Creates a new automaton based on the transitions, starting state and final states given.

Errors

Can return an AutomatonError::NoStates error if no transitions are given.

Examples

Automaton of generic type

use liblet::automaton::{Automaton,Transition};
use liblet::symbol::symbol;
use std::collections::BTreeSet;

let t = Transition::new(vec!["0"], symbol("label"), vec!["1"]);
let q0: BTreeSet<&str> = vec!["0"].into_iter().collect();
let mut f: BTreeSet<BTreeSet<&str>> = BTreeSet::new();
f.insert(vec!["1"].into_iter().collect());

// automaton with starting state {"0"}
// and final state {"1"}
// and transiton "label" from {"0"} to {"1"}
let a = Automaton::with_q0(vec![t], f, q0);
assert!(a.is_ok());

Automaton of symbols

use liblet::automaton::{Automaton,transitions};
use liblet::symbol::{Symbol,symbol};
use std::collections::BTreeSet;

let t = transitions("A -> label -> B");
let q0: BTreeSet<Symbol> = vec![symbol("A")].into_iter().collect();
let mut f: BTreeSet<BTreeSet<Symbol>> = BTreeSet::new();
f.insert(vec![symbol("B")].into_iter().collect());

// automaton with starting state {"A"}
// and final state {"B"}
// and transiton "label" from {"A"} to {"B"}
let a = Automaton::with_q0(t, f, q0);
assert!(a.is_ok());

pub fn n(&self) -> BTreeSet<BTreeSet<T>>

Return the states of the automaton.

Examples

use liblet::automaton::{Automaton,Transition};
use liblet::symbol::symbol;
use std::collections::BTreeSet;

let t = Transition::new(vec!["0"], symbol("label"), vec!["1"]);
let mut f: BTreeSet<BTreeSet<&str>> = BTreeSet::new();
f.insert(vec!["1"].into_iter().collect());

let a = Automaton::new(vec![t], f)?;

// states will be {{"0"}, {"1"}}
let states: BTreeSet<BTreeSet<&str>> =
    vec![vec!["0"],vec!["1"]].into_iter()
        .map(|s| s.into_iter().collect())
        .collect();

assert_eq!(a.n(), states);

pub fn q0(&self) -> BTreeSet<T>

Return the starting state of the automaton.

Examples

use liblet::automaton::{Automaton,Transition};
use liblet::symbol::symbol;
use std::collections::BTreeSet;

let t = Transition::new(vec!["0"], symbol("label"), vec!["1"]);
let mut f: BTreeSet<BTreeSet<&str>> = BTreeSet::new();
f.insert(vec!["1"].into_iter().collect());

let a = Automaton::new(vec![t], f)?;

// starting state will be {"0"}
let q0: BTreeSet<&str> =
    vec!["0"].into_iter().collect();

assert_eq!(a.q0(), q0);

pub fn t(&self) -> BTreeSet<Symbol>

Return the labels set of the automaton.

Examples

use liblet::automaton::{Automaton,Transition,transitions};
use liblet::symbol::{symbol,Symbol};
use std::collections::BTreeSet;

let t = transitions("
    A1 -> label1 -> B1
    A2 -> label2 -> B2
");

let a = Automaton::new::<
       Vec<Transition<Symbol>>,
       BTreeSet<BTreeSet<Symbol>>,
   >(t, BTreeSet::new())?;

// labels set will be {"label1","label2"}
let labels: BTreeSet<Symbol> =
    vec![
        symbol("label1"),
        symbol("label2")
    ].into_iter().collect();

assert_eq!(a.t(), labels);

pub fn transitions(&self) -> BTreeSet<Transition<T>>

Return the transitions set of the automaton.

Examples

use liblet::automaton::{Automaton,Transition,transitions};
use liblet::symbol::{symbol,Symbol};
use std::collections::BTreeSet;

let t = transitions("
    A1 -> label1 -> B1
    A2 -> label2 -> B2
");

let a = Automaton::new::<
       Vec<Transition<Symbol>>,
       BTreeSet<BTreeSet<Symbol>>,
   >(t.clone(), BTreeSet::new())?;


assert_eq!(a.transitions(), t.into_iter().collect());

pub fn f(&self) -> BTreeSet<BTreeSet<T>>

Return the final states set of the automaton.

Examples

use liblet::automaton::{Automaton,transitions};
use liblet::symbol::{symbol,Symbol};
use std::collections::BTreeSet;

let t = transitions("
    A1 -> label1 -> B1
    A2 -> label2 -> B2
");
let mut f: BTreeSet<BTreeSet<Symbol>> = BTreeSet::new();
f.insert(vec![symbol("B1")].into_iter().collect());

let a = Automaton::new(t, f)?;

// final state is only one: {B1}
let states: BTreeSet<BTreeSet<Symbol>> =
    vec![vec![symbol("B1")]].into_iter()
        .map(|s| s.into_iter().collect())
        .collect();

assert_eq!(a.f(), states);

pub fn next<I>(&self, state: I, label: Symbol) -> BTreeSet<BTreeSet<T>> where
    I: IntoIterator<Item = T>, 

Return the next reachable states from the specified state and using the transitions with the specified label.

Examples

use liblet::automaton::{Automaton,Transition,transitions};
use liblet::symbol::{symbol,Symbol};
use std::collections::BTreeSet;

let t = transitions("
    A1 -> label1 -> B1
    A2 -> label2 -> B2
");

let a = Automaton::new::<
       Vec<Transition<Symbol>>,
       BTreeSet<BTreeSet<Symbol>>,
   >(t, BTreeSet::new())?;

// next states is only one: {B1}
let next: BTreeSet<BTreeSet<Symbol>> =
    vec![
        vec![symbol("B1")],
    ].into_iter().map(|n| n.into_iter().collect()).collect();

assert_eq!(a.next(vec![symbol("A1")], symbol("label1")), next);

impl Automaton<Symbol>

pub fn from_string<Q, F>(
    transitions: &str,
    f: F,
    q0: Option<Q>
) -> Result<Automaton<Symbol>, AutomatonError> where
    Q: IntoIterator<Item = Symbol>,
    F: IntoIterator,
    F::Item: IntoIterator<Item = Symbol>, 

Create a new automaton based on the transitions specified as string, other than an optional starting state and the final states.

The starting state is inferred from the "from" part of the first parsed transition, if None is specified at input (if there's at least one transition).

Errors

Can return an AutomatonError if an error occurs while parsing transitions from string or during automaton creation.

Example

use liblet::automaton::Automaton;
use liblet::symbol::{symbol,Symbol};

// create an automaton with two transitions,
// 3 states and the starting state {"A"},
// but no final state
let a = Automaton::from_string::<Vec<Symbol>,Vec<Vec<Symbol>>>(
    "A -> label -> B",
    vec![],
    Some(vec![symbol("A")])
);

pub fn from_grammar(g: &Grammar) -> Result<Automaton<Symbol>, AutomatonError>

Create a new automaton based on the grammar specified as input.

The method works under the assumption that the only rules of the grammar are of the form A -> a B, A -> B, A -> a, A -> ε.

The starting state is inferred from the grammar start symbol. The transitions towards other states are inferred from the grammar productions as follows:

• A -> a B | {A} -> a -> {B}
• A -> B | {A} -> ε -> {B}
• A -> a | {A} -> a -> {◇}
• A -> ε | {A} -> ε -> {◇}

Errors

Can return an AutomatonError if an error occurs creating the automaton or a specific InvalidGrammar error if the passed grammar is not a regular one or is not in the above descripted form.

Example

use liblet::automaton::Automaton;
use liblet::grammar::grammar;

let g = grammar("A -> B\nB -> b | ε");
let a = Automaton::from_grammar(&g);

Trait Implementations

impl<T: Clone> Clone for Automaton<T> where
    T: Eq + Clone + Ord, 

fn clone(&self) -> Automaton<T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> Debug for Automaton<T> where
    T: Eq + Clone + Ord + Debug, 

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

Formats the value using the given formatter.

impl<'de, T> Deserialize<'de> for Automaton<T> where
    T: Eq + Clone + Ord,
    T: Deserialize<'de>, 

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error> where
    __D: Deserializer<'de>, 

Deserialize this value from the given Serde deserializer.

impl Display for Automaton<Symbol>

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

Formats the value using the given formatter.

impl<T: Eq> Eq for Automaton<T> where
    T: Eq + Clone + Ord, 

impl<T: Hash> Hash for Automaton<T> where
    T: Eq + Clone + Ord, 

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given [Hasher].

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given [Hasher].

impl<T: Ord> Ord for Automaton<T> where
    T: Eq + Clone + Ord, 

fn cmp(&self, other: &Automaton<T>) -> Ordering

This method returns an [Ordering] between self and other.

#[must_use]fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

#[must_use]fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

#[must_use]fn clamp(self, min: Self, max: Self) -> Self

🔬 This is a nightly-only experimental API. (clamp)

Restrict a value to a certain interval.

impl<T: PartialEq> PartialEq<Automaton<T>> for Automaton<T> where
    T: Eq + Clone + Ord, 

fn eq(&self, other: &Automaton<T>) -> bool

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

fn ne(&self, other: &Automaton<T>) -> bool

This method tests for !=.

impl<T: PartialOrd> PartialOrd<Automaton<T>> for Automaton<T> where
    T: Eq + Clone + Ord, 

fn partial_cmp(&self, other: &Automaton<T>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Automaton<T>) -> bool

This method tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Automaton<T>) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Automaton<T>) -> bool

This method tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Automaton<T>) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<T> Serialize for Automaton<T> where
    T: Eq + Clone + Ord,
    T: Serialize, 

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error> where
    __S: Serializer, 

Serialize this value into the given Serde serializer.

impl<T> StructuralEq for Automaton<T> where
    T: Eq + Clone + Ord, 

impl<T> StructuralPartialEq for Automaton<T> where
    T: Eq + Clone + Ord, 

impl<'_> TryFrom<&'_ Grammar> for Automaton<Symbol>

type Error = AutomatonError

The type returned in the event of a conversion error.

fn try_from(g: &Grammar) -> Result<Self, Self::Error>

Performs the conversion.