commit 328e6965c07000aed8a74261480a7b3a3dc8e94a
parent 90495df5b4ba97eb181a956c2d3d070ae701651b
Author: Ethan Long <ethandavidlong@gmail.com>
Date: Tue, 28 Nov 2023 02:06:01 +1100
Implemented some more DFAs and some tests!
Woo our DFA library works!
To be fair, it is not hard to simulate a DFA, they are really the most
basic automaton.
Diffstat:
15 files changed, 547 insertions(+), 158 deletions(-)
diff --git a/Cargo.toml b/Cargo.toml
@@ -7,4 +7,23 @@ edition = "2021"
[dependencies]
serde = "1.0.193"
-serde_json = "1.0.108"
-\ No newline at end of file
+serde_json = "1.0.108"
+
+[lib]
+name = "automaton"
+path = "src/lib/automaton.rs"
+test = true
+bench = false
+doc = false
+proc-macro = false
+crate-type = ["lib"]
+required-features = []
+
+[[bin]]
+name = "dfa"
+path = "src/bin/dfa.rs"
+test = false
+bench = false
+doc = false
+proc-macro = false
+required-features = []
+\ No newline at end of file
diff --git a/DFAs/dual_finals_interesting.dfa b/DFAs/dual_finals_interesting.dfa
@@ -0,0 +1,15 @@
+{
+ "description": "This DFA has 2 final states and has some interesting behaviour. It is indescribable. See the diagram to best understand it.",
+ "alphabet": [0, 1],
+ "states": [1, 2, 3, 4, 5, 6],
+ "initial_state": 1,
+ "final_states": [5, 6],
+ "transition_table": [
+ [1, 6, 2],
+ [2, 3, 1],
+ [3, 2, 4],
+ [4, 5, 3],
+ [5, 4, 6],
+ [6, 1, 6]
+ ]
+}
diff --git a/DFAs/even_ones.dfa b/DFAs/even_ones.dfa
@@ -1,4 +1,5 @@
{
+ "description": "This DFA accepts any binary string with an even number of ones.",
"alphabet": [0, 1],
"states": [0, 1],
"initial_state": 0,
diff --git a/DFAs/tests/dual_finals_interesting.dfa.expect b/DFAs/tests/dual_finals_interesting.dfa.expect
@@ -0,0 +1,31 @@
+f
+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
+f
+f
+f
diff --git a/DFAs/tests/dual_finals_interesting.dfa.input b/DFAs/tests/dual_finals_interesting.dfa.input
@@ -0,0 +1,31 @@
+
+1010
+101000
+10100110
+1010010010
+101001011010
+0
+01
+011
+0111
+01111
+011111
+000
+0001
+00011
+00000
+101001010
+1010010101111111
+10101
+1010111111111111
+
+1
+11
+00
+001
+0011
+101
+1011
+101101
+10100
+101001
diff --git a/DFAs/tests/even_ones.dfa.expect b/DFAs/tests/even_ones.dfa.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/DFAs/tests/even_ones.dfa.input b/DFAs/tests/even_ones.dfa.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,33 +1,5 @@
-use std::{collections::{HashMap,HashSet}, env, error::Error, fmt::Display, fs};
-
-struct DFA {
- alphabet: HashSet<char>,
- state_ids: HashSet<u64>,
- initial_state_id: u64,
- final_state_ids: HashSet<u64>,
- transition_table: HashMap<(u64, char), u64>
-}
-
-#[derive(Debug)]
-struct DFAParseError {
- reason: String
-}
-
-impl Display for DFAParseError {
- fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
- write!(f, "{}", self.reason)
- }
-}
-
-impl DFAParseError {
- fn cause(reason: &str) -> Self {
- DFAParseError {
- reason: reason.to_owned()
- }
- }
-}
-
-impl Error for DFAParseError {}
+use std::{env, error::Error, fmt::Display, fs};
+use automaton::dfa::DFA;
#[derive(Debug)]
struct CommandLineError {
@@ -73,129 +45,3 @@ fn main() -> Result<(), Box<dyn Error>> {
}
-impl Display for DFA {
- fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
- let alphabet_str: String = self.alphabet.iter().enumerate().fold("[".to_owned(), |str, (index, c)| {
- let ending = if index == self.alphabet.len() - 1 {
- "]"
- } else {
- ", "
- };
- format!("{str}{c}{ending}")
- });
-
- let state_str: String = self.state_ids.iter().enumerate().fold("[".to_owned(), |str, (index, n)| {
- let ending = if index == self.state_ids.len() - 1 {
- "]"
- } else {
- ", "
- };
- format!("{str}{n}{ending}")
- });
-
- let initial_state_str: String = self.initial_state_id.to_string();
-
- let final_state_str: String = self.final_state_ids.iter().enumerate().fold("[".to_owned(), |str, (index, n)| {
- let ending = if index == self.final_state_ids.len() - 1 {
- "]"
- } else {
- ", "
- };
- 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.iter().enumerate().map(|(index, char)| {
- (char.to_owned(), index)
- }).collect();
-
- let mut transition_table_hdr: String = alphabet_vec.iter().fold("\t|".to_owned(), |str, c| {
- format!("{str}\t{c}\t|")
- });
- transition_table_hdr.push('\n');
-
- let mut transition_map: HashMap<u64, Vec<u64>> = HashMap::new();
-
- for ((from, input), to) in self.transition_table.iter() {
- let mut new_vec: Vec<u64> = transition_map.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 transition_table_str: String = transition_map.iter().fold(transition_table_hdr, |str, (input, states)| {
- let dests = states.into_iter().fold("".to_owned(), |str, dst| {
- format!("{str}{dst}\t|\t")
- });
- format!("{str}{input}\t|\t{dests}\n")
- });
-
- write!(f, "Alphabet: {alphabet_str}\nStates: {state_str}\nInitial State: {initial_state_str}\nFinal States: {final_state_str}\nTransition Table:\n{transition_table_str}")
- }
-}
-
-
-impl DFA {
- fn parse_dfa(dfa_json: &str) -> Result<DFA, Box<dyn Error>> {
- let json: serde_json::Value = serde_json::from_str(dfa_json)?;
-
- let alphabet_vec: Vec<char> = json["alphabet"].as_array().map_or(vec![], |arr| {
- arr.iter().filter_map(|v| v.to_string().chars().next()).collect()
- });
-
- 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 state_ids: HashSet<u64> = json["states"].as_array().map_or(HashSet::new(), |arr| {
- arr.iter().filter_map(|v| v.as_u64()).collect()
- });
-
- let initial_state_id: u64 = json["initial_state"].as_u64().ok_or(Box::new(DFAParseError::cause("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 mut transition_table: HashMap<(u64, char), u64> = HashMap::new();
- for row in json["transition_table"].as_array().iter().flat_map(|opt| opt.iter()) {
- let v: Option<(u64, Vec<(u64, char)>)> = row.as_array().map_or(None, |arr| {
- let from: u64 = arr[0].as_u64()?;
- let to: Vec<(u64, char)> = arr[1..].into_iter().filter_map(|v| v.as_u64()).zip(alphabet_vec.clone()).collect();
- Some((from, to))
- });
- match v {
- Some((from, to)) => {
- for (dest, input) in to.into_iter() {
- transition_table.insert((from, input), dest);
- }
- },
- None => {return Err(Box::new(DFAParseError::cause("Unable to parse DFA, incorrect types in the JSON")));}
- }
- }
-
- Ok(DFA {
- alphabet,
- state_ids,
- final_state_ids,
- transition_table,
- initial_state_id
- })
- }
-
- 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)
- }
-}
diff --git a/src/lib/DFA.rs b/src/lib/DFA.rs
@@ -0,0 +1,207 @@
+use core::fmt::Display;
+use std::{
+ collections::{HashMap, HashSet},
+ error::Error,
+};
+
+#[derive(Debug)]
+struct DFAParseError {
+ reason: String,
+}
+
+impl Display for DFAParseError {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ write!(f, "{}", self.reason)
+ }
+}
+
+impl DFAParseError {
+ fn cause(reason: &str) -> Self {
+ DFAParseError {
+ reason: reason.to_owned(),
+ }
+ }
+}
+
+impl Error for DFAParseError {}
+
+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>,
+}
+
+impl Display for DFA {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ let alphabet_str: String =
+ self.alphabet
+ .iter()
+ .enumerate()
+ .fold("[".to_owned(), |str, (index, c)| {
+ let ending = if index == self.alphabet.len() - 1 {
+ "]"
+ } else {
+ ", "
+ };
+ format!("{str}{c}{ending}")
+ });
+
+ let state_str: String =
+ self.state_ids
+ .iter()
+ .enumerate()
+ .fold("[".to_owned(), |str, (index, n)| {
+ let ending = if index == self.state_ids.len() - 1 {
+ "]"
+ } else {
+ ", "
+ };
+ format!("{str}{n}{ending}")
+ });
+
+ let initial_state_str: String = self.initial_state_id.to_string();
+
+ let final_state_str: String =
+ self.final_state_ids
+ .iter()
+ .enumerate()
+ .fold("[".to_owned(), |str, (index, n)| {
+ let ending = if index == self.final_state_ids.len() - 1 {
+ "]"
+ } else {
+ ", "
+ };
+ 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
+ .iter()
+ .enumerate()
+ .map(|(index, char)| (char.to_owned(), index))
+ .collect();
+
+ let mut transition_table_hdr: String = alphabet_vec
+ .iter()
+ .fold("\t|".to_owned(), |str, c| format!("{str}\t{c}\t|"));
+ transition_table_hdr.push('\n');
+
+ let mut transition_map: HashMap<u64, Vec<u64>> = HashMap::new();
+
+ for ((from, input), to) in self.transition_table.iter() {
+ let mut new_vec: Vec<u64> = transition_map
+ .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 transition_table_str: String =
+ transition_map
+ .iter()
+ .fold(transition_table_hdr, |str, (input, states)| {
+ let dests = states
+ .into_iter()
+ .fold("".to_owned(), |str, dst| format!("{str}{dst}\t|\t"));
+ format!("{str}{input}\t|\t{dests}\n")
+ });
+
+ write!(f, "Alphabet: {alphabet_str}\nStates: {state_str}\nInitial State: {initial_state_str}\nFinal States: {final_state_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)?;
+
+ let alphabet_vec: Vec<char> = json["alphabet"].as_array().map_or(vec![], |arr| {
+ arr.iter()
+ .filter_map(|v| v.to_string().chars().next())
+ .collect()
+ });
+
+ 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 state_ids: HashSet<u64> = json["states"].as_array().map_or(HashSet::new(), |arr| {
+ arr.iter().filter_map(|v| v.as_u64()).collect()
+ });
+
+ let initial_state_id: u64 =
+ json["initial_state"]
+ .as_u64()
+ .ok_or(Box::new(DFAParseError::cause(
+ "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 mut transition_table: HashMap<(u64, char), u64> = HashMap::new();
+ for row in json["transition_table"]
+ .as_array()
+ .iter()
+ .flat_map(|opt| opt.iter())
+ {
+ let v: Option<(u64, Vec<(u64, char)>)> = row.as_array().map_or(None, |arr| {
+ let from: u64 = arr[0].as_u64()?;
+ let to: Vec<(u64, char)> = arr[1..]
+ .into_iter()
+ .filter_map(|v| v.as_u64())
+ .zip(alphabet_vec.clone())
+ .collect();
+ Some((from, to))
+ });
+ match v {
+ Some((from, to)) => {
+ for (dest, input) in to.into_iter() {
+ transition_table.insert((from, input), dest);
+ }
+ }
+ None => {
+ return Err(Box::new(DFAParseError::cause(
+ "Unable to parse DFA, incorrect types in the JSON",
+ )));
+ }
+ }
+ }
+
+ Ok(DFA {
+ alphabet,
+ state_ids,
+ final_state_ids,
+ transition_table,
+ initial_state_id,
+ })
+ }
+
+ 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
@@ -0,0 +1,11 @@
+pub mod dfa;
+pub mod nfa;
+
+#[cfg(test)]
+mod tests {
+ mod dfa_tests;
+ mod nfa_tests;
+ mod testlib {
+ pub mod util;
+ }
+}
diff --git a/src/lib/DFA.rs b/src/lib/nfa.rs
diff --git a/src/lib/DFA.rs b/src/lib/nfa_tests.rs
diff --git a/src/lib/tests/dfa_tests.rs b/src/lib/tests/dfa_tests.rs
@@ -0,0 +1,39 @@
+use std::fs;
+
+use super::super::dfa::DFA;
+
+use super::testlib::util;
+
+#[test]
+fn run_static_dfa_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 dfa_jsons = util::read_directory("DFAs").unwrap();
+ let dfa_tests = util::read_directory("DFAs/tests").unwrap();
+
+ for (filename, file) in dfa_jsons.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]);
+ }
+ if expected_files
+ .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();
+ assert_eq!(inputs.len(), expected.len());
+ for (input, expect) in inputs.iter().zip(expected) {
+ assert_eq!(dfa.run_dfa(input), expect);
+ }
+ println!("Successfully ran {} tests in {}", inputs.len(), expected_paths[0])
+ }
+ }
+}
diff --git a/src/lib/tests/nfa_tests.rs b/src/lib/tests/nfa_tests.rs
@@ -0,0 +1,5 @@
+#[test]
+fn simple_test() {
+ eprintln!("Test not yet written!");
+ assert!(false);
+}
diff --git a/src/lib/tests/testlib/util.rs b/src/lib/tests/testlib/util.rs
@@ -0,0 +1,32 @@
+use std::{
+ collections::HashMap,
+ fs,
+ io::{self, ErrorKind},
+};
+
+pub fn read_directory(path: &str) -> io::Result<HashMap<String, String>> {
+ let dir = fs::read_dir(path)?;
+
+ let mut contents = HashMap::new();
+
+ for entry in dir {
+ let entry = entry?;
+ let path = entry.path();
+
+ if path.is_file() {
+ let file_name: String = path
+ .file_name()
+ .ok_or(io::Error::new(ErrorKind::Other, "Could not get filename"))?
+ .to_str()
+ .ok_or(io::Error::new(
+ ErrorKind::Other,
+ "could not convert filename os string to rust &str",
+ ))?
+ .to_owned();
+ let file_content = fs::read_to_string(&path)?;
+ contents.insert(file_name, file_content);
+ }
+ }
+
+ Ok(contents)
+}
