# HG changeset patch
# User Laman
# Date 2024-06-22 22:02:30
# Node ID 0163ce5ddc96491cd933cf6c9521b597ab2e5bbd
# Parent  9e303d5ff83e709bf33d4472fe1d484bcaf39680

added the automaton reduction

diff --git a/regexp.py b/regexp.py
--- a/regexp.py
+++ b/regexp.py
@@ -271,9 +271,16 @@ class Regexp:
 
 
 class RegexpDFA:
-	def __init__(self, pattern):
+	def __init__(self, rules, end_states):
+		self.rules = rules
+		self.end_states = end_states
+
+	@classmethod
+	def create(cls, pattern):
 		r = Regexp(pattern)
-		(self.rules, self.end_states) = r.determinize()
+		(rules, end_states) = r.determinize()
+
+		return cls(rules, end_states)
 
 	def match(self, s):
 		st = (-1,)
@@ -287,13 +294,56 @@ class RegexpDFA:
 
 		return st in self.end_states
 
+	def reduce(self):
+		equivalents = self._find_equivalent_states()
+		(rules, end_states) = self._collapse_states(equivalents)
+
+		return RegexpDFA(rules, end_states)
+
+	def _find_equivalent_states(self):
+		state_set = [(-2,), (-1,)] + sorted(set(self.rules.values()))
+		alphabet = {c for (st, c) in self.rules.keys()}
+		equivalents = {(s1, s2) for (i, s1) in enumerate(state_set) for s2 in state_set[i+1:]}
+
+		for (s1, s2) in equivalents.copy():
+			if (s1 in self.end_states and s2 not in self.end_states) or (s1 not in self.end_states and s2 in self.end_states):
+				equivalents.remove((s1, s2))
+		
+		ctrl = True
+		while ctrl:
+			ctrl = False
+			for (s1, s2) in equivalents.copy():
+				for c in alphabet:
+					t1 = self.rules.get((s1, c), (-2,))
+					t2 = self.rules.get((s2, c), (-2,))
+					key = (min(t1, t2), max(t1, t2))
+					if t1 != t2 and key not in equivalents:
+						equivalents.remove((s1, s2))
+						ctrl = True
+						break
+		
+		return equivalents
+	
+	def _collapse_states(self, equivalents):
+		rules = self.rules.items()
+		end_states = self.end_states.copy()
+
+		for (s1, s2) in sorted(equivalents):
+			rules = map(
+				lambda item: (item[0], s1 if item[1] == s2 else item[1]),
+				filter(lambda item: item[0][0] != s2, rules)
+			)
+			end_states.discard(s2)
+		
+		return (dict(rules), end_states)
+
 
 if __name__ == "__main__":
 	tests = ["", "a", "ab", "aabb", "abab", "abcd", "abcbcdbcd"]
-	for pattern in ["*", "((a)", "a)"]:
+	for pattern in ["a(b|c)", "a*b*", "(ab)*", "a((bc)*d)*"]:
 		print("#", pattern)
 		try:
-			r = RegexpDFA(pattern)
+			r = RegexpDFA.create(pattern).reduce()
 		except ParsingError as e:
 			print("Failed to parse the regexp:")
 			print(e)
diff --git a/src/main.rs b/src/main.rs
--- a/src/main.rs
+++ b/src/main.rs
@@ -2,10 +2,10 @@ use regexp::Regexp;
 
 fn main() {
 	let tests = ["", "a", "ab", "aabb", "abab", "abcd", "abcbcdbcd"];
-	for pattern in ["a(b|c)", "a*b*", "a+b+", "(ab)*", "(ab)+", "a((bc)*d)*"] {
+	for pattern in ["a(b|c)", "a*b*", "(ab)*", "a((bc)*d)*"] {
 		println!("# {pattern}");
 		let r = match Regexp::new(&pattern.to_string()) {
-			Ok(r1) => r1.determinize(),
+			Ok(r1) => r1.determinize().reduce(),
 			Err(e) => {
 				println!("{e}");
 				continue;
diff --git a/src/regexp.rs b/src/regexp.rs
--- a/src/regexp.rs
+++ b/src/regexp.rs
@@ -5,6 +5,7 @@ pub use token::ParsingError;
 use token::parse;
 
 const START: usize = usize::MAX;
+const FAIL: usize = START-1;
 
 fn encode_set(set: &HashSet<usize>) -> u64 {
 	let mut res = 0;
@@ -144,4 +145,58 @@ impl RegexpDFA {
 
 		return self.end_states.contains(&state);
 	}
+
+	pub fn reduce(&self) -> RegexpDFA {
+		let equivalents = self.find_equivalent_states();
+		return self.collapse_states(equivalents);
+	}
+
+	fn find_equivalent_states(&self) -> Vec<(u64, u64)> {
+		let state_set: HashSet<u64> = HashSet::from_iter(self.rules.values().copied());
+		let mut state_vec: Vec<u64> = Vec::from_iter(state_set.into_iter());
+		state_vec.push(START as u64);
+		state_vec.push(FAIL as u64);
+		state_vec.sort();
+		state_vec.reverse();
+		let alphabet: HashSet<char> = self.rules.keys().map(|(_st, c)| c).copied().collect();
+
+		let mut equivalents = HashSet::new();
+		state_vec.iter().enumerate().for_each(|(i, s1)| {
+			equivalents.extend(
+				state_vec[i+1..].iter()
+				.filter(|s2| !(self.end_states.contains(s1)^self.end_states.contains(s2)))
+				.map(|s2| (*s1, *s2))
+			);
+		});
+
+		let mut n = usize::MAX;
+		while equivalents.len() < n {
+			n = equivalents.len();
+			equivalents = equivalents.iter().filter(|(s1, s2)| {
+				!alphabet.iter().any(|c| {
+					let t1 = self.rules.get(&(*s1, *c)).unwrap_or(&(FAIL as u64));
+					let t2 = self.rules.get(&(*s2, *c)).unwrap_or(&(FAIL as u64));
+					let key = (*t1.min(t2), *t1.max(t2));
+					return t1 != t2 && !equivalents.contains(&key);
+				})
+			}).copied().collect();
+		}
+
+		return Vec::from_iter(equivalents.into_iter());
+	}
+
+	fn collapse_states(&self, mut equivalents: Vec<(u64, u64)>) -> RegexpDFA {
+		let mut rules = self.rules.clone();
+		let mut end_states = self.end_states.clone();
+		equivalents.sort();
+
+		for (s1, s2) in equivalents.into_iter() {
+			rules = rules.into_iter()
+				.filter(|((st, _c), _t)| *st != s2)
+				.map(|(key, t)| (key, if t==s2 {s1} else {t})).collect();
+			end_states.remove(&s2);
+		}
+
+		return RegexpDFA{rules, end_states};
+	}
 }
diff --git a/tests/test_regexp.rs b/tests/test_regexp.rs
--- a/tests/test_regexp.rs
+++ b/tests/test_regexp.rs
@@ -11,7 +11,7 @@ fn test_eval_basic_nfa() {
 
 #[test]
 fn test_eval_basic_dfa() {
-	let r = Regexp::new(&String::from("abc")).unwrap().determinize();
+	let r = Regexp::new(&String::from("abc")).unwrap().determinize().reduce();
 	assert!(r.eval(String::from("abc")));
 	assert!(!r.eval(String::from("ab")));
 	assert!(!r.eval(String::from("abcd")));
@@ -27,9 +27,9 @@ fn test_eval_empty_nfa() {
 
 #[test]
 fn test_eval_empty_dfa() {
-	assert!(Regexp::new(&String::from("a*")).unwrap().determinize().eval(String::from("")));
-	assert!(Regexp::new(&String::from("")).unwrap().determinize().eval(String::from("")));
-	assert!(!Regexp::new(&String::from("")).unwrap().determinize().eval(String::from("a")));
+	assert!(Regexp::new(&String::from("a*")).unwrap().determinize().reduce().eval(String::from("")));
+	assert!(Regexp::new(&String::from("")).unwrap().determinize().reduce().eval(String::from("")));
+	assert!(!Regexp::new(&String::from("")).unwrap().determinize().reduce().eval(String::from("a")));
 }
 
 #[test]
@@ -43,7 +43,7 @@ fn test_eval_asterisk_nfa() {
 
 #[test]
 fn test_eval_asterisk_dfa() {
-	let r = Regexp::new(&String::from("a*b*")).unwrap().determinize();
+	let r = Regexp::new(&String::from("a*b*")).unwrap().determinize().reduce();
 	assert!(r.eval(String::from("a")));
 	assert!(r.eval(String::from("ab")));
 	assert!(r.eval(String::from("aabb")));
@@ -62,7 +62,7 @@ fn test_eval_alternative_nfa() {
 
 #[test]
 fn test_eval_alternative_dfa() {
-	let r = Regexp::new(&String::from("a|b|c")).unwrap().determinize();
+	let r = Regexp::new(&String::from("a|b|c")).unwrap().determinize().reduce();
 	assert!(r.eval(String::from("a")));
 	assert!(r.eval(String::from("b")));
 	assert!(r.eval(String::from("c")));
@@ -85,12 +85,12 @@ fn test_eval_lambda_nfa() {
 
 #[test]
 fn test_eval_lambda_dfa() {
-	let r = Regexp::new(&String::from("a_")).unwrap().determinize();
+	let r = Regexp::new(&String::from("a_")).unwrap().determinize().reduce();
 	assert!(r.eval(String::from("a")));
 	assert!(!r.eval(String::from("")));
 	assert!(!r.eval(String::from("ab")));
 
-	let r = Regexp::new(&String::from("a|_")).unwrap().determinize();
+	let r = Regexp::new(&String::from("a|_")).unwrap().determinize().reduce();
 	assert!(r.eval(String::from("a")));
 	assert!(r.eval(String::from("")));
 	assert!(!r.eval(String::from("b")));