diff options
| author | Elizabeth Alexander Hunt <me@liz.coffee> | 2026-07-02 11:55:17 -0700 |
|---|---|---|
| committer | Elizabeth Alexander Hunt <me@liz.coffee> | 2026-07-02 11:55:17 -0700 |
| commit | 6bf4b90c90f15f4ab60833bddf5b5756d1a6b1f6 (patch) | |
| tree | ed97e39ec77c5231ffd2c394493e68d00ddac5a4 /Homework/cs5000/hw05/PyCYK/cyk.py | |
| download | misc-undergrad-main.tar.gz misc-undergrad-main.zip | |
Diffstat (limited to 'Homework/cs5000/hw05/PyCYK/cyk.py')
| -rw-r--r-- | Homework/cs5000/hw05/PyCYK/cyk.py | 43 |
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]
|