5 files changed, 154 insertions, 1 deletions
diff --git a/.gitignore b/.gitignore
index ea8c4bf..ea8c4bf 100644..100755
--- a/.gitignore
+++ b/.gitignore
diff --git a/Cargo.lock b/Cargo.lock
index 892020a..892020a 100644..100755
--- a/Cargo.lock
+++ b/Cargo.lock
diff --git a/Cargo.toml b/Cargo.toml
index 88c69da..88c69da 100644..100755
--- a/Cargo.toml
+++ b/Cargo.toml
diff --git a/README.md b/README.md
index 0e2e49a..0e2e49a 100644..100755
--- a/README.md
+++ b/README.md
diff --git a/src/main.rs b/src/main.rs
index e7a11a9..cfcfcbf 100644..100755
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,3 +1,156 @@
+#![allow(dead_code, unused_variables, unused_mut)]
+
+#[derive(Debug)]
+struct State {
+    transitions: Vec<(Trans, usize)>, // (input symbol, destination state index)
+}
+
+#[derive(Debug)]
+struct NFA {
+    graph: Vec<State>,
+    initial_state: usize,
+    accepting_states: Vec<usize>,
+}
+
+impl NFA {
+    fn new(graph: Vec<State>, initial_state: usize, accepting_states: Vec<usize>) -> Self {
+        NFA {
+            graph,
+            initial_state,
+            accepting_states,
+        }
+    }
+
+    fn simulate(&self, input: &str) -> bool {
+        let mut current_states = vec![self.initial_state];
+
+        for c in input.chars() {
+            let mut next_states = vec![];
+
+            for state in &current_states {
+                for (trans, dest_state) in &self.graph[*state].transitions {
+                    // println!("char: {c}, trans: {trans:?}, dest_state: {dest_state:?}");
+                    match trans {
+                        Trans::Symbol(symbol) if *symbol == c => {
+                            next_states.push(*dest_state);
+                        }
+                        Trans::Epsilon => {
+                            next_states.push(*dest_state);
+                        }
+                        _ => {}
+                    }
+                }
+            }
+
+            current_states = next_states;
+        }
+
+        // println!("states: {:?}", current_states);
+
+        current_states
+            .iter()
+            .any(|&state| self.accepting_states.contains(&state))
+    }
+}
+
+#[derive(PartialEq, Clone, Debug)]
+enum Trans {
+    Symbol(char),
+    Epsilon,
+}
+
+struct Regex {
+    regex: &'static str,
+}
+
+impl Regex {
+    fn new(input: &'static str) -> Self {
+        Regex { regex: input }
+    }
+
+    fn compile_nfa(&self) -> NFA {
+        let mut graph: Vec<State> = vec![State {
+            transitions: vec![],
+        }];
+        let initial_state = 0;
+        let mut accepting_states = vec![];
+
+        let mut current_state = initial_state;
+        let mut prev_state: Option<usize> = None;
+
+        let input: Vec<char> = self.regex.chars().collect();
+
+        for (i, &c) in input.iter().enumerate() {
+            match c {
+                '*' => {}
+                '+' => todo!(),
+                '.' => {
+                    let next_state = graph.len();
+                    println!("{next_state}");
+                    graph.push(State {
+                        transitions: vec![],
+                    });
+
+                    graph[next_state]
+                        .transitions
+                        .push((Trans::Epsilon, next_state));
+
+                    current_state = next_state;
+                }
+                '|' => {
+                    let before = input[i - 1];
+                    let after = input[i + 1];
+                    let next_state = graph.len();
+                    graph.push(State {
+                        transitions: vec![],
+                    });
+                    graph[current_state]
+                        .transitions
+                        .push((Trans::Symbol(c), next_state));
+
+                    current_state = next_state;
+                }
+                _ => {
+                    // let after = input[i + 1];
+                    // if after != '|' {
+                    let next_state = graph.len();
+                    graph.push(State {
+                        transitions: vec![],
+                    });
+                    graph.push(State {
+                        transitions: vec![],
+                    });
+
+                    graph[current_state]
+                        .transitions
+                        .push((Trans::Symbol(c), next_state + 1));
+                    graph[next_state]
+                        .transitions
+                        .push((Trans::Epsilon, next_state + 1));
+
+                    current_state = next_state + 1;
+                    // }
+                }
+            }
+        }
+
+        accepting_states.push(current_state);
+
+        NFA::new(graph, initial_state, accepting_states)
+    }
+}
+
 fn main() {
-    println!("Hello, world!");
+    let regex = Regex::new("a.bc");
+    let nfa = regex.compile_nfa();
+
+    println!("NFA: {:#?}", nfa);
+
+    let input = vec!["a", "abcc", "abc", "abbc", "abbbc", "abbbbc", "ac", "ab"];
+
+    println!("Regex: {:#?}", regex.regex);
+
+    for inp in input {
+        println!("{} -> {:?}", inp, nfa.simulate(inp)); // Should match
+    }
 }