commit c2650cee1bd0a34733a8aad0a7f94111ee2a8501
parent 328e6965c07000aed8a74261480a7b3a3dc8e94a
Author: Ethan Long <ethandavidlong@gmail.com>
Date: Wed, 29 Nov 2023 14:26:42 +1100
Finished the NFA implementation!
Conversion also works! With the unavoidable caveat (I think) that
NFA->DFA->NFA will result in a different final NFA than the initial NFA.
Diffstat:
17 files changed, 980 insertions(+), 95 deletions(-)
diff --git a/Cargo.lock b/Cargo.lock
@@ -6,17 +6,47 @@ version = 3
name = "automaton"
version = "0.1.0"
dependencies = [
+ "rand",
"serde",
"serde_json",
]
[[package]]
+name = "cfg-if"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd"
+
+[[package]]
+name = "getrandom"
+version = "0.2.11"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "fe9006bed769170c11f845cf00c7c1e9092aeb3f268e007c3e760ac68008070f"
+dependencies = [
+ "cfg-if",
+ "libc",
+ "wasi",
+]
+
+[[package]]
name = "itoa"
version = "1.0.9"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "af150ab688ff2122fcef229be89cb50dd66af9e01a4ff320cc137eecc9bacc38"
[[package]]
+name = "libc"
+version = "0.2.150"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "89d92a4743f9a61002fae18374ed11e7973f530cb3a3255fb354818118b2203c"
+
+[[package]]
+name = "ppv-lite86"
+version = "0.2.17"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5b40af805b3121feab8a3c29f04d8ad262fa8e0561883e7653e024ae4479e6de"
+
+[[package]]
name = "proc-macro2"
version = "1.0.70"
source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -35,6 +65,36 @@ dependencies = [
]
[[package]]
+name = "rand"
+version = "0.8.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "34af8d1a0e25924bc5b7c43c079c942339d8f0a8b57c39049bef581b46327404"
+dependencies = [
+ "libc",
+ "rand_chacha",
+ "rand_core",
+]
+
+[[package]]
+name = "rand_chacha"
+version = "0.3.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e6c10a63a0fa32252be49d21e7709d4d4baf8d231c2dbce1eaa8141b9b127d88"
+dependencies = [
+ "ppv-lite86",
+ "rand_core",
+]
+
+[[package]]
+name = "rand_core"
+version = "0.6.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ec0be4795e2f6a28069bec0b5ff3e2ac9bafc99e6a9a7dc3547996c5c816922c"
+dependencies = [
+ "getrandom",
+]
+
+[[package]]
name = "ryu"
version = "1.0.15"
source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -87,3 +147,9 @@ name = "unicode-ident"
version = "1.0.12"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "3354b9ac3fae1ff6755cb6db53683adb661634f67557942dea4facebec0fee4b"
+
+[[package]]
+name = "wasi"
+version = "0.11.0+wasi-snapshot-preview1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9c8d87e72b64a3b4db28d11ce29237c246188f4f51057d65a7eab63b7987e423"
diff --git a/Cargo.toml b/Cargo.toml
@@ -6,6 +6,7 @@ edition = "2021"
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[dependencies]
+rand = "0.8.5"
serde = "1.0.193"
serde_json = "1.0.108"
@@ -26,4 +27,13 @@ test = false
bench = false
doc = false
proc-macro = false
+required-features = []
+
+[[bin]]
+name = "nfa"
+path = "src/bin/nfa.rs"
+test = false
+bench = false
+doc = false
+proc-macro = false
required-features = []
\ No newline at end of file
diff --git a/NFAs/ending_with_01.nfa b/NFAs/ending_with_01.nfa
@@ -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, [], []]
+ ]
+}
+\ No newline at end of file
diff --git a/NFAs/even_ones.nfa b/NFAs/even_ones.nfa
@@ -0,0 +1,11 @@
+{
+ "description": "This NFA accepts any binary string with an even number of ones.",
+ "alphabet": [0, 1],
+ "states": [0, 1],
+ "initial_state": 0,
+ "final_states": [0],
+ "transition_table": [
+ [0, [0], [1]],
+ [1, [1], [0]]
+ ]
+}
diff --git a/NFAs/tests/ending_with_01.nfa.expect b/NFAs/tests/ending_with_01.nfa.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/NFAs/tests/ending_with_01.nfa.input b/NFAs/tests/ending_with_01.nfa.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/NFAs/tests/even_ones.nfa.expect b/NFAs/tests/even_ones.nfa.expect
@@ -0,0 +1,76 @@
+t
+t
+t
+t
+t
+t
+t
+t
+t
+f
+t
+f
+t
+f
+t
+f
+t
+t
+f
+f
+f
+t
+t
+t
+t
+t
+f
+f
+f
+f
+t
+t
+t
+t
+t
+t
+t
+t
+f
+f
+f
+f
+t
+f
+f
+f
+f
+f
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+t
+f
+f
+f
+f
+f
+f
+f
+f
+f
+f
+t
+t
+t
+t
+t
+t
diff --git a/NFAs/tests/even_ones.nfa.input b/NFAs/tests/even_ones.nfa.input
@@ -0,0 +1,76 @@
+0
+00
+000
+0000
+00000
+000000
+0000000
+00000000
+
+1
+11
+111
+1111
+11111
+111111
+1111111
+11111111
+
+010
+100
+001
+
+110
+101
+011
+
+0001
+0010
+0100
+1000
+
+0011
+0101
+1001
+0110
+1010
+1100
+
+0111
+1011
+1101
+1110
+
+00001
+00010
+00100
+01000
+10000
+
+00011
+00101
+01001
+10001
+00110
+01010
+10010
+01100
+10100
+11000
+
+00111
+01011
+10011
+01101
+10101
+11001
+01110
+10110
+11010
+11100
+
+01111
+10111
+11011
+11101
+11110
diff --git a/src/bin/dfa.rs b/src/bin/dfa.rs
@@ -1,5 +1,5 @@
use std::{env, error::Error, fmt::Display, fs};
-use automaton::dfa::DFA;
+use automaton::{dfa::DFA,Encodable,Automaton};
#[derive(Debug)]
struct CommandLineError {
@@ -36,10 +36,10 @@ fn main() -> Result<(), Box<dyn Error>> {
let dfa_json = fs::read_to_string(args.get(1).unwrap_or(&"".to_owned()))?;
let input_string = args.get(2).ok_or(Box::new(CommandLineError::cause("No input string provided!")))?;
- let dfa: DFA = DFA::parse_dfa(&dfa_json)?;
- println!("DFA: {dfa}");
+ let dfa: DFA = DFA::parse(dfa_json.as_str())?;
+ println!("DFA:\n{dfa}\n");
println!("Running on the following input:\n{input_string}");
- println!("Accepts: {}", dfa.run_dfa(input_string));
+ println!("Accepts: {}", dfa.accepts(input_string));
Ok(())
}
diff --git a/src/bin/nfa.rs b/src/bin/nfa.rs
@@ -1,3 +1,48 @@
-fn main() {
- println!("Hello world")
+use std::{env, error::Error, fmt::Display, fs};
+use automaton::{nfa::NFA,Encodable,Automaton,dfa::DFA, FiniteStateAutomaton};
+
+#[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 nfa_json = fs::read_to_string(args.get(1).unwrap_or(&"".to_owned()))?;
+ let input_string = args.get(2).ok_or(Box::new(CommandLineError::cause("No input string provided!")))?;
+
+ let nfa: NFA = NFA::parse(nfa_json.as_str())?;
+ println!("NFA:\n{nfa}\n");
+ 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}\n");
+
+ Ok(())
}
diff --git a/src/lib/DFA.rs b/src/lib/DFA.rs
@@ -2,15 +2,19 @@ use core::fmt::Display;
use std::{
collections::{HashMap, HashSet},
error::Error,
+ fmt,
};
+use crate::{Automaton, Encodable, FiniteStateAutomaton};
+use serde_json::{from_str, Value};
+
#[derive(Debug)]
struct DFAParseError {
reason: String,
}
impl Display for DFAParseError {
- fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}", self.reason)
}
}
@@ -25,18 +29,70 @@ impl DFAParseError {
impl Error for DFAParseError {}
+#[derive(Clone,Debug,PartialEq)]
pub struct DFA {
- alphabet: HashSet<char>,
- state_ids: HashSet<u64>,
- initial_state_id: u64,
- final_state_ids: HashSet<u64>,
- transition_table: HashMap<(u64, char), u64>,
+ pub alphabet: HashSet<char>,
+ pub states: HashSet<u64>,
+ pub initial_state: u64,
+ pub final_states: HashSet<u64>,
+ pub transition_table: HashMap<(u64, char), u64>,
+}
+
+impl Automaton for DFA {
+ fn accepts(&self, input: &str) -> bool {
+ let mut current_state: u64 = self.initial_state;
+ for c in input.chars() {
+ if !self.alphabet.contains(&c) {
+ eprintln!(
+ "[DFA::accepts WARNING] Input character {} is not in the alphabet of the DFA",
+ c
+ );
+ return false;
+ }
+ match self.transition_table.get(&(current_state, c)) {
+ Some(state) => current_state = state.to_owned(),
+ None => {
+ eprintln!("[DFA::accepts ERROR] The DFA's transition table is incomplete or malformed!");
+ return false;
+ }
+ }
+ }
+ self.final_states.contains(¤t_state)
+ }
+}
+
+impl FiniteStateAutomaton for DFA {
+ fn as_dfa(&self) -> DFA {
+ self.clone()
+ }
+
+ fn from_dfa(dfa: self::DFA) -> Self
+ where
+ Self: Sized
+ {
+ dfa
+ }
+
+ fn convert(automaton: Box<dyn FiniteStateAutomaton>) -> Self
+ where
+ Self: Sized
+ {
+ automaton.as_dfa()
+ }
}
impl Display for DFA {
- fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> 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: String =
- self.alphabet
+ alphabet_vec
.iter()
.enumerate()
.fold("[".to_owned(), |str, (index, c)| {
@@ -48,12 +104,12 @@ impl Display for DFA {
format!("{str}{c}{ending}")
});
- let state_str: String =
- self.state_ids
+ let states_str: String =
+ states_vec
.iter()
.enumerate()
.fold("[".to_owned(), |str, (index, n)| {
- let ending = if index == self.state_ids.len() - 1 {
+ let ending = if index == self.states.len() - 1 {
"]"
} else {
", "
@@ -61,14 +117,14 @@ impl Display for DFA {
format!("{str}{n}{ending}")
});
- let initial_state_str: String = self.initial_state_id.to_string();
+ let initial_state_str: String = self.initial_state.to_string();
- let final_state_str: String =
- self.final_state_ids
+ let final_states_str: String =
+ final_states_vec
.iter()
.enumerate()
.fold("[".to_owned(), |str, (index, n)| {
- let ending = if index == self.final_state_ids.len() - 1 {
+ let ending = if index == self.final_states.len() - 1 {
"]"
} else {
", "
@@ -76,18 +132,16 @@ impl Display for DFA {
format!("{str}{n}{ending}")
});
- //let transition_table_hdr: String = "from\t|\tinput\t|\tto\n".to_owned();
- let alphabet_vec: Vec<char> = self.alphabet.iter().cloned().collect();
- let alphabet_map: HashMap<char, usize> = alphabet_vec
+ let index_map: HashMap<char, usize> = alphabet_vec
.iter()
.enumerate()
.map(|(index, char)| (char.to_owned(), index))
.collect();
- let mut transition_table_hdr: String = alphabet_vec
+ let transition_table_hdr: String = alphabet_vec
.iter()
- .fold("\t|".to_owned(), |str, c| format!("{str}\t{c}\t|"));
- transition_table_hdr.push('\n');
+ .map(|c| format!("\t{c}\t|"))
+ .fold("\t|".to_owned(), |str, substr| format!("{str}{substr}"));
let mut transition_map: HashMap<u64, Vec<u64>> = HashMap::new();
@@ -96,13 +150,9 @@ impl Display for DFA {
.get(from)
.unwrap_or(&vec![0 as u64; self.alphabet.len()])
.to_owned();
- match alphabet_map.get(&input) {
- Some(new_index) => {
- new_vec[*new_index] = to.to_owned();
- transition_map.insert(from.to_owned(), new_vec);
- }
- None => return write!(f, "ERROR!"),
- }
+ let new_index = index_map.get(&input).ok_or(fmt::Error)?;
+ new_vec[*new_index] = to.to_owned();
+ transition_map.insert(from.to_owned(), new_vec);
}
let transition_table_str: String =
@@ -112,46 +162,38 @@ impl Display for DFA {
let dests = states
.into_iter()
.fold("".to_owned(), |str, dst| format!("{str}{dst}\t|\t"));
- format!("{str}{input}\t|\t{dests}\n")
+ format!("{str}\n{input}\t|\t{dests}")
});
- write!(f, "Alphabet: {alphabet_str}\nStates: {state_str}\nInitial State: {initial_state_str}\nFinal States: {final_state_str}\nTransition Table:\n{transition_table_str}")
+ write!(f, "Alphabet: {alphabet_str}\nStates: {states_str}\nInitial State: {initial_state_str}\nFinal States: {final_states_str}\nTransition Table:\n{transition_table_str}")
}
}
-impl DFA {
- pub fn parse_dfa(dfa_json: &str) -> Result<DFA, Box<dyn Error>> {
- let json: serde_json::Value = serde_json::from_str(dfa_json)?;
+// This is the impl that should be used when reading DFA files
+impl Encodable<&str> for DFA {
+ fn parse(json_str: &str) -> Result<DFA, Box<dyn Error>> {
+ DFA::parse(from_str::<Value>(json_str)?)
+ }
+}
- let alphabet_vec: Vec<char> = json["alphabet"].as_array().map_or(vec![], |arr| {
- arr.iter()
- .filter_map(|v| v.to_string().chars().next())
- .collect()
- });
+impl Encodable<Value> for DFA {
+ fn parse(json: Value) -> Result<DFA, Box<dyn Error>> {
+ let alphabet_vec: Vec<char> = json["alphabet"].as_array().ok_or(DFAParseError::cause("[DFA::parse ERROR] Could not get the alphabet from the JSON"))?.iter().map(|v| v.to_string().chars().next()).collect::<Option<Vec<char>>>().ok_or(DFAParseError::cause("[DFA::parse ERROR] Could not convert the alphabet to UTF-8 characters"))?;
- let alphabet: HashSet<char> = json["alphabet"].as_array().map_or(HashSet::new(), |arr| {
- arr.iter()
- .filter_map(|v| v.to_string().chars().next())
- .collect()
- });
+ let alphabet: HashSet<char> = alphabet_vec.iter().map(char::to_owned).collect();
- let state_ids: HashSet<u64> = json["states"].as_array().map_or(HashSet::new(), |arr| {
- arr.iter().filter_map(|v| v.as_u64()).collect()
- });
+ let states: HashSet<u64> = json["states"].as_array().ok_or(DFAParseError::cause("[DFA::parse ERROR] Could not get the states from the JSON"))?.iter().map(|v| v.as_u64()).collect::<Option<HashSet<u64>>>().ok_or(DFAParseError::cause("[DFA::parse ERROR] Could not convert the states to u64"))?;
- let initial_state_id: u64 =
+ let initial_state: u64 =
json["initial_state"]
.as_u64()
.ok_or(Box::new(DFAParseError::cause(
- "Initial state incorrectly formatted",
+ "[DFA::parse ERROR] Initial state incorrectly formatted",
)))?;
- let final_state_ids: HashSet<u64> = json["final_states"]
- .as_array()
- .map_or(HashSet::new(), |arr| {
- arr.iter().filter_map(|v| v.as_u64()).collect()
- });
+ let final_states: HashSet<u64> = json["final_states"].as_array().ok_or(DFAParseError::cause("[DFA::parse ERROR] Could not get the final states from the JSON"))?.iter().map(|v| v.as_u64()).collect::<Option<_>>().ok_or(DFAParseError::cause("[DFA::parse ERROR] Could not convert the final states to u64"))?;
+ // FIXME: This really should be redone, look at the NFA one for inspo
let mut transition_table: HashMap<(u64, char), u64> = HashMap::new();
for row in json["transition_table"]
.as_array()
@@ -183,25 +225,10 @@ impl DFA {
Ok(DFA {
alphabet,
- state_ids,
- final_state_ids,
+ states,
+ final_states,
transition_table,
- initial_state_id,
+ initial_state,
})
}
-
- pub fn run_dfa(&self, input: &str) -> bool {
- let mut current_state_id: u64 = self.initial_state_id;
- for c in input.chars() {
- match self.transition_table.get(&(current_state_id, c)) {
- Some(state) => current_state_id = state.to_owned(),
- None => return false,
- }
- }
- self.final_state_ids.contains(¤t_state_id)
- }
-}
-
-#[cfg(test)]
-mod tests {
}
diff --git a/src/lib/automaton.rs b/src/lib/automaton.rs
@@ -1,6 +1,26 @@
+use std::error::Error;
+
pub mod dfa;
pub mod nfa;
+pub trait Automaton {
+ fn accepts(&self, input: &str) -> bool;
+}
+
+pub trait FiniteStateAutomaton: Automaton {
+ fn as_dfa(&self) -> dfa::DFA;
+ fn from_dfa(dfa: dfa::DFA) -> Self
+ where
+ Self: Sized;
+ fn convert(automaton: Box<dyn FiniteStateAutomaton>) -> Self
+ where
+ Self: Sized;
+}
+
+pub trait Encodable<T> where Self: Sized {
+ fn parse(encoding: T) -> Result<Self, Box<dyn Error>>;
+}
+
#[cfg(test)]
mod tests {
mod dfa_tests;
diff --git a/src/lib/nfa.rs b/src/lib/nfa.rs
@@ -0,0 +1,345 @@
+use crate::{dfa::DFA, Automaton, Encodable, FiniteStateAutomaton};
+use core::fmt::Display;
+use std::{
+ collections::{BTreeSet, HashMap, HashSet},
+ error::Error,
+ fmt,
+};
+
+use serde_json::{from_str, Value};
+
+#[derive(Debug)]
+struct NFAParseError {
+ reason: String,
+}
+
+impl Display for NFAParseError {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> std::fmt::Result {
+ write!(f, "{}", self.reason)
+ }
+}
+
+impl NFAParseError {
+ fn cause(reason: &str) -> Self {
+ NFAParseError {
+ reason: reason.to_owned(),
+ }
+ }
+}
+
+impl Error for NFAParseError {}
+
+#[derive(Clone, Debug, PartialEq)]
+pub struct NFA {
+ pub alphabet: HashSet<char>,
+ states: HashSet<u64>,
+ initial_state: u64,
+ final_states: HashSet<u64>,
+ transition_table: HashMap<(u64, char), Vec<u64>>,
+}
+
+impl Automaton for NFA {
+ fn accepts(&self, input: &str) -> bool {
+ let mut current_states: Vec<u64> = vec![self.initial_state];
+ let mut new_states: Vec<u64> = Vec::new();
+ for c in input.chars() {
+ if !self.alphabet.contains(&c) {
+ eprintln!(
+ "[NFA::accepts WARNING] Input character {} is not in the alphabet of the DFA",
+ c
+ );
+ return false;
+ }
+ for i in 0..current_states.len() {
+ match current_states
+ .get(i)
+ .map_or(None, |s| self.transition_table.get(&(*s, c)))
+ {
+ Some(states) => {
+ new_states.append(&mut states.clone());
+ }
+ None => (),
+ }
+ }
+ current_states = new_states.clone();
+ new_states.clear();
+ if current_states.len() == 0 {
+ return false;
+ }
+ }
+ current_states.iter().any(|s| self.final_states.contains(s))
+ }
+}
+
+impl FiniteStateAutomaton for NFA {
+ fn as_dfa(&self) -> DFA {
+ let mut current_newstate = self.initial_state;
+ let mut newest_newstate = current_newstate;
+ // Subset construction algo
+ let mut state_forward_map: HashMap<BTreeSet<u64>, u64> = HashMap::new();
+ let mut state_reverse_map: HashMap<u64, BTreeSet<u64>> = HashMap::new();
+ let mut transition_table: HashMap<(u64, char), u64> = HashMap::new();
+
+ state_reverse_map.insert(self.initial_state, BTreeSet::from([self.initial_state]));
+ state_forward_map.insert(BTreeSet::from([self.initial_state]), self.initial_state);
+
+ while current_newstate <= newest_newstate {
+ for c in self.alphabet.iter() {
+ let current_states = state_reverse_map
+ .clone()
+ .get(¤t_newstate)
+ .expect("We should have already added this state into the reverse map!")
+ .to_owned();
+ let to: BTreeSet<u64> = current_states
+ .iter()
+ .flat_map(|st| {
+ self.transition_table
+ .get(&(*st, *c))
+ .unwrap_or(&vec![])
+ .to_owned()
+ .iter()
+ .map(u64::to_owned)
+ .collect::<Vec<u64>>()
+ })
+ .collect();
+
+ match state_forward_map.get(&to) {
+ Some(state) => {
+ transition_table.insert((current_newstate, *c), *state);
+ }
+ None => {
+ newest_newstate += 1;
+ state_forward_map.insert(to.clone(), newest_newstate);
+ state_reverse_map.insert(newest_newstate, to.clone());
+ transition_table.insert((current_newstate, *c), newest_newstate);
+ if to.len() == 0 {
+ println!("Should be here!");
+ // Add the transitions to the new trap state
+ for c in self.alphabet.iter() {
+ transition_table.insert((newest_newstate, *c), newest_newstate);
+ }
+ }
+ }
+ }
+ }
+ current_newstate += 1;
+ }
+ let states = (self.initial_state..newest_newstate).collect();
+ let final_states: HashSet<u64> = state_reverse_map
+ .iter()
+ .filter(|(_, old_states)| {
+ old_states
+ .iter()
+ .any(|old_state| self.final_states.contains(old_state))
+ })
+ .map(|(new_state, _)| new_state.to_owned())
+ .collect();
+
+ DFA {
+ alphabet: self.alphabet.clone(),
+ states,
+ initial_state: self.initial_state,
+ final_states,
+ transition_table,
+ }
+ }
+
+ fn from_dfa(dfa: DFA) -> Self
+ where
+ Self: Sized,
+ {
+ let transition_table = dfa
+ .transition_table
+ .iter()
+ .map(|(from_input, to)| (*from_input, vec![*to]))
+ .collect();
+ NFA {
+ alphabet: dfa.alphabet,
+ states: dfa.states,
+ initial_state: dfa.initial_state,
+ final_states: dfa.final_states,
+ transition_table,
+ }
+ }
+
+ fn convert(automaton: Box<dyn FiniteStateAutomaton>) -> Self
+ where
+ Self: Sized,
+ {
+ NFA::from_dfa(automaton.as_dfa())
+ }
+}
+
+impl Display for NFA {
+ 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 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 initial_state_str: String = self.initial_state.to_string();
+
+ write!(f, "Alphabet: {alphabet_str}\nStates: {states_str}\nInitial State: {initial_state_str}\nFinal States: {final_states_str}")
+ }
+}
+
+impl Encodable<&str> for NFA {
+ fn parse(json_str: &str) -> Result<Self, Box<dyn std::error::Error>> {
+ NFA::parse(from_str::<Value>(json_str)?)
+ }
+}
+
+impl Encodable<Value> for NFA {
+ fn parse(json: Value) -> Result<Self, Box<dyn Error>> {
+ let alphabet_vec: Vec<char> = json["alphabet"]
+ .as_array()
+ .ok_or(NFAParseError::cause(
+ "[NFA::parse ERROR] Could not get the alphabet from the JSON",
+ ))?
+ .iter()
+ .map(|v| v.to_string().chars().next())
+ .collect::<Option<Vec<char>>>()
+ .ok_or(NFAParseError::cause(
+ "[NFA::parse ERROR] Could not convert the alphabet to UTF-8 characters",
+ ))?;
+
+ let alphabet: HashSet<char> = alphabet_vec.iter().map(char::to_owned).collect();
+
+ let states: HashSet<u64> = json["states"]
+ .as_array()
+ .ok_or(NFAParseError::cause(
+ "[NFA::parse ERROR] Could not get the states from the JSON",
+ ))?
+ .iter()
+ .map(|v| v.as_u64())
+ .collect::<Option<_>>()
+ .ok_or(NFAParseError::cause(
+ "[NFA::parse ERROR] Could not convert the states to u64",
+ ))?;
+
+ let initial_state: u64 =
+ json["initial_state"]
+ .as_u64()
+ .ok_or(Box::new(NFAParseError::cause(
+ "[NFA::parse ERROR] Initial state incorrectly formatted",
+ )))?;
+
+ let final_states: HashSet<u64> = json["final_states"]
+ .as_array()
+ .ok_or(NFAParseError::cause(
+ "[NFA::parse ERROR] Could not get the final states from the JSON",
+ ))?
+ .iter()
+ .map(|v| v.as_u64())
+ .collect::<Option<_>>()
+ .ok_or(NFAParseError::cause(
+ "[NFA::parse ERROR] Could not convert the final states to u64",
+ ))?;
+
+ /*
+ {
+ "description": "...",
+ "alphabet": [...],
+ "states": [...],
+ "initial_state": ...,
+ "final_states": [...],
+ "transition_table": [
+ [0, [...], [...], ...],
+ [1, [...], [...], ...]
+ ]
+ }
+ */
+ let mut transition_table: HashMap<(u64, char), Vec<u64>> = HashMap::new();
+ for row in json["transition_table"]
+ .as_array()
+ .ok_or(NFAParseError::cause(
+ "[NFA::parse ERROR] Unable to parse rows in transition table",
+ ))
+ .iter()
+ .flat_map(|opt| opt.iter())
+ {
+ let transitions = row
+ .as_array()
+ .ok_or(NFAParseError::cause(
+ "[NFA::parse ERROR] Unable to get a row in the transition table",
+ ))?
+ .to_owned();
+ let from: u64 = transitions
+ .get(0)
+ .ok_or(NFAParseError::cause(
+ "[NFA::parse ERROR] Unable to get the \"from\" state of a row",
+ ))?
+ .as_u64()
+ .ok_or("[NFA::parse ERROR] Unable to parse the \"from\" state of a row as a u64")?;
+ let dest_sets: Vec<(char, Vec<u64>)> = transitions[1..]
+ .iter()
+ .map(|v| v.as_array())
+ .zip(alphabet_vec.clone())
+ .map(|(states, input)| {
+ states.and_then(|vs| {
+ vs.iter()
+ .map(|v| v.as_u64())
+ .collect::<Option<_>>()
+ .and_then(|sts| Some((input, sts)))
+ })
+ })
+ .collect::<Option<_>>()
+ .ok_or(NFAParseError::cause(
+ "[NFA::parse ERROR] 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());
+ }
+ }
+
+ //assert!(false, "FUNCTION NOT YET IMPLEMENTED!");
+ Ok(NFA {
+ alphabet,
+ states,
+ initial_state,
+ final_states,
+ transition_table,
+ })
+ }
+}
diff --git a/src/lib/nfa_tests.rs b/src/lib/nfa_tests.rs
diff --git a/src/lib/tests/dfa_tests.rs b/src/lib/tests/dfa_tests.rs
@@ -1,9 +1,10 @@
+use crate::{
+ dfa::DFA,
+ tests::testlib::util::{rand_string, read_directory},
+ Automaton, Encodable, FiniteStateAutomaton,
+};
use std::fs;
-use super::super::dfa::DFA;
-
-use super::testlib::util;
-
#[test]
fn run_static_dfa_tests() {
const NUM_EXTS: usize = 2;
@@ -11,10 +12,11 @@ fn run_static_dfa_tests() {
let mut expected_files: [String; NUM_EXTS] = ["".to_owned(), "".to_owned()];
let mut expected_paths: [String; NUM_EXTS] = ["".to_owned(), "".to_owned()];
- let dfa_jsons = util::read_directory("DFAs").unwrap();
- let dfa_tests = util::read_directory("DFAs/tests").unwrap();
+ let dfas = read_directory("DFAs").expect("Unable to read items in DFAs directory");
+ let dfa_tests =
+ read_directory("DFAs/tests").expect("Unable to read items in the DFAs/tests directory");
- for (filename, file) in dfa_jsons.iter() {
+ for (filename, file) in dfas.iter() {
for i in 0..NUM_EXTS {
expected_files[i] = format!("{}{}", filename, expected_exts[i]);
expected_paths[i] = format!("DFAs/tests/{}{}", filename, expected_exts[i]);
@@ -23,17 +25,54 @@ fn run_static_dfa_tests() {
.iter()
.all(|fname| dfa_tests.contains_key(fname))
{
- let dfa = DFA::parse_dfa(file).unwrap();
- let inputs: Vec<String> = fs::read_to_string(expected_paths[0].clone()).unwrap().lines().map(String::from).collect();
- let expected: Vec<bool> = fs::read_to_string(expected_paths[1].clone()).unwrap().lines().map(|str| match str {
- "t" => true,
- _ => false
- }).collect();
+ let dfa = DFA::parse(file.as_str()).expect("Unable to parse DFA!");
+ 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 (input, expect) in inputs.iter().zip(expected) {
- assert_eq!(dfa.run_dfa(input), expect);
+ assert_eq!(dfa.accepts(input), expect);
}
- println!("Successfully ran {} tests in {}", inputs.len(), expected_paths[0])
+ println!(
+ "Successfully ran {} tests in {}",
+ inputs.len(),
+ expected_paths[0]
+ )
+ }
+ }
+}
+
+#[test]
+fn dfa_conversion() {
+ let dfas: Vec<String> = read_directory("DFAs")
+ .expect("Unable to read items in the DFAs directory")
+ .values()
+ .map(String::to_owned)
+ .collect();
+
+ for dfa_enc in dfas.iter() {
+ let dfa = DFA::parse(dfa_enc.as_str()).expect("Unable to parse DFA!");
+ let as_dfa = dfa.as_dfa();
+
+ for i in 1..2000 {
+ let input = rand_string(i, dfa.alphabet.iter().map(char::to_owned).collect());
+ assert_eq!(dfa.accepts(&input), as_dfa.accepts(&input));
}
}
}
diff --git a/src/lib/tests/nfa_tests.rs b/src/lib/tests/nfa_tests.rs
@@ -1,5 +1,74 @@
+use crate::{nfa::NFA, Automaton, Encodable, FiniteStateAutomaton, tests::testlib::util::{rand_string, read_directory}};
+use std::fs;
+
#[test]
-fn simple_test() {
- eprintln!("Test not yet written!");
- assert!(false);
+fn run_static_nfa_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 nfas = read_directory("NFAs").expect("Unable to read items in NFAs directory");
+ let nfa_tests =
+ read_directory("NFAs/tests").expect("Unable to read items in the NFAs/tests directory");
+
+ for (filename, file) in nfas.iter() {
+ for i in 0..NUM_EXTS {
+ expected_files[i] = format!("{}{}", filename, expected_exts[i]);
+ expected_paths[i] = format!("NFAs/tests/{}{}", filename, expected_exts[i]);
+ }
+ if expected_files
+ .iter()
+ .all(|fname| nfa_tests.contains_key(fname))
+ {
+ let nfa = NFA::parse(file.as_str()).expect("Unable to parse NFA!");
+ 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!(nfa.accepts(input), expect, "Test no: {index}, input: {input}");
+ }
+ println!(
+ "Successfully ran {} tests in {}",
+ inputs.len(),
+ expected_paths[0]
+ )
+ }
+ }
+}
+
+#[test]
+fn dfa_conversion() {
+ let nfas: Vec<String> = read_directory("NFAs")
+ .expect("Unable to read items in the NFAs directory")
+ .values()
+ .map(String::to_owned)
+ .collect();
+
+ for nfa_enc in nfas.iter() {
+ let nfa = NFA::parse(nfa_enc.as_str()).expect("Unable to parse NFA!");
+ let as_dfa = nfa.as_dfa();
+
+ for i in 1..2000 {
+ let input = rand_string(i, nfa.alphabet.iter().map(char::to_owned).collect());
+ assert_eq!(nfa.accepts(&input), as_dfa.accepts(&input));
+ }
+ }
}
diff --git a/src/lib/tests/testlib/util.rs b/src/lib/tests/testlib/util.rs
@@ -1,3 +1,4 @@
+use rand::Rng;
use std::{
collections::HashMap,
fs,
@@ -30,3 +31,14 @@ pub fn read_directory(path: &str) -> io::Result<HashMap<String, String>> {
Ok(contents)
}
+
+pub fn rand_string(size: usize, alphabet: Vec<char>) -> String {
+ let mut rng = rand::thread_rng();
+ (0..size)
+ .map(|_| {
+ alphabet
+ .get(rng.gen_range(0..alphabet.len()))
+ .expect("Unable to get random number in range!")
+ })
+ .collect()
+}
