7 files changed, 397 insertions, 0 deletions
diff --git a/Homework/cs5000/hw05/.DS_Store b/Homework/cs5000/hw05/.DS_Store
new file mode 100644
index 0000000..9fc8419
--- /dev/null
+++ b/Homework/cs5000/hw05/.DS_Store
diff --git a/Homework/cs5000/hw05/CS5000_F23_HW05.pdf b/Homework/cs5000/hw05/CS5000_F23_HW05.pdf
new file mode 100644
index 0000000..aea985e
--- /dev/null
+++ b/Homework/cs5000/hw05/CS5000_F23_HW05.pdf
diff --git a/Homework/cs5000/hw05/PyCYK/__pycache__/cnfg.cpython-310.pyc b/Homework/cs5000/hw05/PyCYK/__pycache__/cnfg.cpython-310.pyc
new file mode 100644
index 0000000..6866f6c
--- /dev/null
+++ b/Homework/cs5000/hw05/PyCYK/__pycache__/cnfg.cpython-310.pyc
diff --git a/Homework/cs5000/hw05/PyCYK/__pycache__/cyk.cpython-310.pyc b/Homework/cs5000/hw05/PyCYK/__pycache__/cyk.cpython-310.pyc
new file mode 100644
index 0000000..d5fd992
--- /dev/null
+++ b/Homework/cs5000/hw05/PyCYK/__pycache__/cyk.cpython-310.pyc
diff --git a/Homework/cs5000/hw05/PyCYK/cnfg.py b/Homework/cs5000/hw05/PyCYK/cnfg.py
new file mode 100644
index 0000000..bb1ed17
--- /dev/null
+++ b/Homework/cs5000/hw05/PyCYK/cnfg.py
@@ -0,0 +1,82 @@
+###############################################
+# module: cnfg.py
+# description: Chomsky Normal Form Grammar
+# bugs to vladimir kulyukin in canvas
+###############################################
+
+class CNFG:
+    
+    def __init__(self, startSymbol = "S", productions = dict()):
+        self._productions = productions
+        self._startSymbol = startSymbol
+
+    def __str__(self):
+        productions = list()
+        for lhs in self._productions:
+            for rhs in self._productions[lhs]:
+                 productions.append(lhs + " -> " + str(rhs))
+        return "\n".join(productions)
+
+    def add_production(self, lhs, rhs1, rhs2 = None):
+        if lhs in self._productions:
+            rhs = self._productions.get(lhs)
+            rhs.append(CNFProductionRHS(rhs1, rhs2))
+        else:
+            rhs = list()
+            rhs.append(CNFProductionRHS(rhs1, rhs2))
+            self._productions[lhs] = rhs
+
+    def fetch_lhs(self, rhs1, rhs2 = None):
+        lhs_list = set()    
+        for lhs in self._productions:
+            for prod_rhs in self._productions[lhs]:
+                if rhs2 is None:
+                    if prod_rhs.is_rhs1() and prod_rhs.is_rhs1_equal(rhs1):
+                        lhs_list.add(lhs)                        
+                else:
+                    if prod_rhs.is_rhs2() and prod_rhs.is_rhs2_equal(rhs1, rhs2):
+                        lhs_list.add(lhs)
+            
+        return lhs_list
+
+    def clear_productions(self):
+        self._productions.clear()
+
+    def get_start_symbol(self):
+        return self._startSymbol
+        
+    def display(self):
+        print(str(self))
+
+
+class CNFProductionRHS:
+    def __init__(self, rhs1, rhs2 = None):
+        if rhs2 is None:
+            self._rhs_list = list(rhs1)
+        else:
+            self._rhs_list = list([rhs1, rhs2])
+
+    def __str__(self):
+        return "".join(self._rhs_list)
+
+    def is_rhs1(self):
+        return len(self._rhs_list) == 1
+
+    def is_rhs2(self):
+        return len(self._rhs_list) == 2
+
+    def is_rhs1_equal(self, rhs):
+        return self._rhs_list[0] == rhs
+
+    def is_rhs2_equal(self, rhs1, rhs2):
+        return self._rhs_list[0] == rhs1 and self._rhs_list[1] == rhs2
+
+    def get_productions(self):
+        if self.is_rhs1():
+            return self._rhs_list[0]
+        elif self.is_rhs2():
+            return self._rhs_list[0], self._rhs_list[1]
+        else:
+            return None
+
+
diff --git a/Homework/cs5000/hw05/PyCYK/cyk.py b/Homework/cs5000/hw05/PyCYK/cyk.py
new file mode 100644
index 0000000..e02e34a
--- /dev/null
+++ b/Homework/cs5000/hw05/PyCYK/cyk.py
@@ -0,0 +1,43 @@
+###############################################
+# module: cyk.py
+# Elizabeth Hunt
+# A02364151
+###############################################
+
+
+def format_table(derives: list[list[set]], max_row: int) -> str:
+    table = ""
+    n = len(derives)
+    for row in range(max_row):
+        curr_row = f"{row+1}: "
+        for col in range(n - row):
+            set_of_nonterminals = " ".join(derives[row][col])
+            curr_row += f"|{set_of_nonterminals}|"
+        table += curr_row + "\n"
+    return table
+
+
+class CYK(object):
+    @staticmethod
+    def is_in_cfl(test_string, cnfg, table_display_flag=False):
+        n = len(test_string)
+        derives = [[set() for _ in range(n)] for _ in range(n)]
+
+        for i, terminal in enumerate(test_string):
+            derives[0][i] |= cnfg.fetch_lhs(terminal)
+        if table_display_flag:
+            print(format_table(derives, 1))
+
+        for length in range(2, n + 1):
+            for start in range(n - length + 1):
+                for split_idx in range(1, length):
+                    for first in derives[split_idx - 1][start]:
+                        for second in derives[length - split_idx - 1][
+                            start + split_idx
+                        ]:
+                            derives[length - 1][start] |= cnfg.fetch_lhs(first, second)
+
+            if table_display_flag:
+                print(format_table(derives, length))
+
+        return "S" in derives[n - 1][0]
diff --git a/Homework/cs5000/hw05/PyCYK/cyktest.py b/Homework/cs5000/hw05/PyCYK/cyktest.py
new file mode 100644
index 0000000..0fa5e59
--- /dev/null
+++ b/Homework/cs5000/hw05/PyCYK/cyktest.py
@@ -0,0 +1,272 @@
+###############################################
+# module: cyktest.py
+# description: tests CYK in cyk.py
+# bugs to vladimir kulyukin via canvas
+###############################################
+
+import unittest
+import cyk
+from cyk import CYK
+from cnfg import CNFG
+
+class TestCykAlgorithm(unittest.TestCase):
+    _grammar = CNFG()
+    
+    def _use_grammar1(self):
+        ## 1. S -> AB
+        ## 2. S --> BC
+        ## 3. A --> BA
+        ## 4. A --> a
+        ## 5. B --> CC
+        ## 6. B --> b
+        ## 7. C --> AB
+        ## 8. C --> a
+        self._grammar.clear_productions()
+        self._grammar = CNFG()
+        self._grammar.add_production("S", "A", "B")
+        self._grammar.add_production("S", "B", "C")
+        self._grammar.add_production("A", "B", "A")
+        self._grammar.add_production("A", "a")
+        self._grammar.add_production("B", "C", "C")
+        self._grammar.add_production("B", "b")
+        self._grammar.add_production("C", "A", "B")
+        self._grammar.add_production("C", "a")
+
+    def _use_grammar2(self):
+        ## 1. S ->  AB
+        ## 2. S --> BB
+        ## 3. A --> CC
+        ## 4. A --> AB
+        ## 5. A --> a
+        ## 6. B --> BB
+        ## 7. B --> CA
+        ## 8. B --> b
+        ## 9. C --> BA
+        ## 10. C --> AA
+        ## 11. C --> b
+        self._grammar.clear_productions()        
+        self._grammar = CNFG();
+        self._grammar.add_production("S", "A", "B")
+        self._grammar.add_production("S", "B", "B")
+        self._grammar.add_production("A", "C", "C")
+        self._grammar.add_production("A", "A", "B")
+        self._grammar.add_production("A", "a")
+        self._grammar.add_production("B", "B", "B")
+        self._grammar.add_production("B", "C", "A")
+        self._grammar.add_production("B", "b")
+        self._grammar.add_production("C", "B", "A")
+        self._grammar.add_production("C", "A", "A")
+        self._grammar.add_production("C", "b")
+
+    def _use_grammar3(self):
+        ## 1. S ->  AD1
+        ## 2. D1 --> BC
+        ## 3. C --> BD2
+        ## 4. D2 --> AB
+        ## 5. C --> c
+        ## 6. B --> BB
+        ## 7. B --> b
+        ## 8. A --> a
+        self._grammar._productions.clear()
+        self._grammar = CNFG();
+        self._grammar.add_production("S", "A", "D1")
+        self._grammar.add_production("D1", "B", "C")
+        self._grammar.add_production("C", "B", "D2")
+        self._grammar.add_production("D2", "A", "B")
+        self._grammar.add_production("C", "c")
+        self._grammar.add_production("B", "B", "B")
+        self._grammar.add_production("B", "b")
+        self._grammar.add_production("A", "a")
+
+    def test_ut0(self):
+        print("===== Test 00 =====")        
+        grammar = CNFG()
+        grammar.clear_productions()
+        grammar.add_production("S", "A", "B")
+        grammar.add_production("S", "B", "C")
+        grammar.add_production("A", "B", "A")
+        grammar.add_production("A", "a")
+        grammar.add_production("B", "C", "C")
+        grammar.add_production("B", "b")
+        grammar.add_production("C", "A", "B")
+        grammar.add_production("C", "a")
+        print("LHS for RHS AB is {}".format(grammar.fetch_lhs("A", "B")))
+        
+    ### ===================== Grammar 1 Tests #############################
+    
+    def test1a(self):
+        print("===== Test 1a =====")
+        self._use_grammar1()
+        #self._grammar.display()
+        input_str = 'ab'
+        print('Input string: ' + input_str)
+        result = (CYK.is_in_cfl(input_str, self._grammar))
+        print('Result = ' + str(result))
+
+    def test1(self):
+        print("===== Test 1 =====")
+        self._use_grammar1()
+        self._grammar.display()
+        input_str = 'baaba'
+        print('Input string: ' + input_str)
+        result = (CYK.is_in_cfl(input_str, self._grammar))
+        print('Result = ' + str(result))
+        
+    def test2(self):
+        print("===== Test 2 =====")
+        self._use_grammar1()
+        #self._grammar.display()
+        input_str = 'baaa'
+        print('Input string: ' + input_str)
+        result = (CYK.is_in_cfl(input_str, self._grammar))
+        print('Result = ' + str(result))
+        
+    def test3(self):
+        print("===== Test 3 =====")
+        self._use_grammar1()
+        #self._grammar.display()
+        input_str = 'baba'
+        print('Input string: ' + input_str)
+        result = (CYK.is_in_cfl(input_str, self._grammar))
+        print('Result = ' + str(result))
+        
+    def test4(self):
+        print("===== Test 4 =====")
+        self._use_grammar1()
+        #self._grammar.display()
+        input_str = 'baaabab'
+        print('Input string: ' + input_str)
+        result = (CYK.is_in_cfl(input_str, self._grammar))
+        print('Result = ' + str(result))
+
+    def test4a(self):
+        print('===== Test 4a =====')
+        self._use_grammar1()
+        input_str = 'baab'
+        print('Input string: {}'.format(input_str))
+        result = (CYK.is_in_cfl(input_str, self._grammar, True))
+        print('Result = ' + str(result))
+
+    def test4b(self):
+        print('===== Test 4b =====')
+        self._use_grammar1()
+        input_str = 'aaab'
+        print('Input string: {}'.format(input_str))
+        result = (CYK.is_in_cfl(input_str, self._grammar, True))
+        print('Result = ' + str(result))
+
+    ### ===================== Grammar 2 Tests #############################
+    
+    def test5(self):
+        print("===== Test 5 =====")
+        self._use_grammar2()
+        #self._grammar.display()
+        input_str = 'aabb'
+        print('Input string: ' + input_str)
+        result = (CYK.is_in_cfl(input_str, self._grammar))
+        print('Result = ' + str(result))
+
+    def test5a(self):
+        print("===== Test 5a =====")
+        self._use_grammar2()
+        #self._grammar.display()
+        input_str = 'bbb'
+        print('Input string: ' + input_str)
+        result = (CYK.is_in_cfl(input_str, self._grammar))
+        print('Result = ' + str(result))
+
+    def test5b(self):
+        print("===== Test 5b =====")
+        self._use_grammar2()
+        #self._grammar.display()
+        input_str = 'bbb'
+        print('Input string: ' + input_str)
+        result = (CYK.is_in_cfl(input_str, self._grammar))
+        print('Result = ' + str(result))
+
+    def test5c(self):
+        print("===== Test 5c =====")
+        self._use_grammar2()
+        #self._grammar.display()
+        input_str = 'cccccb'
+        print('Input string: ' + input_str)
+        result = (CYK.is_in_cfl(input_str, self._grammar))
+        print('Result = ' + str(result))
+
+    def test5d(self):
+        print("===== Test 5d =====")
+        self._use_grammar2()
+        #self._grammar.display()
+        input_str = 'bababaaa'
+        print('Input string: ' + input_str)
+        result = (CYK.is_in_cfl(input_str, self._grammar))
+        print('Result = ' + str(result))
+        
+    ### ===================== Grammar 3 Tests #############################
+
+    def test6(self):
+        print("===== Test 6 =====")
+        self._use_grammar3()
+        input_str = 'abc'
+        print('Input string: ' + input_str)
+        result = (CYK.is_in_cfl(input_str, self._grammar))
+        print('Result = ' + str(result))
+
+    def test7(self):
+        print("===== Test 7 =====")
+        self._use_grammar3()
+        input_str = 'abbbabb'
+        print('Input string: ' + input_str)
+        result = (CYK.is_in_cfl(input_str, self._grammar))
+        print('Result = ' + str(result))
+
+    def test7b(self):
+        print("===== Test 7b =====")
+        self._use_grammar3()
+        input_str = 'abbc'
+        print('Input string: ' + input_str)
+        result = (CYK.is_in_cfl(input_str, self._grammar))
+        print('Result = ' + str(result))
+
+    def test8(self):
+        print("===== Test 8 =====")
+        self._use_grammar3()
+        input_str = 'bbc'
+        print('Input string: ' + input_str)
+        result = (CYK.is_in_cfl(input_str, self._grammar))
+        print('Result = ' + str(result))
+
+    def test9(self):
+        print("===== Test 9 =====")
+        self._use_grammar3()
+        input_str = 'aaabb'
+        print('Input string: ' + input_str)
+        result = (CYK.is_in_cfl(input_str, self._grammar))
+        print('Result = ' + str(result))
+
+    def test10(self):
+        print("===== Test 10 =====")
+        self._use_grammar3()
+        input_str = 'ab'
+        print('Input string: ' + input_str)
+        result = (CYK.is_in_cfl(input_str, self._grammar))
+        print('Result = ' + str(result))
+
+if __name__ == '__main__':
+    unittest.main()
+        
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+