Repository: pemistahl/grex (language: python)

Issue:
Allow to provide test cases that must not be matched
Currently, only test cases that must be matched by the generated regular expression can be provided. It would be useful to additionally provide test cases that must **not** be matched by the generated expression. In combination with shorthand character classes this would allow for more specific and versatile regular expressions.


Discussion / hints:

Fix patch:
diff --git a/src/char/grapheme.rs b/src/char/grapheme.rs
index 5bcc45f..eabfcfa 100644
--- a/src/char/grapheme.rs
+++ b/src/char/grapheme.rs
@@ -18,12 +18,20 @@ use crate::char::ColorizableString;
 use crate::regexp::RegExpConfig;
 use colored::ColoredString;
 use itertools::Itertools;
+use std::cmp::{max, min, Ordering};
 use std::fmt::{Display, Formatter, Result};
 
 const CHARS_TO_ESCAPE: [&str; 14] = [
     "(", ")", "[", "]", "{", "}", "+", "*", "-", ".", "?", "|", "^", "$",
 ];
 
+#[derive(PartialEq, Eq, Debug)]
+pub(crate) enum GraphemeOverlapState {
+    Left,
+    Right,
+    Overlap,
+}
+
 #[derive(Clone, Debug, Hash, Ord, PartialOrd, Eq, PartialEq)]
 pub struct Grapheme {
     pub(crate) chars: Vec<String>,
@@ -156,6 +164,81 @@ impl Grapheme {
             .map(|it| format!("\\u{{{:x}}}", it))
             .join("")
     }
+
+    pub(crate) fn overlap_with(&self, other: &Self) -> Option<Vec<(Self, GraphemeOverlapState)>> {
+        if self.chars != other.chars {
+            return None;
+        }
+
+        if self.min > other.min || (self.min == other.min && self.max > other.max) {
+            return Some(
+                other
+                    .overlap_with(self)?
+                    .iter()
+                    .map(|(g, state)| (g.clone(), state.flip()))
+                    .collect_vec(),
+            );
+        }
+
+        let mut result = Vec::new();
+        if self.min < other.min {
+            result.push((
+                Self::new(
+                    self.chars.clone(),
+                    self.min,
+                    min(self.max, other.min - 1),
+                    &self.config,
+                ),
+                GraphemeOverlapState::Left,
+            ));
+        }
+
+        if self.max >= other.min {
+            result.push((
+                Self::new(
+                    self.chars.clone(),
+                    other.min,
+                    min(self.max, other.max),
+                    &self.config,
+                ),
+                GraphemeOverlapState::Overlap,
+            ));
+        }
+
+        match self.max.cmp(&other.max) {
+            Ordering::Less => result.push((
+                Self::new(
+                    self.chars.clone(),
+                    max(self.max + 1, other.min),
+                    other.max,
+                    &self.config,
+                ),
+                GraphemeOverlapState::Right,
+            )),
+            Ordering::Equal => (),
+            Ordering::Greater => result.push((
+                Self::new(
+                    self.chars.clone(),
+                    max(other.max + 1, self.min),
+                    self.max,
+                    &self.config,
+                ),
+                GraphemeOverlapState::Left,
+            )),
+        }
+
+        Some(result)
+    }
+}
+
+impl GraphemeOverlapState {
+    fn flip(&self) -> Self {
+        match self {
+            Self::Left => Self::Right,
+            Self::Right => Self::Left,
+            Self::Overlap => Self::Overlap,
+        }
+    }
 }
 
 impl Display for Grapheme {
@@ -259,3 +342,112 @@ fn to_colorized_string(
         v[7].clone(),
     )
 }
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_overlap_same() {
+        let config = RegExpConfig::new();
+        let chars = vec![String::from("a")];
+
+        let grapheme1 = Grapheme::new(chars, 0, 0, &config);
+
+        assert_eq!(
+            grapheme1.overlap_with(&grapheme1),
+            Some(vec![(grapheme1, GraphemeOverlapState::Overlap),])
+        );
+    }
+
+    #[test]
+    fn test_overlap_disjoint() {
+        let config = RegExpConfig::new();
+        let chars = vec![String::from("a")];
+
+        let grapheme1 = Grapheme::new(chars.clone(), 0, 0, &config);
+        let grapheme2 = Grapheme::new(chars, 10, 10, &config);
+
+        assert_eq!(
+            grapheme2.overlap_with(&grapheme1),
+            Some(vec![
+                (grapheme1, GraphemeOverlapState::Right),
+                (grapheme2, GraphemeOverlapState::Left)
+            ])
+        );
+    }
+
+    #[test]
+    fn test_overlap_initial_match() {
+        let config = RegExpConfig::new();
+        let chars = vec![String::from("a")];
+
+        let grapheme1 = Grapheme::new(chars.clone(), 0, 0, &config);
+        let grapheme2 = Grapheme::new(chars.clone(), 0, 1, &config);
+
+        assert_eq!(
+            grapheme1.overlap_with(&grapheme2),
+            Some(vec![
+                (grapheme1, GraphemeOverlapState::Overlap),
+                (
+                    Grapheme::new(chars, 1, 1, &config),
+                    GraphemeOverlapState::Right
+                )
+            ])
+        );
+    }
+
+    #[test]
+    fn test_overlap_initial_non_match() {
+        let config = RegExpConfig::new();
+        let chars = vec![String::from("a")];
+
+        let grapheme1 = Grapheme::new(chars.clone(), 0, 10, &config);
+        let grapheme2 = Grapheme::new(chars.clone(), 5, 15, &config);
+
+        assert_eq!(
+            grapheme1.overlap_with(&grapheme2),
+            Some(vec![
+                (
+                    Grapheme::new(chars.clone(), 0, 4, &config),
+                    GraphemeOverlapState::Left
+                ),
+                (
+                    Grapheme::new(chars.clone(), 5, 10, &config),
+                    GraphemeOverlapState::Overlap
+                ),
+                (
+                    Grapheme::new(chars, 11, 15, &config),
+                    GraphemeOverlapState::Right
+                ),
+            ])
+        );
+    }
+
+    #[test]
+    fn test_overlap_fully_contained() {
+        let config = RegExpConfig::new();
+        let chars = vec![String::from("a")];
+
+        let grapheme1 = Grapheme::new(chars.clone(), 0, 15, &config);
+        let grapheme2 = Grapheme::new(chars.clone(), 5, 10, &config);
+
+        assert_eq!(
+            grapheme1.overlap_with(&grapheme2),
+            Some(vec![
+                (
+                    Grapheme::new(chars.clone(), 0, 4, &config),
+                    GraphemeOverlapState::Left
+                ),
+                (
+                    Grapheme::new(chars.clone(), 5, 10, &config),
+                    GraphemeOverlapState::Overlap
+                ),
+                (
+                    Grapheme::new(chars, 11, 15, &config),
+                    GraphemeOverlapState::Left
+                ),
+            ])
+        );
+    }
+}
diff --git a/src/char/mod.rs b/src/char/mod.rs
index 6b3a912..9dc8510 100644
--- a/src/char/mod.rs
+++ b/src/char/mod.rs
@@ -21,3 +21,4 @@ mod grapheme;
 pub use cluster::GraphemeCluster;
 pub use color::ColorizableString;
 pub use grapheme::Grapheme;
+pub(crate) use grapheme::GraphemeOverlapState;
diff --git a/src/fsm/dfa.rs b/src/fsm/dfa.rs
index 08cbc30..6af6fec 100644
--- a/src/fsm/dfa.rs
+++ b/src/fsm/dfa.rs
@@ -14,29 +14,56 @@
  * limitations under the License.
  */
 
-use crate::char::{Grapheme, GraphemeCluster};
+use crate::char::{Grapheme, GraphemeCluster, GraphemeOverlapState};
 use crate::regexp::RegExpConfig;
 use itertools::Itertools;
-use petgraph::dot::{Config, Dot};
+use petgraph::dot::Dot;
 use petgraph::graph::NodeIndex;
 use petgraph::stable_graph::{Edges, StableGraph};
-use petgraph::visit::Dfs;
+use petgraph::visit::{Dfs, EdgeRef, NodeIndexable};
 use petgraph::{Directed, Direction};
-use std::cmp::{max, min};
-use std::collections::{BTreeSet, HashMap, HashSet};
+use std::cmp::max;
+use std::collections::{BTreeSet, HashMap, HashSet, VecDeque};
+use std::fmt::{Display, Formatter, Result};
 
 type State = NodeIndex<u32>;
-type StateLabel = String;
 type EdgeLabel = Grapheme;
 
+#[derive(PartialEq, Clone, Debug, Copy)]
+enum StateStatus {
+    Intermediate,
+    Accept,
+}
+
+#[derive(Clone)]
+struct StateLabel {
+    description: String,
+    status: StateStatus,
+}
+
+#[derive(Clone)]
 pub struct DFA {
     alphabet: BTreeSet<Grapheme>,
     graph: StableGraph<StateLabel, EdgeLabel>,
     initial_state: State,
-    final_state_indices: HashSet<usize>,
     config: RegExpConfig,
 }
 
+#[derive(PartialEq, Eq, Hash, Debug, Clone)]
+enum InputState<T> {
+    Both(T, T),
+    Left(T),
+}
+
+struct DFASubtractionBuilder<'a> {
+    left: &'a DFA,
+    right: &'a DFA,
+    result: DFA,
+    new_nodes: HashMap<InputState<usize>, State>,
+    queue: VecDeque<InputState<usize>>,
+    enqueued: HashSet<InputState<usize>>,
+}
+
 impl DFA {
     pub(crate) fn from(grapheme_clusters: Vec<GraphemeCluster>, config: &RegExpConfig) -> Self {
         let mut dfa = Self::new(config);
@@ -65,27 +92,28 @@ impl DFA {
     }
 
     pub(crate) fn is_final_state(&self, state: State) -> bool {
-        self.final_state_indices.contains(&state.index())
+        self.graph[state].status == StateStatus::Accept
+    }
+
+    pub(crate) fn subtract(&self, other: &Self) -> Option<Self> {
+        DFASubtractionBuilder::subtract(self, other)
     }
 
     #[allow(dead_code)]
     fn println(&self, comment: &str) {
-        println!(
-            "{}: {}",
-            comment,
-            Dot::with_config(&self.graph, &[Config::NodeIndexLabel])
-        );
-        println!("{:?}", self.final_state_indices);
+        println!("{}: {}", comment, Dot::new(&self.graph));
     }
 
     fn new(config: &RegExpConfig) -> Self {
         let mut graph = StableGraph::new();
-        let initial_state = graph.add_node("".to_string());
+        let initial_state = graph.add_node(StateLabel {
+            description: "initial".to_string(),
+            status: StateStatus::Intermediate,
+        });
         Self {
             alphabet: BTreeSet::new(),
             graph,
             initial_state,
-            final_state_indices: HashSet::new(),
             config: config.clone(),
         }
     }
@@ -97,48 +125,68 @@ impl DFA {
             self.alphabet.insert(grapheme.clone());
             current_state = self.get_next_state(current_state, grapheme);
         }
-        self.final_state_indices.insert(current_state.index());
+        self.graph[current_state].status = StateStatus::Accept;
     }
 
     fn get_next_state(&mut self, current_state: State, edge_label: &Grapheme) -> State {
-        match self.find_next_state(current_state, edge_label) {
-            Some(next_state) => next_state,
+        match self
+            .graph
+            .edges_directed(current_state, Direction::Outgoing)
+            .find(|edge| *edge.weight() == *edge_label)
+        {
+            Some(edge) => edge.target(),
             None => self.add_new_state(current_state, edge_label),
         }
     }
 
-    fn find_next_state(&mut self, current_state: State, grapheme: &Grapheme) -> Option<State> {
-        for next_state in self.graph.neighbors(current_state) {
-            let edge_idx = self.graph.find_edge(current_state, next_state).unwrap();
-            let current_grapheme = self.graph.edge_weight(edge_idx).unwrap();
+    fn add_new_state(&mut self, current_state: State, edge_label: &Grapheme) -> State {
+        let next_state = self.graph.add_node(StateLabel {
+            description: "".to_string(),
+            status: StateStatus::Intermediate,
+        });
+        self.graph
+            .add_edge(current_state, next_state, edge_label.clone());
+        next_state
+    }
+
+    fn minimize(&mut self) {
+        self.remove_dead_ends();
+        self.deduplicate_equivalent_states();
+        self.deduplicate_redundant_edges();
+    }
+
+    pub fn remove_dead_ends(&mut self) {
+        let mut queue: VecDeque<State> = self.graph.node_indices().collect();
+        let initial_size = self.graph.node_count();
 
-            if current_grapheme.value() != grapheme.value() {
+        while let Some(state) = queue.pop_front() {
+            if !self.graph.contains_node(state) || state.index() == self.initial_state.index() {
                 continue;
             }
 
-            if current_grapheme.maximum() == grapheme.maximum() - 1 {
-                let min = min(current_grapheme.minimum(), grapheme.minimum());
-                let max = max(current_grapheme.maximum(), grapheme.maximum());
-                let new_grapheme = Grapheme::new(grapheme.chars().clone(), min, max, &self.config);
-                self.graph
-                    .update_edge(current_state, next_state, new_grapheme);
-                return Some(next_state);
-            } else if current_grapheme.maximum() == grapheme.maximum() {
-                return Some(next_state);
+            let has_outgoing = self.graph.edges_directed(state, Direction::Outgoing).next() != None;
+            let has_incoming = self.graph.edges_directed(state, Direction::Incoming).next() != None;
+            let is_final = self.graph[state].status == StateStatus::Accept;
+
+            if (has_outgoing || is_final) && has_incoming {
+                continue;
             }
+
+            queue.append(&mut self.graph.neighbors(state).collect());
+            self.graph.remove_node(state);
         }
-        None
-    }
 
-    fn add_new_state(&mut self, current_state: State, edge_label: &Grapheme) -> State {
-        let next_state = self.graph.add_node("".to_string());
-        self.graph
-            .add_edge(current_state, next_state, edge_label.clone());
-        next_state
+        if self.graph.node_count() != initial_size {
+            self.alphabet = self
+                .graph
+                .edge_indices()
+                .map(|e| self.graph[e].clone())
+                .collect();
+        }
     }
 
     #[allow(clippy::many_single_char_names)]
-    fn minimize(&mut self) {
+    fn deduplicate_equivalent_states(&mut self) {
         let mut p = self.get_initial_partition();
         let mut w = p.iter().cloned().collect_vec();
 
@@ -196,13 +244,74 @@ impl DFA {
         self.recreate_graph(p.iter().filter(|&it| !it.is_empty()).collect_vec());
     }
 
+    fn deduplicate_redundant_edges(&mut self) {
+        for state in self.graph.node_indices().collect_vec() {
+            let mut next_nodes = HashMap::new();
+            for edge in self.graph.edges_directed(state, Direction::Outgoing) {
+                next_nodes
+                    .entry(edge.target().index())
+                    .or_insert_with(HashMap::new)
+                    .entry(edge.weight().value())
+                    .or_insert_with(Vec::new)
+                    .push(edge.id());
+            }
+
+            for (next_index, mut grapheme_map) in next_nodes {
+                for edges in grapheme_map.values_mut() {
+                    let graphemes = edges
+                        .iter()
+                        .map(|edge| self.graph[*edge].clone())
+                        .collect_vec();
+                    let new_graphemes = self.merge_graphemes(graphemes);
+                    if new_graphemes.len() == edges.len() {
+                        continue;
+                    }
+                    for edge in edges {
+                        self.graph.remove_edge(*edge);
+                    }
+                    for grapheme in new_graphemes.iter().rev() {
+                        self.graph.add_edge(
+                            state,
+                            self.graph.from_index(next_index),
+                            grapheme.clone(),
+                        );
+                    }
+                }
+            }
+        }
+    }
+
+    fn merge_graphemes(&self, mut graphemes: Vec<Grapheme>) -> Vec<Grapheme> {
+        graphemes.sort_by_key(|grapheme| (grapheme.minimum(), grapheme.maximum()));
+
+        let mut result = Vec::new();
+        for grapheme in graphemes {
+            match result.last_mut() {
+                None => result.push(grapheme),
+                Some(last) => {
+                    if last.maximum() + 1 >= grapheme.minimum() {
+                        *last = Grapheme::new(
+                            last.chars().clone(),
+                            last.minimum(),
+                            max(last.maximum(), grapheme.maximum()),
+                            &self.config,
+                        );
+                    } else {
+                        result.push(grapheme);
+                    }
+                }
+            }
+        }
+        result
+    }
+
     fn get_initial_partition(&self) -> Vec<HashSet<State>> {
         let (final_states, non_final_states): (HashSet<State>, HashSet<State>) = self
             .graph
             .node_indices()
-            .partition(|&state| !self.final_state_indices.contains(&state.index()));
+            .partition(|&state| self.graph[state].status != StateStatus::Intermediate);
 
-        vec![final_states, non_final_states]
+        vec![non_final_states, final_states]
     }
 
     fn get_parent_states(&self, a: &HashSet<State>, label: &Grapheme) -> HashSet<State> {
@@ -225,49 +334,244 @@ impl DFA {
         x
     }
 
-    fn recreate_graph(&mut self, p: Vec<&HashSet<State>>) {
+    fn recreate_graph(&mut self, equivalence_classes: Vec<&HashSet<State>>) {
         let mut graph = StableGraph::<StateLabel, EdgeLabel>::new();
-        let mut final_state_indices = HashSet::new();
         let mut state_mappings = HashMap::new();
         let mut new_initial_state: Option<NodeIndex> = None;
 
-        for equivalence_class in p.iter() {
-            let new_state = graph.add_node("".to_string());
+        for equivalence_class in equivalence_classes.iter() {
+            let new_state = graph.add_node(StateLabel {
+                description: format!(
+                    "{:?}",
+                    equivalence_class
+                        .iter()
+                        .map(|state| state.index())
+                        .collect_vec()
+                ),
+                status: self.graph[*equivalence_class.iter().next().unwrap()].status,
+            });
 
             for old_state in equivalence_class.iter() {
                 if self.initial_state == *old_state {
                     new_initial_state = Some(new_state);
+                    graph[new_state].description.push_str(" initial");
                 }
                 state_mappings.insert(*old_state, new_state);
             }
         }
 
-        for equivalence_class in p.iter() {
-            let old_source_state = *equivalence_class.iter().next().unwrap();
-            let new_source_state = state_mappings.get(&old_source_state).unwrap();
+        for equivalence_class in equivalence_classes.iter() {
+            let new_source_state = state_mappings
+                .get(equivalence_class.iter().next().unwrap())
+                .unwrap();
 
-            for old_target_state in self.graph.neighbors(old_source_state) {
-                let edge = self
-                    .graph
-                    .find_edge(old_source_state, old_target_state)
-                    .unwrap();
+            let mut added_edges: HashSet<(Grapheme, usize)> = HashSet::new();
 
-                let grapheme = self.graph.edge_weight(edge).unwrap().clone();
-                let new_target_state = state_mappings.get(&old_target_state).unwrap();
+            for edge in equivalence_class
+                .iter()
+                .flat_map(|from_state| self.graph.edges_directed(*from_state, Direction::Outgoing))
+            {
+                let grapheme = edge.weight();
+                let new_target_state = state_mappings.get(&edge.target()).unwrap();
 
-                graph.add_edge(*new_source_state, *new_target_state, grapheme.clone());
-
-                if self.final_state_indices.contains(&old_target_state.index()) {
-                    final_state_indices.insert(new_target_state.index());
+                if added_edges.insert((grapheme.clone(), new_target_state.index())) {
+                    graph.add_edge(*new_source_state, *new_target_state, grapheme.clone());
                 }
             }
         }
         self.initial_state = new_initial_state.unwrap();
-        self.final_state_indices = final_state_indices;
         self.graph = graph;
     }
 }
 
+impl Display for StateLabel {
+    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
+        write!(f, "{} ({:?})", self.description, self.status)
+    }
+}
+
+impl<T> InputState<T> {
+    fn map_any<R, F, G>(&self, f: F, g: G) -> InputState<R>
+    where
+        F: FnOnce(&T) -> R,
+        G: FnOnce(&T) -> R,
+    {
+        match self {
+            Self::Left(x) => InputState::Left(f(x)),
+            Self::Both(x, y) => InputState::Both(f(x), g(y)),
+        }
+    }
+}
+
+impl<'a> DFASubtractionBuilder<'a> {
+    fn subtract(left: &'a DFA, right: &'a DFA) -> Option<DFA> {
+        if left.config != right.config {
+            None
+        } else {
+            let mut builder = Self {
+                left,
+                right,
+                result: DFA::new(&left.config),
+                new_nodes: HashMap::new(),
+                queue: VecDeque::new(),
+                enqueued: HashSet::new(),
+            };
+            builder.build();
+            Some(builder.result)
+        }
+    }
+
+    fn output_state_status(&self, idx: InputState<usize>) -> StateStatus {
+        match idx.map_any(
+            |state_left| self.left.graph[self.left.graph.from_index(*state_left)].status,
+            |state_right| self.right.graph[self.right.graph.from_index(*state_right)].status,
+        ) {
+            InputState::Both(_, StateStatus::Accept) => StateStatus::Intermediate,
+            InputState::Both(StateStatus::Accept, _) => StateStatus::Accept,
+            InputState::Left(StateStatus::Accept) => StateStatus::Accept,
+            _ => StateStatus::Intermediate,
+        }
+    }
+
+    fn input_to_output_state_space(&mut self, idx: &InputState<usize>) -> State {
+        if *idx
+            == InputState::Both(
+                self.left.initial_state.index(),
+                self.right.initial_state.index(),
+            )
+        {
+            self.result.initial_state
+        } else {
+            match self.new_nodes.get(&idx) {
+                Some(state) => *state,
+                None => {
+                    let new_state = self.result.graph.add_node(StateLabel {
+                        description: format!("{:?}", idx),
+                        status: self.output_state_status(idx.clone()),
+                    });
+                    self.new_nodes.insert(idx.clone(), new_state);
+                    new_state
+                }
+            }
+        }
+    }
+
+    fn add_edge(&mut self, new_from: State, grapheme: Grapheme, input: &InputState<usize>) {
+        let new_to = self.input_to_output_state_space(input);
+        self.result.graph.add_edge(new_from, new_to, grapheme);
+        if !self.enqueued.contains(&input) {
+            self.queue.push_back(input.clone());
+            self.enqueued.insert(input.clone());
+        }
+    }
+
+    fn overlap_all_grapheme(
+        &mut self,
+        left: Grapheme,
+        rights: Vec<(Grapheme, usize)>,
+    ) -> (Vec<Grapheme>, Vec<(Grapheme, usize)>) {
+        let mut overlaps = Vec::new();
+        let mut unoverlapped = vec![left];
+
+        for (right_grapheme, right_idx) in rights {
+            let mut new_unoverlapped = Vec::new();
+            for left_grapheme in unoverlapped {
+                for (new_grapheme, overlap_state) in
+                    left_grapheme.overlap_with(&right_grapheme).unwrap()
+                {
+                    match overlap_state {
+                        GraphemeOverlapState::Right => continue,
+                        GraphemeOverlapState::Overlap => overlaps.push((new_grapheme, right_idx)),
+                        GraphemeOverlapState::Left => new_unoverlapped.push(new_grapheme),
+                    }
+                }
+            }
+            unoverlapped = new_unoverlapped;
+        }
+        (unoverlapped, overlaps)
+    }
+
+    fn build(&mut self) {
+        let input_initial = InputState::Both(
+            self.left.initial_state.index(),
+            self.right.initial_state.index(),
+        );
+        self.queue.push_back(input_initial.clone());
+        self.enqueued.insert(input_initial);
+
+        while let Some(idx) = self.queue.pop_front() {
+            let new_from = self.input_to_output_state_space(&idx);
+
+            match idx.map_any(
+                |left_idx| {
+                    self.left
+                        .outgoing_edges(self.left.graph.from_index(*left_idx))
+                },
+                |right_idx| {
+                    self.right
+                        .outgoing_edges(self.right.graph.from_index(*right_idx))
+                },
+            ) {
+                InputState::Left(left_edges) => {
+                    for edge in left_edges {
+                        self.add_edge(
+                            new_from,
+                            edge.weight().clone(),
+                            &InputState::Left(edge.target().index()),
+                        );
+                    }
+                }
+                InputState::Both(left_edges, right_edges) => {
+                    let right_edges_vec = right_edges.collect_vec();
+
+                    for edge_left in left_edges {
+                        let grapheme_left = edge_left.weight();
+                        let edge_left_to = edge_left.target().index();
+
+                        let matching_edges = right_edges_vec
+                            .iter()
+                            .filter(|edge| edge.weight().value() == grapheme_left.value())
+                            .collect_vec();
+
+                        let (unoverlapped, overlapped) = self.overlap_all_grapheme(
+                            grapheme_left.clone(),
+                            matching_edges
+                                .iter()
+                                .map(|edge| (edge.weight().clone(), edge.target().index()))
+                                .collect_vec(),
+                        );
+
+                        for new_grapheme in unoverlapped {
+                            self.add_edge(
+                                new_from,
+                                new_grapheme.clone(),
+                                &InputState::Left(edge_left_to),
+                            );
+                        }
+
+                        for (new_grapheme, edge_right_to) in overlapped {
+                            self.add_edge(
+                                new_from,
+                                new_grapheme.clone(),
+                                &InputState::Both(edge_left_to, edge_right_to),
+                            );
+                        }
+                    }
+                }
+            }
+        }
+
+        self.result.alphabet = self
+            .result
+            .graph
+            .edge_indices()
+            .map(|e| self.result.graph[e].clone())
+            .collect();
+
+        self.result.minimize();
+    }
+}
+
 #[cfg(test)]
 mod tests {
     use super::*;
@@ -297,6 +601,28 @@ mod tests {
         assert_eq!(dfa.is_final_state(final_state), true);
     }
 
+    #[test]
+    fn test_subtraction() {
+        let config = RegExpConfig::new();
+        let dfa1 = DFA::from(
+            vec![
+                GraphemeCluster::from("abcd", &RegExpConfig::new()),
+                GraphemeCluster::from("abcf", &RegExpConfig::new()),
+            ],
+            &config,
+        );
+        let dfa2 = DFA::from(
+            vec![GraphemeCluster::from("abcd", &RegExpConfig::new())],
+            &config,
+        );
+
+        let dfa_option = dfa1.subtract(&dfa2);
+        assert!(dfa_option.is_some());
+
+        let dfa = dfa_option.unwrap();
+        assert_eq!(dfa.state_count(), 5);
+    }
+
     #[test]
     fn test_outgoing_edges() {
         let config = RegExpConfig::new();
diff --git a/src/main.rs b/src/main.rs
index cdfe71e..d913600 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -196,6 +196,28 @@ struct CLI {
     )]
     file_path: Option<PathBuf>,
 
+    #[structopt(
+        name = "exclusions",
+        value_name = "INPUT",
+        long,
+        conflicts_with = "exclusions-file",
+        help = "One or more negative test cases separated by blank space"
+    )]
+    exclusions: Option<Vec<String>>,
+
+    #[structopt(
+        name = "exclusions-file",
+        value_name = "FILE",
+        long,
+        parse(from_os_str),
+        help = "Reads negative test cases on separate lines from a file",
+        long_help = "Reads negative test cases on separate lines from a file.\n\n\
+                     Lines may be ended with either a newline (`\\n`) or\n\
+                     a carriage return with a line feed (`\\r\\n`).\n\
+                     The final line ending is optional."
+    )]
+    exclusions_file_path: Option<PathBuf>,
+
     #[structopt(
         name = "min-repetitions",
         value_name = "QUANTITY",
@@ -224,14 +246,17 @@ fn main() {
     handle_input(&cli, obtain_input(&cli));
 }
 
+fn read_input_file(file_path: &PathBuf) -> Result<Vec<String>, Error> {
+    let file_content = std::fs::read_to_string(&file_path)?;
+
+    Ok(file_content.lines().map(|it| it.to_string()).collect_vec())
+}
+
 fn obtain_input(cli: &CLI) -> Result<Vec<String>, Error> {
     if !cli.input.is_empty() {
         Ok(cli.input.clone())
     } else if let Some(file_path) = &cli.file_path {
-        match std::fs::read_to_string(&file_path) {
-            Ok(file_content) => Ok(file_content.lines().map(|it| it.to_string()).collect_vec()),
-            Err(error) => Err(error),
-        }
+        read_input_file(file_path)
     } else {
         Err(Error::new(
             ErrorKind::InvalidInput,
@@ -240,80 +265,105 @@ fn obtain_input(cli: &CLI) -> Result<Vec<String>, Error> {
     }
 }
 
-fn handle_input(cli: &CLI, input: Result<Vec<String>, Error>) {
-    match input {
-        Ok(test_cases) => {
-            let mut builder = RegExpBuilder::from(&test_cases);
-            let mut conversion_features = vec![];
+fn file_error(source: &str, error: Error) {
+    match error.kind() {
+        ErrorKind::NotFound => eprintln!("error: the specified {} file could not be found", source),
+        ErrorKind::InvalidData => eprintln!(
+            "error: the specified {} file's encoding is not valid UTF-8",
+            source
+        ),
+        ErrorKind::PermissionDenied => eprintln!(
+            "permission denied: the {} specified file could not be opened",
+            source
+        ),
+        _ => eprintln!("error on {} file: {}", source, error),
+    }
+}
 
-            if cli.is_digit_converted {
-                conversion_features.push(Feature::Digit);
-            }
+fn build_builder(cli: &CLI, test_cases: &[String]) -> RegExpBuilder {
+    let mut builder = RegExpBuilder::from(&test_cases);
 
-            if cli.is_non_digit_converted {
-                conversion_features.push(Feature::NonDigit);
+    if let Some(exclusions) = &cli.exclusions {
+        builder.with_negative_matches(&exclusions);
+    } else if let Some(exclusions_file_path) = &cli.exclusions_file_path {
+        match read_input_file(exclusions_file_path) {
+            Ok(lines) => {
+                builder.with_negative_matches(&lines);
             }
-
-            if cli.is_space_converted {
-                conversion_features.push(Feature::Space);
+            Err(error) => {
+                file_error("negative match", error);
+                panic!();
             }
+        }
+    }
 
-            if cli.is_non_space_converted {
-                conversion_features.push(Feature::NonSpace);
-            }
+    let mut conversion_features = vec![];
 
-            if cli.is_word_converted {
-                conversion_features.push(Feature::Word);
-            }
+    if cli.is_digit_converted {
+        conversion_features.push(Feature::Digit);
+    }
 
-            if cli.is_non_word_converted {
-                conversion_features.push(Feature::NonWord);
-            }
+    if cli.is_non_digit_converted {
+        conversion_features.push(Feature::NonDigit);
+    }
 
-            if cli.is_repetition_converted {
-                conversion_features.push(Feature::Repetition);
-            }
+    if cli.is_space_converted {
+        conversion_features.push(Feature::Space);
+    }
 
-            if cli.is_case_ignored {
-                conversion_features.push(Feature::CaseInsensitivity);
-            }
+    if cli.is_non_space_converted {
+        conversion_features.push(Feature::NonSpace);
+    }
 
-            if cli.is_group_captured {
-                conversion_features.push(Feature::CapturingGroup);
-            }
+    if cli.is_word_converted {
+        conversion_features.push(Feature::Word);
+    }
 
-            if !conversion_features.is_empty() {
-                builder.with_conversion_of(&conversion_features);
-            }
+    if cli.is_non_word_converted {
+        conversion_features.push(Feature::NonWord);
+    }
 
-            if cli.is_non_ascii_char_escaped {
-                builder.with_escaping_of_non_ascii_chars(
-                    cli.is_astral_code_point_converted_to_surrogate,
-                );
-            }
+    if cli.is_repetition_converted {
+        conversion_features.push(Feature::Repetition);
+    }
 
-            if cli.is_output_colorized {
-                builder.with_syntax_highlighting();
-            }
+    if cli.is_case_ignored {
+        conversion_features.push(Feature::CaseInsensitivity);
+    }
+
+    if cli.is_group_captured {
+        conversion_features.push(Feature::CapturingGroup);
+    }
+
+    if !conversion_features.is_empty() {
+        builder.with_conversion_of(&conversion_features);
+    }
+
+    if cli.is_non_ascii_char_escaped {
+        builder.with_escaping_of_non_ascii_chars(cli.is_astral_code_point_converted_to_surrogate);
+    }
+
+    if cli.is_output_colorized {
+        builder.with_syntax_highlighting();
+    }
 
-            builder
-                .with_minimum_repetitions(cli.minimum_repetitions)
-                .with_minimum_substring_length(cli.minimum_substring_length);
+    builder
+        .with_minimum_repetitions(cli.minimum_repetitions)
+        .with_minimum_substring_length(cli.minimum_substring_length);
+
+    builder
+}
+
+fn handle_input(cli: &CLI, input: Result<Vec<String>, Error>) {
+    match input {
+        Ok(test_cases) => {
+            let mut builder = build_builder(cli, &test_cases);
 
             let regexp = builder.build();
 
             println!("{}", regexp);
         }
-        Err(error) => match error.kind() {
-            ErrorKind::NotFound => eprintln!("error: the specified file could not be found"),
-            ErrorKind::InvalidData => {
-                eprintln!("error: the specified file's encoding is not valid UTF-8")
-            }
-            ErrorKind::PermissionDenied => {
-                eprintln!("permission denied: the specified file could not be opened")
-            }
-            _ => eprintln!("error: {}", error),
-        },
+        Err(error) => file_error("input", error),
     }
 }
 
diff --git a/src/regexp/builder.rs b/src/regexp/builder.rs
index 4e868a8..d3f830c 100644
--- a/src/regexp/builder.rs
+++ b/src/regexp/builder.rs
@@ -22,7 +22,8 @@ use std::path::PathBuf;
 
 /// This struct builds regular expressions from user-provided test cases.
 pub struct RegExpBuilder {
-    test_cases: Vec<String>,
+    positive_test_cases: Vec<String>,
+    negative_test_cases: Vec<String>,
     config: RegExpConfig,
 }
 
@@ -37,7 +38,8 @@ impl RegExpBuilder {
             panic!("No test cases have been provided for regular expression generation");
         }
         Self {
-            test_cases: test_cases.iter().cloned().map(|it| it.into()).collect_vec(),
+            positive_test_cases: test_cases.iter().cloned().map(|it| it.into()).collect_vec(),
+            negative_test_cases: Vec::new(),
             config: RegExpConfig::new(),
         }
     }
@@ -57,10 +59,9 @@ impl RegExpBuilder {
     /// - the file cannot be opened because of conflicting permissions
     pub fn from_file<T: Into<PathBuf>>(file_path: T) -> Self {
         match std::fs::read_to_string(file_path.into()) {
-            Ok(file_content) => Self {
-                test_cases: file_content.lines().map(|it| it.to_string()).collect_vec(),
-                config: RegExpConfig::new(),
-            },
+            Ok(file_content) => {
+                Self::from(&file_content.lines().map(|it| it.to_string()).collect_vec())
+            }
             Err(error) => match error.kind() {
                 ErrorKind::NotFound => panic!("The specified file could not be found"),
                 ErrorKind::InvalidData => {
@@ -138,10 +139,23 @@ impl RegExpBuilder {
         self
     }
 
+    pub fn with_negative_matches<T: Clone + Into<String>>(
+        &mut self,
+        test_cases: &[T],
+    ) -> &mut Self {
+        self.negative_test_cases = test_cases.iter().cloned().map(|it| it.into()).collect_vec();
+        self
+    }
+
     /// Builds the actual regular expression using the previously given settings.
     /// Every generated regular expression is surrounded by the anchors `^` and `$`
     /// so that substrings not being part of the test cases are not matched accidentally.
     pub fn build(&mut self) -> String {
-        RegExp::from(&mut self.test_cases, &self.config).to_string()
+        RegExp::from(
+            &mut self.positive_test_cases,
+            &mut self.negative_test_cases,
+            &self.config,
+        )
+        .to_string()
     }
 }
diff --git a/src/regexp/regexp.rs b/src/regexp/regexp.rs
index 3570c8c..258f069 100644
--- a/src/regexp/regexp.rs
+++ b/src/regexp/regexp.rs
@@ -29,13 +29,16 @@ pub struct RegExp {
 }
 
 impl RegExp {
-    pub(crate) fn from(test_cases: &mut Vec<String>, config: &RegExpConfig) -> Self {
-        if config.is_case_insensitive_matching() {
-            Self::convert_to_lowercase(test_cases);
+    pub(crate) fn from(
+        positive_test_cases: &mut Vec<String>,
+        negative_test_cases: &mut Vec<String>,
+        config: &RegExpConfig,
+    ) -> Self {
+        let mut dfa = Self::build_dfa(positive_test_cases, config);
+        if !negative_test_cases.is_empty() {
+            let negative_dfa = Self::build_dfa(negative_test_cases, config);
+            dfa = dfa.subtract(&negative_dfa).unwrap();
         }
-        Self::sort(test_cases);
-        let grapheme_clusters = Self::grapheme_clusters(&test_cases, config);
-        let dfa = DFA::from(grapheme_clusters, config);
         let ast = Expression::from(dfa, config);
         Self {
             ast,
@@ -43,11 +46,17 @@ impl RegExp {
         }
     }
 
+    fn build_dfa(test_cases: &mut Vec<String>, config: &RegExpConfig) -> DFA {
+        if config.is_case_insensitive_matching() {
+            Self::convert_to_lowercase(test_cases);
+        }
+        Self::sort(test_cases);
+        let grapheme_clusters = Self::grapheme_clusters(&test_cases, config);
+        DFA::from(grapheme_clusters, config)
+    }
+
     fn convert_to_lowercase(test_cases: &mut Vec<String>) {
-        std::mem::replace(
-            test_cases,
-            test_cases.iter().map(|it| it.to_lowercase()).collect_vec(),
-        );
+        *test_cases = test_cases.iter().map(|it| it.to_lowercase()).collect_vec();
     }
 
     fn sort(test_cases: &mut Vec<String>) {


Test patch:
diff --git a/tests/cli_integration_tests.rs b/tests/cli_integration_tests.rs
index 069884e..cfba2c1 100644
--- a/tests/cli_integration_tests.rs
+++ b/tests/cli_integration_tests.rs
@@ -83,7 +83,7 @@ mod no_conversion {
             grex.args(&["-f", file.path().to_str().unwrap()]);
             grex.assert()
                 .success()
-                .stdout(predicate::eq("^(?:b\\\\n|äöü|[ac♥])$\n"));
+                .stdout(predicate::eq("^(?:b\\\\n|äöü|[ac♥])?$\n"));
         }
 
         #[test]
@@ -120,7 +120,7 @@ mod no_conversion {
                 .success()
                 .stdout(predicate::str::is_empty())
                 .stderr(predicate::eq(
-                    "error: the specified file could not be found\n",
+                    "error: the specified input file could not be found\n",
                 ));
         }
 
diff --git a/tests/lib_integration_tests.rs b/tests/lib_integration_tests.rs
index 4f7a073..b5f40e2 100644
--- a/tests/lib_integration_tests.rs
+++ b/tests/lib_integration_tests.rs
@@ -15,6 +15,7 @@
  */
 
 use grex::{Feature, RegExpBuilder};
+use itertools::Itertools;
 use regex::Regex;
 use rstest::rstest;
 use std::io::Write;
@@ -180,7 +181,7 @@ mod no_conversion {
             case(vec!["a", "aa"], "^a{1,2}$"),
             case(vec!["aaa", "a", "aa"], "^a{1,3}$"),
             case(vec!["aaaa", "a", "aa"], "^(?:a{1,2}|a{4})$"),
-            case(vec!["a", "aa", "aaa", "aaaa", "aaab"], "^(?:a{3}b|a{1,4})$"),
+            case(vec!["a", "aa", "aaa", "aaaa", "aaab"], "^(?:a{3}b?|a{1,2}|a{4})$"),
             case(vec!["baabaaaaaabb"], "^ba{2}ba{6}b{2}$"),
             case(vec!["aabbaabbaaa"], "^(?:a{2}b{2}){2}a{3}$"),
             case(vec!["aabbaa"], "^a{2}b{2}a{2}$"),
@@ -298,7 +299,7 @@ mod no_conversion {
             case(vec!["xy̆y̆z", "xy̆y̆y̆y̆z"], "^x(?:y̆y̆|(?:y̆){4})z$"),
             case(vec!["aaa", "a", "aa"], "^a(?:aa?)?$"),
             case(vec!["a", "aa", "aaa", "aaaa"], "^(?:aaa|aa?|a{4})$"),
-            case(vec!["a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa"], "^(?:aaa|aa?|a{4,6})$")
+            case(vec!["a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa"], "^(?:a(?:aa?)?|a{4,6})$")
         )]
         fn succeeds_with_increased_minimum_repetitions(
             test_cases: Vec<&str>,
@@ -1663,6 +1664,101 @@ mod word_non_word_conversion {
     }
 }
 
+mod negative_testcases {
+    use super::*;
+
+    mod no_repetition {
+        use super::*;
+
+        #[rstest(positive_test_cases, negative_test_cases, expected_output,
+            case(vec!["a"], vec!["b"], "^a$"),
+            case(vec!["a"], vec!["a"], "^$"),
+            case(vec!["ab"], vec!["bc"], "^ab$"),
+            case(vec!["ab"], vec!["aa"], "^ab$"),
+            case(vec!["a", "b"], vec![], "^[ab]$"),
+            case(vec!["a", "b"], vec!["a"], "^b$"),
+            case(vec!["a", "b"], vec!["a","b"], "^$"),
+            case(vec!["a", "b"], vec!["c"], "^[ab]$"),
+            case(vec!["abcdef"], vec!["012345"], "^abcdef$"),
+            case(vec!["aa"], vec!["aaa"], "^aa$"),
+            case(vec!["aaa"], vec!["aa"], "^aaa$"),
+            case(vec!["aaa"], vec!["aab"], "^aaa$"),
+            case(vec!["a", "aa", "aaa"], vec!["aa"], "^a(?:aa)?$"),
+            case(vec!["a", "aaaaaaaaa"], vec!["aa", "aaaa"], "^a(?:aaaaaaaa)?$"),
+            case(vec!["a", "aaaaaaaaa", "aaaaaab"], vec!["aaaaa"], "^a(?:aaaaa(?:aaa|b))?$"),
+        )]
+        fn succeeds(
+            positive_test_cases: Vec<&str>,
+            negative_test_cases: Vec<&str>,
+            expected_output: &str,
+        ) {
+            let regexp = RegExpBuilder::from(&positive_test_cases)
+                .with_negative_matches(&negative_test_cases)
+                .build();
+            assert_eq!(
+                regexp, expected_output,
+                "\n\npositive cases: {:?}\nnegative cases: {:?}\nexpected: {}\nactual: {}\n\n",
+                positive_test_cases, negative_test_cases, expected_output, regexp
+            );
+            test_if_regexp_matches_test_cases(
+                expected_output,
+                positive_test_cases
+                    .iter()
+                    .filter(|case| !negative_test_cases.contains(case))
+                    .copied()
+                    .collect_vec(),
+            );
+            test_if_regexp_doesnt_match_test_cases(expected_output, negative_test_cases.clone());
+        }
+    }
+
+    mod repetition {
+        use super::*;
+
+        #[rstest(positive_test_cases, negative_test_cases, expected_output,
+            case(vec!["a"], vec!["b"], "^a$"),
+            case(vec!["a"], vec!["a"], "^$"),
+            case(vec!["ab"], vec!["bc"], "^ab$"),
+            case(vec!["ab"], vec!["aa"], "^ab$"),
+            case(vec!["a", "b"], vec![], "^[ab]$"),
+            case(vec!["a", "b"], vec!["a"], "^b$"),
+            case(vec!["a", "b"], vec!["a","b"], "^$"),
+            case(vec!["a", "b"], vec!["c"], "^[ab]$"),
+            case(vec!["abcdef"], vec!["012345"], "^abcdef$"),
+            case(vec!["aa"], vec!["aaa"], "^a{2}$"),
+            case(vec!["aaa"], vec!["aa"], "^a{3}$"),
+            case(vec!["aaa"], vec!["aab"], "^a{3}$"),
+            case(vec!["a", "aa", "aaa"], vec!["aa"], "^(?:a|a{3})$"),
+            case(vec!["a", "aaaaaaaaa"], vec!["aa", "aaaa"], "^(?:a|a{9})$"),
+            case(vec!["a", "aaaaaaaaa", "aaaaaab"], vec!["aaaaa"], "^(?:a{6}b|a|a{9})$"),
+        )]
+        fn succeeds(
+            positive_test_cases: Vec<&str>,
+            negative_test_cases: Vec<&str>,
+            expected_output: &str,
+        ) {
+            let regexp = RegExpBuilder::from(&positive_test_cases)
+                .with_negative_matches(&negative_test_cases)
+                .with_conversion_of(&[Feature::Repetition])
+                .build();
+            assert_eq!(
+                regexp, expected_output,
+                "\n\npositive cases: {:?}\nnegative cases: {:?}\nexpected: {}\nactual: {}\n\n",
+                positive_test_cases, negative_test_cases, expected_output, regexp
+            );
+            test_if_regexp_matches_test_cases(
+                expected_output,
+                positive_test_cases
+                    .iter()
+                    .filter(|case| !negative_test_cases.contains(case))
+                    .copied()
+                    .collect_vec(),
+            );
+            test_if_regexp_doesnt_match_test_cases(expected_output, negative_test_cases.clone());
+        }
+    }
+}
+
 fn test_if_regexp_is_correct(regexp: String, expected_output: &str, test_cases: &[&str]) {
     assert_eq!(
         regexp, expected_output,
@@ -1676,7 +1772,19 @@ fn test_if_regexp_matches_test_cases(expected_output: &str, test_cases: Vec<&str
     for test_case in test_cases {
         assert!(
             re.is_match(test_case),
-            "\n\n\"{}\" does not match regex {}\n\n",
+            "\n\n\"{}\" does not match regex \"{}\"\n\n",
+            test_case,
+            expected_output
+        );
+    }
+}
+
+fn test_if_regexp_doesnt_match_test_cases(expected_output: &str, test_cases: Vec<&str>) {
+    let re = Regex::new(expected_output).unwrap();
+    for test_case in test_cases {
+        assert!(
+            !re.is_match(test_case),
+            "\n\n\"{}\" does match regex \"{}\"\n\n",
             test_case,
             expected_output
         );
diff --git a/tests/property_tests.rs b/tests/property_tests.rs
index 94d0d91..f26fce5 100644
--- a/tests/property_tests.rs
+++ b/tests/property_tests.rs
@@ -158,6 +158,31 @@ proptest! {
         }
     }
 
+    #[test]
+    #[ignore]
+    fn regexes_not_matching_other_strings_with_default_settings_restricted_alphabet(
+        test_cases in prop::collection::hash_set("[a-f]{1,10}", 1..=10),
+        other_strings in prop::collection::hash_set("[a-f]{1,10}", 1..=100)
+    ) {
+        let test_cases_vec = test_cases.iter().cloned().collect::<Vec<_>>();
+        let regexp = RegExpBuilder::from(&test_cases_vec).build();
+        let compiled_regexp = compile_regexp(&regexp).unwrap();
+        prop_assert!(other_strings.iter().filter(|other_string| !test_cases_vec.contains(other_string)).all(|other_string| !compiled_regexp.is_match(&other_string)));
+    }
+
+
+    #[test]
+    #[ignore]
+    fn regexes_not_matching_other_strings_with_repetition_restricted_alphabet(
+        test_cases in prop::collection::hash_set("[a-f]{1,10}", 1..=10),
+        other_strings in prop::collection::hash_set("[a-f]{1,10}", 1..=100)
+    ) {
+        let test_cases_vec = test_cases.iter().cloned().collect::<Vec<_>>();
+        let regexp = RegExpBuilder::from(&test_cases_vec).with_conversion_of(&[Feature::Repetition]).build();
+        let compiled_regexp = compile_regexp(&regexp).unwrap();
+        prop_assert!(other_strings.iter().filter(|other_string| !test_cases_vec.contains(other_string)).all(|other_string| !compiled_regexp.is_match(&other_string)));
+    }
+
     #[test]
     #[ignore]
     fn regexes_not_matching_other_strings_with_escape_sequences(
@@ -174,6 +199,73 @@ proptest! {
             }
         }
     }
+
+    #[test]
+    #[ignore]
+    fn regexes_not_matching_negative_test_cases(
+        test_cases in prop::collection::hash_set("[a-f]{1,20}", 1..=10),
+        negative_test_cases in prop::collection::hash_set("[a-f]{1,20}", 1..=10)
+    ) {
+        let test_cases_vec = test_cases.iter().cloned().collect::<Vec<_>>();
+        let negative_test_cases_vec = negative_test_cases.iter().cloned().collect::<Vec<_>>();
+        let regexp = RegExpBuilder::from(&test_cases_vec)
+            .with_negative_matches(&negative_test_cases_vec)
+            .build();
+        let compiled_regexp = compile_regexp(&regexp).unwrap();
+        for test_case in negative_test_cases {
+            prop_assert_eq!(compiled_regexp.is_match(&test_case), false, "Negative test case \"{}\" matched regex \"{}\"", test_case, regexp);
+        }
+        for test_case in test_cases.iter().filter(|test_case| !negative_test_cases_vec.contains(&test_case)) {
+            prop_assert_eq!(compiled_regexp.is_match(&test_case), true, "Positive test case \"{}\" didn't match regex \"{}\"", test_case, regexp);
+        }
+    }
+
+    #[test]
+    #[ignore]
+    fn regexes_not_matching_negative_test_cases_with_repetition(
+        test_cases in prop::collection::hash_set("[a-f]{1,20}", 1..=10),
+        negative_test_cases in prop::collection::hash_set("[a-f]{1,20}", 1..=10)
+    ) {
+        let test_cases_vec = test_cases.iter().cloned().collect::<Vec<_>>();
+        let negative_test_cases_vec = negative_test_cases.iter().cloned().collect::<Vec<_>>();
+        let regexp = RegExpBuilder::from(&test_cases_vec)
+            .with_negative_matches(&negative_test_cases_vec)
+            .with_conversion_of(&[Feature::Repetition])
+            .build();
+        if let Ok(compiled_regexp) = compile_regexp(&regexp) {
+            for test_case in negative_test_cases {
+                prop_assert_eq!(compiled_regexp.is_match(&test_case), false, "Negative test case \"{}\" matched regex \"{}\"", test_case, regexp);
+            }
+            for test_case in test_cases.iter().filter(|test_case| !negative_test_cases_vec.contains(&test_case)) {
+                prop_assert_eq!(compiled_regexp.is_match(&test_case), true, "Positive test case \"{}\" didn't matched regex \"{}\"", test_case, regexp);
+            }
+        }
+    }
+
+
+    #[test]
+    #[ignore]
+    fn regexes_not_matching_negative_test_cases_with_conversion_features_ascii_printable(
+        test_cases in prop::collection::hash_set("[ -~]{1,20}", 1..=10),
+        negative_test_cases in prop::collection::hash_set("[ -~]{1,20}", 1..=10),
+        conversion_features in prop::collection::hash_set(conversion_feature_strategy(), 1..=9),
+        minimum_repetitions in 1..100u32,
+        minimum_substring_length in 1..100u32
+    ) {
+        let test_cases_vec = test_cases.iter().cloned().collect::<Vec<_>>();
+        let negative_test_cases_vec = negative_test_cases.iter().cloned().collect::<Vec<_>>();
+        let regexp = RegExpBuilder::from(&test_cases_vec)
+            .with_negative_matches(&negative_test_cases_vec)
+            .with_conversion_of(&conversion_features.into_iter().collect::<Vec<_>>())
+            .with_minimum_repetitions(minimum_repetitions)
+            .with_minimum_substring_length(minimum_substring_length)
+            .build();
+        if let Ok(compiled_regexp) = compile_regexp(&regexp) {
+            for test_case in negative_test_cases {
+                prop_assert_eq!(compiled_regexp.is_match(&test_case), false, "Negative test case \"{}\" matched regex \"{}\"", test_case, regexp);
+            }
+        }
+    }
 }
 
 fn conversion_feature_strategy() -> impl Strategy<Value = Feature> {