1 files changed, 43 insertions, 0 deletions
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]