1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
#![warn(missing_docs)]
//! This crate implements non-deterministic finite automata.
//!
//! By default this uses the graph from the crate [`graph`]. To use
//! another external graph, add a module in which the external graph
//! implements the Graph trait from the [`graph`] crate, and then use
//! that external graph type as [`Graph`][graph::Graph] here.
mod error;
extern crate graph;
use core::fmt::Display;
use graph::{Graph, GraphLabel, LabelGraph};
use error::Error;
/// The expected behaviour of a regular language.
///
/// Nondeterministic finite automata are equivalent to regular
/// languages. Since regular languages are easier to understand for a
/// human being, nondeterministic finite automata include the data for
/// the equivalent regular languages.
pub trait Regex<T: GraphLabel>: Graph + Display {
/// Return the label of a vertex, or an error if the node is
/// invalid.
fn vertex_label(&self, node_id: usize) -> Result<T, Error>;
#[inline]
/// Return the root node of the regular language.
///
/// Implementations can follow different conventions for the root
/// node, and hence this function.
///
/// If the regular language is empty, the implementation should
/// return None.
///
/// The default implementation uses the convention that the root
/// node is always the first node.
fn root(&self) -> Option<usize> {
if self.is_empty() {
None
} else {
Some(0)
}
}
// TODO: add functions that determine if certain "positions" in a
// regular language satisfy some special properties, like at the
// end of a Kleene star, or at the end of a regular language, et
// cetera. These will be needed later.
}
/// The expected behvaiour of a nondeterministic finite automaton.
///
/// Every NFA is a special labelled graph, so this trait extends the
/// [`LabelGraph`][graph::LabelGraph] trait.
pub trait Nfa<T: GraphLabel>: LabelGraph<T> {
/// Remove all empty transitions from the nondeterministic finite
/// automaton.
fn remove_epsilon(&mut self) -> Result<(), Error>;
/// Return a state-minimal NFA equivalent with the original one.
///
/// This is not required. It is just to allow me to experiment
/// with NFA optimization algorithms.
fn minimize(&self) -> Result<Self, Error> {
Err(Error::UnsupportedOperation)
}
/// Build a nondeterministic finite automaton out of a regular
/// language.
fn to_nfa(regex: impl Regex<T>) -> Self;
/// Remove all dead states from the nondeterministic finite
/// automaton.
///
/// A state is dead if there are no edges going to the state.
fn remove_dead(&mut self) -> Result<(), Error>;
/// For each empty transition from A to B, and for every edge from
/// B to C, say, add an edge from A to C.
///
/// This is needed specifically by the algorithm to produce a set
/// of atomic languages that represent "null-closed" derived
/// languages.
fn nulling(&mut self) -> Result<(), Error>;
}
pub mod default;
#[cfg(test)]
mod nfa_tests {}
|
