1 files changed, 94 insertions, 0 deletions
diff --git a/nfa/src/lib.rs b/nfa/src/lib.rs
new file mode 100644
index 0000000..ef207cf
--- /dev/null
+++ b/nfa/src/lib.rs
@@ -0,0 +1,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 {}