From 6bf4b90c90f15f4ab60833bddf5b5756d1a6b1f6 Mon Sep 17 00:00:00 2001 From: Elizabeth Alexander Hunt Date: Thu, 2 Jul 2026 11:55:17 -0700 Subject: Init --- Homework/cs5000/hw05/PyCYK/cyk.py | 43 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 43 insertions(+) create mode 100644 Homework/cs5000/hw05/PyCYK/cyk.py (limited to 'Homework/cs5000/hw05/PyCYK/cyk.py') 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] -- cgit v1.3