# Minimization Algorithm

unknown
rust
2 years ago
5.6 kB
1
Indexable
Never
```pub fn minimize(&self) -> Self {
// table filling algorithm

// 1. Remove unreachable states
let mut reachable_states = HashSet::new();
reachable_states.insert(self.starting_state.clone());

for state in &self.states {
for symbol in &self.alphabet {
if let Some(out_state) = (self.transition_function)(state.clone(), symbol.clone()) {
reachable_states.insert(out_state);
}
}
}

// 2. Mark final AND non-final states
let mut mark_table = Table::new();
for state1 in &reachable_states {
for state2 in &reachable_states {
let is_final1 = self.final_states.contains(state1);
let not_is_final2 = !self.final_states.contains(state2);
mark_table.set(state1.id, state2.id, is_final1 && not_is_final2);
}
}

// Some states in the upper triangle maybe marked, could potentially be harmful to the algorithm
mark_table.drop(|key1, key2, _| {
key2 >= key1
});

// 3. Mark pairs of states
loop {
let mut has_marked = false;

// for all pairs of states (p, q) in reachable_states X alphabet
for state1 in &reachable_states {
for state2 in &reachable_states {
if *mark_table.get(&state1.id, &state2.id).unwrap() {
continue;
}

for symbol in &self.alphabet {
// if (s1, s2) where s1 = delta(p, a) and s2 = delta(q, a) is marked
// then mark (p, q)

let out_state1 = (self.transition_function)(state1.clone(), symbol.clone());
let out_state2 = (self.transition_function)(state2.clone(), symbol.clone());

if let (Some(out_state1), Some(out_state2)) = (out_state1, out_state2) {
if *mark_table.get(&out_state1.id, &out_state2.id).unwrap() {
mark_table.set(state1.id, state2.id, true);
has_marked = true;
}
}
}
}
}

mark_table.drop(|key1, key2, _| {
key2 >= key1
});

if !has_marked {
break;
}
}

// 4. Create equivalence classes
let mut equivalence_classes = Vec::new();
let mut available_states = reachable_states.clone();

while !available_states.is_empty() {
let state = available_states.iter().next().unwrap().clone();

let mut equivalence_class = HashSet::new();
equivalence_class.insert(state.clone());

for state2 in &available_states {
if !mark_table.get(&state.id, &state2.id).unwrap() {
equivalence_class.insert(state2.clone());
}
}

equivalence_classes.push(equivalence_class.clone());
available_states = available_states.difference(&equivalence_class).cloned().collect();
}

let dfa_states = st_range_hash!(0..(equivalence_classes.len() as u32));
let dfa_initial_state = equivalence_classes
.iter()
.position(|equivalence_class| equivalence_class.contains(&self.starting_state))
.unwrap();
let dfa_final_states = equivalence_classes
.iter()
.enumerate()
.filter(|(_, equivalence_class)|
equivalence_class
.iter()
.any(|state| self.final_states.contains(state)))
.map(|(i, _)| State::new(i as u32))
.collect::<HashSet<_>>();

let mut dfa_transition_function = Table::new();

for equivalence_class in &equivalence_classes {
for symbol in &self.alphabet {
// pick a state from the equivalence class
let state = equivalence_class.iter().next().unwrap().clone();

// find delta[state, symbol]
let out_state = (self.transition_function)(state.clone(), symbol.clone());
// ? is it guaranteed that out_state is always a Some()?
let out_state = out_state.unwrap();

// find the equivalence class of out_state
let out_equivalence_class = equivalence_classes
.iter()
.find(|equivalence_class| equivalence_class.contains(&out_state))
.unwrap();

// find the index of the equivalence class
let out_equivalence_class_index = equivalence_classes
.iter()
.position(|equivalence_class| equivalence_class == out_equivalence_class)
.unwrap();

// set the transition function
dfa_transition_function.set(state.id, symbol.symbol.clone(), Some(out_equivalence_class_index as u32));
}
}

Self {
states: dfa_states,
alphabet: self.alphabet.clone(),
starting_state: State::new(dfa_initial_state as u32),
final_states: dfa_final_states,
transition_function: transition_function_from_table(dfa_transition_function),
}
}```