diff --git a/tests/test_regexp.rs b/tests/test_regexp.rs
--- a/tests/test_regexp.rs
+++ b/tests/test_regexp.rs
@@ -1,7 +1,68 @@
 use regexp::Regexp;
 
 #[test]
-fn test_eval() {
-	let r = Regexp::new(&String::from("(ab)*"));
+fn test_eval_basic_nfa() {
+	let r = Regexp::new(&String::from("abc"));
+	assert!(r.eval(String::from("abc")));
+	assert!(!r.eval(String::from("ab")));
+	assert!(!r.eval(String::from("abcd")));
+}
+
+#[test]
+fn test_eval_basic_dfa() {
+	let r = Regexp::new(&String::from("abc")).determinize();
+	assert!(r.eval(String::from("abc")));
+	assert!(!r.eval(String::from("ab")));
+	assert!(!r.eval(String::from("abcd")));
+}
+
+#[test]
+fn test_eval_empty_nfa() {
+	assert!(Regexp::new(&String::from("a*")).eval(String::from("")));
+	assert!(Regexp::new(&String::from("")).eval(String::from("")));
+	assert!(!Regexp::new(&String::from("")).eval(String::from("a")));
+	assert!(!Regexp::new(&String::from("a")).eval(String::from("")));
+}
+
+#[test]
+fn test_eval_empty_dfa() {
+	assert!(Regexp::new(&String::from("a*")).determinize().eval(String::from("")));
+	assert!(Regexp::new(&String::from("")).determinize().eval(String::from("")));
+	assert!(!Regexp::new(&String::from("")).determinize().eval(String::from("a")));
+}
+
+#[test]
+fn test_eval_asterisk_nfa() {
+	let r = Regexp::new(&String::from("a*b*"));
+	assert!(r.eval(String::from("a")));
 	assert!(r.eval(String::from("ab")));
+	assert!(r.eval(String::from("aabb")));
+	assert!(!r.eval(String::from("abab")));
 }
+
+#[test]
+fn test_eval_asterisk_dfa() {
+	let r = Regexp::new(&String::from("a*b*")).determinize();
+	assert!(r.eval(String::from("a")));
+	assert!(r.eval(String::from("ab")));
+	assert!(r.eval(String::from("aabb")));
+	assert!(!r.eval(String::from("abab")));
+}
+
+#[test]
+fn test_eval_plus_nfa() {
+	let r = Regexp::new(&String::from("(ab)+"));
+	assert!(!r.eval(String::from("a")));
+	assert!(r.eval(String::from("ab")));
+	assert!(r.eval(String::from("abab")));
+	assert!(!r.eval(String::from("aabb")));
+}
+
+#[test]
+fn test_eval_plus_dfa() {
+	let r = Regexp::new(&String::from("(ab)+")).determinize();
+	assert!(!r.eval(String::from("a")));
+	assert!(r.eval(String::from("ab")));
+	assert!(r.eval(String::from("abab")));
+	assert!(!r.eval(String::from("aabb")));
+}