InitHEADmain

9 files changed, 292 insertions, 0 deletions

diff --git a/Homework/cs5000/hw03/CS5000_F23_hw03.org b/Homework/cs5000/hw03/CS5000_F23_hw03.org
new file mode 100644
index 0000000..a0f08de
--- /dev/null
+++ b/Homework/cs5000/hw03/CS5000_F23_hw03.org
@@ -0,0 +1,43 @@
+#+TITLE: HW 02
+#+AUTHOR: Elizabeth Hunt
+#+STARTUP: entitiespretty fold inlineimages
+#+LATEX_HEADER: \notindent \notag  \usepackage{amsmath} \usepackage[a4paper,margin=1in,portrait]{geometry}
+#+LATEX: \setlength\parindent{0pt}
+#+OPTIONS: toc:nil
+
+* Question One
+** Partition Refinement
+{ {q_0, q_1, q_3}, {q_2, q_4} }
+
+S_1 = {(q_0, q_1), (q_0, q_3), (q_1, q_3)}
+S_2 = {(q_2, q_4)}
+
+\delta(q_0, 1) = q_3 \in S_1
+\delta(q_1, 1) = q_4 \in S_2
+
+(q_0, q_1) need to be split
+
+\delta(q_0, 0) = q_1 \in S_1
+\delta(q_3, 0) = q_2 \in S_2
+
+(q_1, q_2) need to be split
+
+\forall x \in \Sigma, \delta(q_1, x) = \delta(q_3, x)
+so {q_1, q_3} does not need to be split
+
+In S_2, \delta(q_2, 0) \in S_1 and \delta(q_4, 0) \in S_2, thus need to be split
+
+Finally, the refined partitions are {{q_0}, {q_1, q_3}, {q_2}, {q_4}}
+
+** Minimization
+| a \in \Sigma | {q_0}     | {q_1, q_3} | {q_2}     | {q_4} |
+|     0 | {q_1, q_3} | {q_2}     | {q_1, q_3} | {q_4} |
+|     1 | {q_1, q_3} | {q_4}     | {q_4}     | {q_4} |
+
+with d_0 = {q_0}, d_1 = {q_1, q_3}, d_2 = {q_2} and d_3 = {q_4}
+
+#+attr_latex: :width 350px
+[[./img/min_dfa.png]]
+
+* Question Two
+See attached python
diff --git a/Homework/cs5000/hw03/CS5000_F23_hw03.tex b/Homework/cs5000/hw03/CS5000_F23_hw03.tex
new file mode 100644
index 0000000..634470a
--- /dev/null
+++ b/Homework/cs5000/hw03/CS5000_F23_hw03.tex
@@ -0,0 +1,76 @@
+% Created 2023-09-20 Wed 15:58
+% Intended LaTeX compiler: pdflatex
+\documentclass[11pt]{article}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage{graphicx}
+\usepackage{longtable}
+\usepackage{wrapfig}
+\usepackage{rotating}
+\usepackage[normalem]{ulem}
+\usepackage{amsmath}
+\usepackage{amssymb}
+\usepackage{capt-of}
+\usepackage{hyperref}
+\notindent \notag  \usepackage{amsmath} \usepackage[a4paper,margin=1in,portrait]{geometry}
+\author{Elizabeth Hunt}
+\date{\today}
+\title{HW 02}
+\hypersetup{
+ pdfauthor={Elizabeth Hunt},
+ pdftitle={HW 02},
+ pdfkeywords={},
+ pdfsubject={},
+ pdfcreator={Emacs 28.2 (Org mode 9.7-pre)}, 
+ pdflang={English}}
+\begin{document}
+
+\maketitle
+\setlength\parindent{0pt}
+
+\section{Question One}
+\label{sec:org859695d}
+\subsection{Partition Refinement}
+\label{sec:org55dda6e}
+\{ \{q\textsubscript{0}, q\textsubscript{1}, q\textsubscript{3}\}, \{q\textsubscript{2}, q\textsubscript{4}\} \}
+
+S\textsubscript{1} = \{(q\textsubscript{0}, q\textsubscript{1}), (q\textsubscript{0}, q\textsubscript{3}), (q\textsubscript{1}, q\textsubscript{3})\}
+S\textsubscript{2} = \{(q\textsubscript{2}, q\textsubscript{4})\}
+
+\(\delta\)(q\textsubscript{0}, 1) = q\textsubscript{3} \(\in\) S\textsubscript{1}
+\(\delta\)(q\textsubscript{1}, 1) = q\textsubscript{4} \(\in\) S\textsubscript{2}
+
+(q\textsubscript{0}, q\textsubscript{1}) need to be split
+
+\(\delta\)(q\textsubscript{0}, 0) = q\textsubscript{1} \(\in\) S\textsubscript{1}
+\(\delta\)(q\textsubscript{3}, 0) = q\textsubscript{2} \(\in\) S\textsubscript{2}
+
+(q\textsubscript{1}, q\textsubscript{2}) need to be split
+
+\(\forall\) x \(\in\) \(\Sigma\), \(\delta\)(q\textsubscript{1}, x) = \(\delta\)(q\textsubscript{3}, x)
+so \{q\textsubscript{1}, q\textsubscript{3}\} does not need to be split
+
+In S\textsubscript{2}, \(\delta\)(q\textsubscript{2}, 0) \(\in\) S\textsubscript{1} and \(\delta\)(q\textsubscript{4}, 0) \(\in\) S\textsubscript{2}, thus need to be split
+
+Finally, the refined partitions are \{\{q\textsubscript{0}\}, \{q\textsubscript{1}, q\textsubscript{3}\}, \{q\textsubscript{2}\}, \{q\textsubscript{4}\}\}
+
+\subsection{Minimization}
+\label{sec:org870d4d3}
+\begin{center}
+\begin{tabular}{rllll}
+a \(\in\) \(\Sigma\) & \{q\textsubscript{0}\} & \{q\textsubscript{1}, q\textsubscript{3}\} & \{q\textsubscript{2}\} & \{q\textsubscript{4}\}\\[0pt]
+0 & \{q\textsubscript{1}, q\textsubscript{3}\} & \{q\textsubscript{2}\} & \{q\textsubscript{1}, q\textsubscript{3}\} & \{q\textsubscript{4}\}\\[0pt]
+1 & \{q\textsubscript{1}, q\textsubscript{3}\} & \{q\textsubscript{4}\} & \{q\textsubscript{4}\} & \{q\textsubscript{4}\}\\[0pt]
+\end{tabular}
+\end{center}
+
+with d\textsubscript{0} = \{q\textsubscript{0}\}, d\textsubscript{1} = \{q\textsubscript{1}, q\textsubscript{3}\}, d\textsubscript{2} = \{q\textsubscript{2}\} and d\textsubscript{3} = \{q\textsubscript{4}\}
+
+\begin{center}
+\includegraphics[width=350px]{./img/min_dfa.png}
+\end{center}
+
+\section{Question Two}
+\label{sec:orga1d2018}
+See attached python
+\end{document}
\ No newline at end of file
diff --git a/Homework/cs5000/hw03/__pycache__/cs5000_f23_hw03.cpython-311.pyc b/Homework/cs5000/hw03/__pycache__/cs5000_f23_hw03.cpython-311.pyc
new file mode 100644
index 0000000..f3444a4
--- /dev/null
+++ b/Homework/cs5000/hw03/__pycache__/cs5000_f23_hw03.cpython-311.pyc
diff --git a/Homework/cs5000/hw03/hw03.zip b/Homework/cs5000/hw03/hw03.zip
new file mode 100644
index 0000000..1092d16
--- /dev/null
+++ b/Homework/cs5000/hw03/hw03.zip
diff --git a/Homework/cs5000/hw03/hw03/CS5000_F23_hw03.pdf b/Homework/cs5000/hw03/hw03/CS5000_F23_hw03.pdf
new file mode 100644
index 0000000..cb3a987
--- /dev/null
+++ b/Homework/cs5000/hw03/hw03/CS5000_F23_hw03.pdf
diff --git a/Homework/cs5000/hw03/hw03/__pycache__/cs5000_f23_hw03.cpython-311.pyc b/Homework/cs5000/hw03/hw03/__pycache__/cs5000_f23_hw03.cpython-311.pyc
new file mode 100644
index 0000000..d005ebc
--- /dev/null
+++ b/Homework/cs5000/hw03/hw03/__pycache__/cs5000_f23_hw03.cpython-311.pyc
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}")
diff --git a/Homework/cs5000/hw03/hw03/cs5000_f23_hw03_uts.py b/Homework/cs5000/hw03/hw03/cs5000_f23_hw03_uts.py
new file mode 100644
index 0000000..173d3cf
--- /dev/null
+++ b/Homework/cs5000/hw03/hw03/cs5000_f23_hw03_uts.py
@@ -0,0 +1,63 @@
+####################################################
+# CS5000: F23: Assignment 3: Unit Tests
+# Description: Two unit tests for the subset construction
+#              algorithm.
+# bugs to vladimir kulyukin in canvas
+#####################################################
+
+from cs5000_f23_hw03 import nfa_to_dfa, display_dfa
+import unittest
+
+class CS5000F23Assign03UnitTests(unittest.TestCase):
+
+    def test_assgn_03_ut_01(self):
+        print('\n***** Assign 03: Subset Construction UT 01 *****')
+        NFA_DELTA_01 = {}
+        NFA_DELTA_01[('q0', '0')] = set(['q0'])
+        NFA_DELTA_01[('q0', '1')] = set(['q0', 'q1'])
+        NFA_DELTA_01[('q1', '0')] = set(['q2'])
+        NFA_DELTA_01[('q1', '1')] = set(['q2'])
+        NFA_01 = (set(['q0','q1', 'q2']),
+                  set(['0', '1']),
+                  NFA_DELTA_01,
+                  'q0',
+                  set(['q2']))
+
+        dfa_01 = nfa_to_dfa(NFA_01)
+        display_dfa(dfa_01)
+
+    def test_assgn_03_ut_02(self):
+        print('\n***** Assign 03: Subset Construction UT 02 *****')
+        NFA_DELTA_02 = {}
+        NFA_DELTA_02[('q0', '0')] = set(['q0', 'q1'])
+        NFA_DELTA_02[('q0', '1')] = set(['q1'])
+        NFA_DELTA_02[('q1', '0')] = set(['q2'])
+        NFA_DELTA_02[('q1', '1')] = set(['q2'])
+        NFA_DELTA_02[('q2', '0')] = set(['q2'])
+        NFA_DELTA_02[('q2', '1')] = set(['q2'])        
+        NFA_02 = (set(['q0', 'q1', 'q2']),
+                  set(['0', '1']),
+                  NFA_DELTA_02,
+                  'q0',
+                  set(['q1']))
+        dfa_02 = nfa_to_dfa(NFA_02)
+        display_dfa(dfa_02)
+    
+### ================ Unit Tests ====================
+
+if __name__ == '__main__':
+    unittest.main()
+
+
+ 
+    
+        
+        
+
+    
+        
+
+
+
+
+
diff --git a/Homework/cs5000/hw03/img/min_dfa.png b/Homework/cs5000/hw03/img/min_dfa.png
new file mode 100644
index 0000000..3d4d529
--- /dev/null
+++ b/Homework/cs5000/hw03/img/min_dfa.png