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/.DS_Store | Bin 0 -> 6148 bytes Homework/cs5000/hw05/CS5000_F23_HW05.pdf | Bin 0 -> 99041 bytes .../hw05/PyCYK/__pycache__/cnfg.cpython-310.pyc | Bin 0 -> 2989 bytes .../hw05/PyCYK/__pycache__/cyk.cpython-310.pyc | Bin 0 -> 1580 bytes Homework/cs5000/hw05/PyCYK/cnfg.py | 82 +++++++ Homework/cs5000/hw05/PyCYK/cyk.py | 43 ++++ Homework/cs5000/hw05/PyCYK/cyktest.py | 272 +++++++++++++++++++++ 7 files changed, 397 insertions(+) create mode 100644 Homework/cs5000/hw05/.DS_Store create mode 100644 Homework/cs5000/hw05/CS5000_F23_HW05.pdf create mode 100644 Homework/cs5000/hw05/PyCYK/__pycache__/cnfg.cpython-310.pyc create mode 100644 Homework/cs5000/hw05/PyCYK/__pycache__/cyk.cpython-310.pyc create mode 100644 Homework/cs5000/hw05/PyCYK/cnfg.py create mode 100644 Homework/cs5000/hw05/PyCYK/cyk.py create mode 100644 Homework/cs5000/hw05/PyCYK/cyktest.py (limited to 'Homework/cs5000/hw05') diff --git a/Homework/cs5000/hw05/.DS_Store b/Homework/cs5000/hw05/.DS_Store new file mode 100644 index 0000000..9fc8419 Binary files /dev/null and b/Homework/cs5000/hw05/.DS_Store differ 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 Binary files /dev/null and b/Homework/cs5000/hw05/CS5000_F23_HW05.pdf differ 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 Binary files /dev/null and b/Homework/cs5000/hw05/PyCYK/__pycache__/cnfg.cpython-310.pyc differ 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 Binary files /dev/null and b/Homework/cs5000/hw05/PyCYK/__pycache__/cyk.cpython-310.pyc differ 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() + + + + + + + + + + + + + + + + -- cgit v1.3