1 files changed, 110 insertions, 0 deletions
diff --git a/Homework/cs5000/hw03/hw03/cs5000_f23_hw03.py b/Homework/cs5000/hw03/hw03/cs5000_f23_hw03.py
new file mode 100644
index 0000000..f32a7c1
--- /dev/null
+++ b/Homework/cs5000/hw03/hw03/cs5000_f23_hw03.py
@@ -0,0 +1,110 @@
+###############################################
+# cs5000_f23_hw03.py
+# Elizabeth Hunt
+# A02364151
+###############################################
+import functools
+from collections.abc import Iterable
+
+
+def power_set(s: list) -> list[list]:
+    if len(s) == 0:
+        return [[]]
+
+    head, tail = [s[0], s[1:]]
+    tail_set = power_set(tail)
+
+    res = []
+    for i in tail_set:
+        res.append(i + [head])
+        res.append(i)
+
+    return res
+
+
+def deterministic_states_key(s: Iterable[str]) -> str:
+    return "".join(sorted(s))
+
+
+def reachable(
+    begin: str,
+    states: set[str],
+    alphabet: set[str],
+    delta: dict[tuple[str, str], set[str]],
+) -> set[str]:
+    visited = set()
+
+    def dfs(state: str):
+        visited.add(state)
+
+        for a in alphabet:
+            transition = (state, a)
+            if transition in delta and delta[transition] not in visited:
+                new_state = delta[transition]
+                dfs(new_state)
+
+    dfs(begin)
+    return visited
+
+
+def nfa_to_dfa(
+    nfa: tuple[set[str], set[str], dict[tuple[str, str], set[str]], set[str]]
+) -> tuple[set[str], set[str], dict[tuple[str, str], set[str]], set[str]]:
+    (states, alphabet, delta, start, accepting) = nfa
+
+    p_states = power_set(list(states))
+    p_inv = dict((deterministic_states_key(s), str(i)) for i, s in enumerate(p_states))
+    start_d = next(
+        str(i) for i, s in enumerate(p_states) if len(s) == 1 and s[0] == start
+    )
+    f_d = set()
+    delta_d = {}
+
+    for i, q in enumerate(p_states):
+        for a in alphabet:
+            nfa_to_states = functools.reduce(
+                lambda acc, x: acc.union(delta[(x, a)] if (x, a) in delta else set()),
+                q,
+                set(),
+            )
+            key = deterministic_states_key(nfa_to_states)
+
+            if key in p_inv:
+                delta_d[(str(i), a)] = p_inv[key]
+
+    for i, q in enumerate(p_states):
+        if len(set(q).intersection(accepting)) > 0:
+            f_d.add(str(i))
+
+    reachable_states = reachable(start_d, list(range(len(p_states))), alphabet, delta_d)
+    pruned_delta_d = dict(
+        list(
+            filter(
+                lambda x: x[0][0] in reachable_states and x[1] in reachable_states,
+                delta_d.items(),
+            )
+        )
+    )
+
+    return (
+        reachable_states,
+        alphabet,
+        pruned_delta_d,
+        start_d,
+        f_d.intersection(reachable_states),
+    )
+
+
+def display_dfa(
+    dfa: tuple[set[str], set[str], dict[tuple[str, str], set[str]], set[str]]
+):
+    (states, alphabet, delta, start, accepting) = dfa
+
+    print(f"STATES: {states}")
+    print(f"SIGMA: {alphabet}")
+    print(f"START STATE: {start}")
+    print("DELTA:")
+    for i, entry in enumerate(delta.items()):
+        (key, value) = entry
+        print(f"{i}) d({key}) = {value}")
+    print(f"FINAL STATES: {accepting}")