commit 535924654494262d9585cf2ee309cd268a6b54c0
parent f1dea359d2176a141bd7e9895aa183a24b723a87
Author: Ethan Long <ethandavidlong@gmail.com>
Date: Thu, 30 Nov 2023 15:07:06 +1100
Implemented epsilon NFAs!
We're so close to regular expressions!
Diffstat:
19 files changed, 938 insertions(+), 14 deletions(-)
diff --git a/ENFAs/comp1600_a3_q3.enfa b/ENFAs/comp1600_a3_q3.enfa
@@ -0,0 +1,14 @@
+{
+ "description": "The following NFA is from the ANU COMP1600 course, assignment 3, question 3",
+ "alphabet": [0, 1],
+ "states": [0, 1, 2, 3, 4],
+ "initial_state": 0,
+ "final_states": [2, 4],
+ "transition_table": [
+ [0, [0], [0, 3], [1]],
+ [1, [3], [2], [4]],
+ [2, [4], [], []],
+ [3, [4], [], []],
+ [4, [], [], [0, 2]]
+ ]
+}
+\ No newline at end of file
diff --git a/ENFAs/ending_with_01.enfa b/ENFAs/ending_with_01.enfa
@@ -0,0 +1,12 @@
+{
+ "description": "The following NFA accepts any binary string ending with '01'",
+ "alphabet": [0, 1],
+ "states": [0, 1, 2],
+ "initial_state": 0,
+ "final_states": [2],
+ "transition_table": [
+ [0, [0, 1], [0], []],
+ [1, [], [2], []],
+ [2, [], [], []]
+ ]
+}
diff --git a/ENFAs/even_0s_or_1s.enfa b/ENFAs/even_0s_or_1s.enfa
@@ -0,0 +1,14 @@
+{
+ "description": "The following NFA accepts any binary string with an even number of '0's or '1's, or a string that is all '0's or '1's",
+ "alphabet": [0, 1],
+ "states": [0, 1, 2, 3, 4],
+ "initial_state": 0,
+ "final_states": [1, 3],
+ "transition_table": [
+ [0, [], [], [1, 3]],
+ [1, [2], [1], []],
+ [2, [1], [2], []],
+ [3, [3], [4], []],
+ [4, [4], [3], []]
+ ]
+}
diff --git a/ENFAs/every_0_followed_by_1.enfa b/ENFAs/every_0_followed_by_1.enfa
@@ -0,0 +1,12 @@
+{
+ "description": "The following NFA accepts any binary string where every '0' in the string is immediately followed by a '1'",
+ "alphabet": [0, 1],
+ "states": [0, 1, 2],
+ "initial_state": 0,
+ "final_states": [0],
+ "transition_table": [
+ [0, [], [], [1, 2]],
+ [1, [2], [], []],
+ [2, [], [0], []]
+ ]
+}
+\ No newline at end of file
diff --git a/ENFAs/tests/comp1600_a3_q3.enfa.expect b/ENFAs/tests/comp1600_a3_q3.enfa.expect
@@ -0,0 +1,33 @@
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
diff --git a/ENFAs/tests/comp1600_a3_q3.enfa.input b/ENFAs/tests/comp1600_a3_q3.enfa.input
@@ -0,0 +1,33 @@
+01010100111001
+10101001010101010
+01010
+101
+11
+10000
+000
+0101001
+
+01100
+1010
+1001
+1
+01010
+010
+0
+01
+010
+10
+
+001010
+
+01
+1101
+10
+
+0
+0100010
+101
+
+101001010010
+10010010010010010101001001011
+10010101110010
diff --git a/ENFAs/tests/ending_with_01.enfa.expect b/ENFAs/tests/ending_with_01.enfa.expect
@@ -0,0 +1,38 @@
+t
+t
+t
+t
+t
+t
+t
+
+t
+
+t
+t
+
+t
+t
+t
+t
+
+t
+t
+t
+t
+t
+t
+t
+t
+
+t
+t
+t
+
+f
+f
+f
+f
+f
+f
+f
diff --git a/ENFAs/tests/ending_with_01.enfa.input b/ENFAs/tests/ending_with_01.enfa.input
@@ -0,0 +1,38 @@
+01
+101
+1101
+11101
+111101
+1111101
+11111101
+
+0101
+
+01001
+01101
+
+010001
+010101
+011001
+011101
+
+0100001
+0100101
+0101001
+0101101
+0110001
+0110101
+0111001
+0111101
+
+0100101010101001100010101001
+01010100110101001001010101
+0101010010101110011011011001001
+
+011
+01011
+010110
+0110
+01011
+010110
+011010
diff --git a/ENFAs/tests/even_0s_or_1s.enfa.expect b/ENFAs/tests/even_0s_or_1s.enfa.expect
@@ -0,0 +1,59 @@
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+f
+f
+f
+f
+f
+f
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
diff --git a/ENFAs/tests/even_0s_or_1s.enfa.input b/ENFAs/tests/even_0s_or_1s.enfa.input
@@ -0,0 +1,59 @@
+00
+11
+
+0000
+0011
+0101
+1001
+0110
+1010
+1100
+1111
+
+001
+010
+100
+
+00111
+01011
+10011
+01101
+10101
+11001
+01110
+10110
+11010
+11100
+
+011
+101
+110
+
+11000
+10100
+01100
+10010
+01010
+00110
+10001
+01001
+00101
+00011
+
+10
+01
+1110
+0001
+111000
+000111
+
+0
+00
+000
+0000
+00000
+1
+11
+111
+1111
+11111
diff --git a/ENFAs/tests/every_0_followed_by_1.enfa.expect b/ENFAs/tests/every_0_followed_by_1.enfa.expect
@@ -0,0 +1,43 @@
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+f
+f
+f
+f
+f
+f
+f
+f
diff --git a/ENFAs/tests/every_0_followed_by_1.enfa.input b/ENFAs/tests/every_0_followed_by_1.enfa.input
@@ -0,0 +1,43 @@
+1
+
+01
+11
+
+011
+111
+
+0101
+0111
+1111
+
+01011
+01101
+10101
+01111
+10111
+11011
+11101
+11111
+
+010101
+010111
+011011
+011101
+101011
+101101
+110101
+011111
+101111
+110111
+111011
+111101
+111111
+
+001
+1001
+00
+10
+0
+01001
+0101001
+010
diff --git a/src/bin/enfa.rs b/src/bin/enfa.rs
@@ -0,0 +1,52 @@
+use automaton::{dfa::DFA, enfa::ENFA, Automaton, Encodable, FiniteStateAutomaton};
+use std::{env, error::Error, fmt::Display, fs};
+
+#[derive(Debug)]
+struct CommandLineError {
+ reason: String,
+}
+
+impl Display for CommandLineError {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ write!(f, "{}", self.reason)
+ }
+}
+
+impl CommandLineError {
+ fn cause(reason: &str) -> Self {
+ CommandLineError {
+ reason: reason.to_owned(),
+ }
+ }
+}
+
+impl Error for CommandLineError {}
+
+fn usage(prog_name: &str) -> String {
+ format!("Usage: {prog_name} <NFA filename> <input string>")
+}
+
+fn main() -> Result<(), Box<dyn Error>> {
+ let args: Vec<String> = env::args().collect();
+
+ if args.len() != 3 {
+ return Err(Box::new(CommandLineError::cause(&usage(
+ args.get(0).map_or("automaton", |s| s),
+ ))));
+ }
+
+ let enfa_json = fs::read_to_string(args.get(1).unwrap_or(&"".to_owned()))?;
+ let input_string = args
+ .get(2)
+ .ok_or(CommandLineError::cause("No input string provided!"))?;
+
+ let nfa: ENFA = ENFA::parse(enfa_json.as_str())?;
+ println!("NFA:\n{nfa}");
+ println!("Running on the following input:\n{input_string}");
+ println!("Accepts: {}", nfa.accepts(input_string));
+ let dfa: DFA = DFA::convert(Box::new(nfa))?;
+ println!("Converted to DFA, accepts: {}", dfa.accepts(input_string));
+ println!("DFA:\n{dfa}");
+
+ Ok(())
+}
diff --git a/src/lib/automaton.rs b/src/lib/automaton.rs
@@ -2,6 +2,7 @@ use std::error::Error;
pub mod dfa;
pub mod nfa;
+pub mod enfa;
pub trait Automaton {
fn accepts(&self, input: &str) -> bool;
@@ -14,7 +15,10 @@ pub trait FiniteStateAutomaton: Automaton {
Self: Sized;
fn convert(automaton: Box<dyn FiniteStateAutomaton>) -> Result<Self, Box<dyn Error>>
where
- Self: Sized;
+ Self: Sized
+ {
+ Self::from_dfa(automaton.as_dfa()?)
+ }
}
pub trait Encodable<T>
@@ -28,6 +32,7 @@ where
mod tests {
mod dfa_tests;
mod nfa_tests;
+ mod enfa_tests;
mod testlib {
pub mod util;
}
diff --git a/src/lib/enfa.rs b/src/lib/enfa.rs
@@ -0,0 +1,375 @@
+use std::{
+ collections::{HashMap, HashSet},
+ panic::Location, error::Error,
+};
+use crate::{Automaton, dfa::DFA, Encodable, FiniteStateAutomaton, nfa::NFA};
+use core::fmt::Display;
+use serde_json::{from_str, Value};
+
+#[derive(Debug)]
+struct ENFAParseError {
+ reason: String,
+}
+
+impl Display for ENFAParseError {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ write!(f, "{}", self.reason)
+ }
+}
+
+impl ENFAParseError {
+ #[track_caller]
+ fn warn_str(reason: &str, loc: Option<&Location>) -> String {
+ let location = loc.unwrap_or(Location::caller());
+ format!("[ENFA::{} WARN] {}", location, reason)
+ }
+ #[track_caller]
+ fn print_warn(reason: &str) {
+ let location = Location::caller();
+ eprintln!("{}", ENFAParseError::warn_str(reason, Some(location)))
+ }
+
+ #[track_caller]
+ fn error_str(reason: &str, loc: Option<&Location>) -> String {
+ let location = loc.unwrap_or(Location::caller());
+ format!("[ENFA::{} ERROR] {}", location, reason)
+ }
+ #[track_caller]
+ fn error(reason: &str) -> Self {
+ let location = Location::caller();
+ ENFAParseError {
+ reason: ENFAParseError::error_str(reason, Some(location)),
+ }
+ }
+}
+
+impl Error for ENFAParseError {}
+
+// ε-NFAs!
+#[derive(Clone, Debug, PartialEq)]
+pub struct ENFA {
+ pub alphabet: HashSet<char>,
+ states: HashSet<u64>,
+ initial_state: u64,
+ final_states: HashSet<u64>,
+ transition_table: HashMap<(u64, Option<char>), Vec<u64>>,
+}
+
+impl ENFA {
+ // FIXME: BUG: Circular epsilon closures kill this
+ fn eclose(&self, state: u64, visited: Option<&mut HashSet<u64>>) -> HashSet<u64> {
+ let mut reachable: HashSet<u64> = HashSet::new();
+ let mut deez = HashSet::new();
+ let visited = visited.unwrap_or(&mut deez);
+ reachable.insert(state);
+ for state in self.transition_table.get(&(state, None)).unwrap_or(&vec![]) {
+ if !visited.contains(state) {
+ visited.insert(*state);
+ for state in self.eclose(*state, Some(visited)).iter() {
+ reachable.insert(*state);
+ visited.insert(*state);
+ }
+ }
+ }
+ reachable
+ }
+}
+
+impl Automaton for ENFA {
+ // TODO: Check that this is all g
+ fn accepts(&self, input: &str) -> bool {
+ let mut current_states: HashSet<u64> = self.eclose(self.initial_state, None).into_iter().collect();
+ let mut new_states: HashSet<u64> = HashSet::new();
+
+ for c in input.chars() {
+ if !self.alphabet.contains(&c) {
+ ENFAParseError::print_warn(&format!(
+ "Input character {} is not in the alphabet of the DFA",
+ c
+ ));
+ return false;
+ }
+ for state in current_states.iter() {
+ for newstate in self.transition_table.get(&(*state, Some(c))).unwrap_or(&vec![]).iter().flat_map(|s| self.eclose(*s, None)) {
+ new_states.insert(newstate);
+ }
+ }
+ current_states = new_states;
+ new_states = HashSet::new();
+ if current_states.len() == 0 {
+ return false;
+ }
+ }
+ current_states.iter().any(|s| self.final_states.contains(s))
+ }
+}
+
+impl FiniteStateAutomaton for ENFA {
+ // TODO: Check that this is all g
+ // FIXED?: BUG: If a final state is within close(state), then state is also a final state.
+ // TODO: Check that there are no other bugs
+ fn as_dfa(&self) -> Result<DFA, Box<dyn std::error::Error>> {
+ let mut nfa_transition_table = HashMap::new();
+ for (from, input) in self.transition_table.keys().filter_map(|(f, i)| i.and_then(|c| Some((*f, c)))) {
+ let new_to: Vec<u64> = self
+ .eclose(from, None)
+ .iter()
+ .filter_map(|v| self.transition_table.get(&(*v, Some(input))))
+ .flatten()
+ .map(u64::to_owned)
+ .collect();
+ nfa_transition_table.insert((from, input), new_to);
+ }
+ let final_states = self.states.iter().filter(|v| self.eclose(**v, None).iter().any(|s| self.final_states.contains(s))).map(u64::to_owned).collect();
+ let nfa = NFA::new(self.alphabet.clone(), self.states.clone(), self.initial_state, final_states, nfa_transition_table);
+ nfa.as_dfa()
+ }
+
+ fn from_dfa(dfa: crate::dfa::DFA) -> Result<Self, Box<dyn std::error::Error>>
+ where
+ Self: Sized
+ {
+ let transition_table = dfa
+ .transition_table
+ .iter()
+ .map(|((from, input), to)| ((*from, Some(*input)), vec![*to]))
+ .collect();
+ Ok(ENFA {
+ alphabet: dfa.alphabet,
+ states: dfa.states,
+ initial_state: dfa.initial_state,
+ final_states: dfa.final_states,
+ transition_table,
+ })
+ }
+}
+
+impl Display for ENFA {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ let mut alphabet_vec: Vec<char> = self.alphabet.iter().copied().collect();
+ let mut states_vec: Vec<u64> = self.states.iter().copied().collect();
+ let mut final_states_vec: Vec<u64> = self.final_states.iter().copied().collect();
+
+ alphabet_vec.sort();
+ states_vec.sort();
+ final_states_vec.sort();
+
+ let alphabet_str =
+ alphabet_vec
+ .iter()
+ .enumerate()
+ .fold("[".to_owned(), |str, (index, c)| {
+ let ending = if index == self.alphabet.len() - 1 {
+ "]"
+ } else {
+ ", "
+ };
+ format!("{str}{c}{ending}")
+ });
+
+ let states_str = states_vec
+ .iter()
+ .enumerate()
+ .fold("[".to_owned(), |str, (index, c)| {
+ let ending = if index == self.states.len() - 1 {
+ "]"
+ } else {
+ ", "
+ };
+ format!("{str}{c}{ending}")
+ });
+
+ let initial_state_str: String = self.initial_state.to_string();
+
+ let final_states_str =
+ final_states_vec
+ .iter()
+ .enumerate()
+ .fold("[".to_owned(), |str, (index, c)| {
+ let ending = if index == self.final_states.len() - 1 {
+ "]"
+ } else {
+ ", "
+ };
+ format!("{str}{c}{ending}")
+ });
+
+ let mut transition_table_hdr: String = alphabet_vec
+ .iter()
+ .map(|c| format!("\t{c}\t|"))
+ .fold("\t|".to_owned(), |str, substr| format!("{str}{substr}"));
+ transition_table_hdr.push_str("\tε\t|");
+
+ let mut transition_map: HashMap<u64, Vec<Vec<u64>>> = HashMap::new();
+
+ let index_map: HashMap<char, usize> = alphabet_vec
+ .iter()
+ .enumerate()
+ .map(|(index, char)| (char.to_owned(), index))
+ .collect();
+
+ for ((from, input), to) in self.transition_table.iter() {
+ let mut new_vec: Vec<Vec<u64>> = transition_map
+ .get(from)
+ .unwrap_or(&vec![Vec::new(); self.alphabet.len() + 1])
+ .to_owned();
+ match input {
+ Some(char) => {
+ let new_index = index_map.get(char).ok_or(core::fmt::Error)?;
+ new_vec[*new_index] = to.to_owned();
+ }
+ None => {
+ new_vec[self.alphabet.len()] = to.to_owned();
+ }
+ }
+ transition_map.insert(from.to_owned(), new_vec);
+ }
+
+ let transition_table_str = transition_map
+ .iter()
+ .fold(transition_table_hdr, |acc, (input, state_sets)|{
+ let dests = state_sets.into_iter().fold("".to_owned(), |acc, dsts| {
+ let dest_sets_str: String = if dsts.len() == 0 {
+ "∅".to_owned()
+ } else {
+ dsts.iter()
+ .enumerate()
+ .fold("{".to_owned(), |acc, (index, dst)| {
+ let end = if index == dsts.len() - 1 { "}" } else { ", " };
+ format!("{}{}{}", acc, dst, end)
+ })
+ };
+ format!("{}{}\t|\t", acc, dest_sets_str)
+ });
+ format!("{}\n{}\t|\t{}", acc, input, dests)
+ });
+
+ writeln!(f, "Alphabet: {}", alphabet_str)?;
+ writeln!(f, "States: {}", states_str)?;
+ writeln!(f, "Initial State: {}", initial_state_str)?;
+ writeln!(f, "Final State: {}", final_states_str)?;
+ writeln!(f, "Transition Table:\n{}", transition_table_str)
+ }
+}
+
+impl Encodable<&str> for ENFA {
+ fn parse(json_str: &str) -> Result<Self, Box<dyn std::error::Error>> {
+ ENFA::parse(from_str::<Value>(json_str)?)
+ }
+}
+
+impl Encodable<Value> for ENFA {
+ fn parse(json: Value) -> Result<Self, Box<dyn std::error::Error>> {
+ let alphabet_vec: Vec<char> = json["alphabet"]
+ .as_array()
+ .ok_or(ENFAParseError::error(
+ "Could not get the alphabet from the JSON",
+ ))?
+ .iter()
+ .map(|v| v.to_string().chars().next())
+ .collect::<Option<Vec<char>>>()
+ .ok_or(ENFAParseError::error(
+ "Could not convert the alphabet to UTF-8 characters",
+ ))?;
+
+ let alphabet_size = alphabet_vec.len();
+
+ let alphabet: HashSet<char> = alphabet_vec.iter().map(char::to_owned).collect();
+
+ let states: HashSet<u64> = json["states"]
+ .as_array()
+ .ok_or(ENFAParseError::error(
+ "Could not get the states from the JSON",
+ ))?
+ .iter()
+ .map(|v| v.as_u64())
+ .collect::<Option<_>>()
+ .ok_or(ENFAParseError::error("Could not convert the states to u64"))?;
+
+ let initial_state: u64 = json["initial_state"]
+ .as_u64()
+ .ok_or(ENFAParseError::error("Initial state incorrectly formatted"))?;
+
+ let final_states: HashSet<u64> = json["final_states"]
+ .as_array()
+ .ok_or(ENFAParseError::error(
+ "Could not get the final states from the JSON",
+ ))?
+ .iter()
+ .map(|v| v.as_u64())
+ .collect::<Option<_>>()
+ .ok_or(ENFAParseError::error(
+ "Could not convert the final states to u64",
+ ))?;
+
+ let mut transition_table: HashMap<(u64, Option<char>), Vec<u64>> = HashMap::new();
+
+ for row in json["transition_table"]
+ .as_array()
+ .ok_or(ENFAParseError::error(
+ "Unable to parse rows in transition table",
+ ))?
+ .iter()
+ {
+ let transitions = row
+ .as_array()
+ .ok_or(ENFAParseError::error(
+ "Unable to get a row in the transition table",
+ ))?
+ .to_owned();
+
+ let from: u64 = transitions
+ .get(0)
+ .ok_or(ENFAParseError::error(
+ "Unable to get the \"from\" state of a row",
+ ))?
+ .as_u64()
+ .ok_or(ENFAParseError::error(
+ "Unable to parse the \"from\" state of a row as a u64",
+ ))?;
+
+ let dest_sets: Vec<(char, Vec<u64>)> = alphabet_vec
+ .iter()
+ .zip(transitions.iter().skip(1).take(alphabet_size).map(Value::as_array))
+ .map(|(input, states)| {
+ states.and_then(|vs| {
+ vs.iter()
+ .map(|v| v.as_u64())
+ .collect::<Option<_>>()
+ .and_then(|sts| Some((*input, sts)))
+ })
+ })
+ .collect::<Option<_>>()
+ .ok_or(ENFAParseError::error(
+ "Unable to parse the transition destinations in the table"
+ ))?;
+ let epsilon_transitions: Vec<Vec<u64>> = transitions.iter().skip(alphabet_size + 1).map(Value::as_array)
+ .map(|states| {
+ states.and_then(|vs| {
+ vs.iter()
+ .map(Value::as_u64)
+ .collect::<Option<_>>()
+ })
+ })
+ .collect::<Option<_>>()
+ .ok_or(ENFAParseError::error(
+ "Unable to parse the ε-closure destinations in the table"
+ ))?;
+ for (input, dests) in dest_sets.iter() {
+ transition_table.insert((from, Some(*input)), dests.to_owned());
+ }
+ for transition in epsilon_transitions.iter() {
+ transition_table.insert((from, None), transition.to_owned());
+ }
+ }
+
+ //panic!("Not yet implemented!");
+ Ok(ENFA {
+ alphabet,
+ states,
+ initial_state,
+ final_states,
+ transition_table
+ })
+ }
+}
diff --git a/src/lib/nfa.rs b/src/lib/nfa.rs
@@ -57,6 +57,24 @@ pub struct NFA {
transition_table: HashMap<(u64, char), Vec<u64>>,
}
+impl NFA {
+ pub fn new(
+ alphabet: HashSet<char>,
+ states: HashSet<u64>,
+ initial_state: u64,
+ final_states: HashSet<u64>,
+ transition_table: HashMap<(u64, char), Vec<u64>>,
+ ) -> Self {
+ NFA {
+ alphabet,
+ states,
+ initial_state,
+ final_states,
+ transition_table
+ }
+ }
+}
+
impl Automaton for NFA {
fn accepts(&self, input: &str) -> bool {
let mut current_states: Vec<u64> = vec![self.initial_state];
@@ -80,8 +98,8 @@ impl Automaton for NFA {
None => (),
}
}
- current_states = new_states.clone();
- new_states.clear();
+ current_states = new_states;
+ new_states = Vec::new();
if current_states.len() == 0 {
return false;
}
@@ -181,17 +199,9 @@ impl FiniteStateAutomaton for NFA {
transition_table,
})
}
-
- fn convert(automaton: Box<dyn FiniteStateAutomaton>) -> Result<Self, Box<dyn Error>>
- where
- Self: Sized,
- {
- NFA::from_dfa(automaton.as_dfa()?)
- }
}
impl Display for NFA {
- // FIXME: This is incomplete
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
let mut alphabet_vec: Vec<char> = self.alphabet.iter().copied().collect();
let mut states_vec: Vec<u64> = self.states.iter().copied().collect();
@@ -377,7 +387,7 @@ impl Encodable<Value> for NFA {
"Unable to parse the transition destinations in the table",
))?;
for (input, dests) in dest_sets.iter() {
- transition_table.insert((from, *input), dests.to_owned().clone());
+ transition_table.insert((from, *input), dests.to_owned());
}
}
diff --git a/src/lib/tests/dfa_tests.rs b/src/lib/tests/dfa_tests.rs
@@ -6,7 +6,7 @@ use crate::{
use std::fs;
#[test]
-fn run_static_dfa_tests() {
+fn run_static_tests() {
const NUM_EXTS: usize = 2;
let expected_exts: [&str; NUM_EXTS] = [".input", ".expect"];
let mut expected_files: [String; NUM_EXTS] = ["".to_owned(), "".to_owned()];
diff --git a/src/lib/tests/enfa_tests.rs b/src/lib/tests/enfa_tests.rs
@@ -0,0 +1,82 @@
+use crate::{
+ enfa::ENFA,
+ tests::testlib::util::{rand_string, read_directory},
+ Automaton, Encodable, FiniteStateAutomaton,
+};
+use std::fs;
+
+#[test]
+fn run_static_tests() {
+ const NUM_EXTS: usize = 2;
+ let expected_exts: [&str; NUM_EXTS] = [".input", ".expect"];
+ let mut expected_files: [String; NUM_EXTS] = ["".to_owned(), "".to_owned()];
+ let mut expected_paths: [String; NUM_EXTS] = ["".to_owned(), "".to_owned()];
+
+ let enfas = read_directory("ENFAs").expect("Unable to read items in ENFAs directory");
+ let enfa_tests =
+ read_directory("ENFAs/tests").expect("Unable to read items in the ENFAs/tests directory");
+
+ for (filename, file) in enfas.iter() {
+ for i in 0..NUM_EXTS {
+ expected_files[i] = format!("{}{}", filename, expected_exts[i]);
+ expected_paths[i] = format!("ENFAs/tests/{}{}", filename, expected_exts[i]);
+ }
+ if expected_files
+ .iter()
+ .all(|fname| enfa_tests.contains_key(fname))
+ {
+ let enfa = ENFA::parse(file.as_str()).expect("Unable to parse ENFA!");
+ let inputs: Vec<String> = fs::read_to_string(expected_paths[0].clone())
+ .expect(&format!(
+ "Unable to read file {} to string",
+ expected_paths[0]
+ ))
+ .lines()
+ .map(String::from)
+ .collect();
+ let expected: Vec<bool> = fs::read_to_string(expected_paths[1].clone())
+ .expect(&format!(
+ "Unable to read file {} to string",
+ expected_paths[0]
+ ))
+ .lines()
+ .map(|str| match str {
+ "t" => true,
+ _ => false,
+ })
+ .collect();
+ assert_eq!(inputs.len(), expected.len());
+ for ((index, input), expect) in inputs.iter().enumerate().zip(expected) {
+ assert_eq!(
+ enfa.accepts(input),
+ expect,
+ "Test no: {index}, input: {input}, file: {filename}"
+ );
+ }
+ println!(
+ "Successfully ran {} tests in {}",
+ inputs.len(),
+ expected_paths[0]
+ )
+ }
+ }
+}
+
+#[test]
+fn dfa_conversion() {
+ let enfas: Vec<String> = read_directory("ENFAs")
+ .expect("Unable to read items in the ENFAs directory")
+ .values()
+ .map(String::to_owned)
+ .collect();
+
+ for enfa_enc in enfas.iter() {
+ let enfa = ENFA::parse(enfa_enc.as_str()).expect("Unable to parse NFA!");
+ let as_dfa = enfa.as_dfa().expect("Error converting NFA to DFA!");
+
+ for i in 1..2000 {
+ let input = rand_string(i, enfa.alphabet.iter().map(char::to_owned).collect());
+ assert_eq!(enfa.accepts(&input), as_dfa.accepts(&input));
+ }
+ }
+}
diff --git a/src/lib/tests/nfa_tests.rs b/src/lib/tests/nfa_tests.rs
@@ -6,7 +6,7 @@ use crate::{
use std::fs;
#[test]
-fn run_static_nfa_tests() {
+fn run_static_tests() {
const NUM_EXTS: usize = 2;
let expected_exts: [&str; NUM_EXTS] = [".input", ".expect"];
let mut expected_files: [String; NUM_EXTS] = ["".to_owned(), "".to_owned()];
