-
Notifications
You must be signed in to change notification settings - Fork 0
/
regex_test.py
110 lines (81 loc) · 4.9 KB
/
regex_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
import unittest
from enfa import EPS
from regex import Regex
class RegexTest(unittest.TestCase):
def test_shunting_yard(self):
self.assertEqual(Regex("0").shunting_yard(), "0")
self.assertEqual(Regex("01").shunting_yard(), "01.")
self.assertEqual(Regex("0+1").shunting_yard(), "01+")
self.assertEqual(Regex("(0+1)*0+11").shunting_yard(), "01+*0.11.+")
self.assertEqual(Regex("0(0+1)*1").shunting_yard(), "001+*.1.")
self.assertEqual(Regex("(0)(1)").shunting_yard(), "01.")
def test_thomsons_construction_empty_regex(self):
enfa = Regex("").thomsons_construction("")
self.assertEqual(enfa.starting_state, "aa")
self.assertEqual(enfa.final_states, {"ab"})
expected_transition_function = {("aa", EPS): {"ab"}}
self.assertEqual(enfa.transition_function, expected_transition_function)
def test_thomsons_construction_single_symbol_regex(self):
enfa = Regex("").thomsons_construction("0")
self.assertEqual(enfa.starting_state, "aa")
self.assertEqual(enfa.final_states, {"ab"})
expected_transition_function = {("aa", "0"): {"ab"}}
self.assertEqual(enfa.transition_function, expected_transition_function)
def test_thomsons_construction_single_union_regex(self):
enfa = Regex("").thomsons_construction("01+")
self.assertEqual(enfa.starting_state, "ae")
self.assertEqual(enfa.final_states, {"af"})
self.assertEqual(len(enfa.transition_function), 5)
self.assertEqual(enfa.transition_function[("aa", "0")], {"ab"})
self.assertEqual(enfa.transition_function[("ac", "1")], {"ad"})
self.assertEqual(enfa.transition_function[("ae", EPS)], {"aa", "ac"})
self.assertEqual(enfa.transition_function[("ab", EPS)], {"af"})
self.assertEqual(enfa.transition_function[("ad", EPS)], {"af"})
def test_thomsons_construction_single_concatenation_regex(self):
enfa = Regex("").thomsons_construction("01.")
self.assertEqual(enfa.starting_state, "aa")
self.assertEqual(enfa.final_states, {"ad"})
self.assertEqual(len(enfa.transition_function), 2)
self.assertEqual(enfa.transition_function[("aa", "0")], {"ae"})
self.assertEqual(enfa.transition_function[("ae", "1")], {"ad"})
def test_thomsons_construction_single_kleene_star_regex(self):
enfa = Regex("").thomsons_construction("0*")
self.assertEqual(enfa.starting_state, "ac")
self.assertEqual(enfa.final_states, {"ad"})
self.assertEqual(len(enfa.transition_function), 3)
self.assertEqual(enfa.transition_function[("ac", EPS)], {"aa", "ad"})
self.assertEqual(enfa.transition_function[("aa", "0")], {"ab"})
self.assertEqual(enfa.transition_function[("ab", EPS)], {"aa", "ad"})
def test_thomsons_construction_double_concatenation_regex(self):
enfa = Regex("").thomsons_construction("01.0.")
self.assertEqual(enfa.starting_state, "aa")
self.assertEqual(enfa.final_states, {"ag"})
self.assertEqual(len(enfa.transition_function), 3)
self.assertEqual(enfa.transition_function[("aa", "0")], {"ae"})
self.assertEqual(enfa.transition_function[("ae", "1")], {"ah"})
self.assertEqual(enfa.transition_function[("ah", "0")], {"ag"})
def test_thomsons_construction_union_and_concatenation_regex(self):
enfa = Regex("").thomsons_construction("01+0.")
self.assertEqual(enfa.starting_state, "ae")
self.assertEqual(enfa.final_states, {"ah"})
self.assertEqual(len(enfa.transition_function), 6)
self.assertEqual(enfa.transition_function[("aa", "0")], {"ab"})
self.assertEqual(enfa.transition_function[("ac", "1")], {"ad"})
self.assertEqual(enfa.transition_function[("ae", EPS)], {"aa", "ac"})
self.assertEqual(enfa.transition_function[("ab", EPS)], {"ai"})
self.assertEqual(enfa.transition_function[("ad", EPS)], {"ai"})
self.assertEqual(enfa.transition_function[("ai", "0")], {"ah"})
def test_thomsons_construction_1(self):
enfa = Regex("").thomsons_construction("001+*.1.")
self.assertEqual(enfa.starting_state, "aa")
self.assertEqual(enfa.final_states, {"am"})
self.assertEqual(len(enfa.transition_function), 9)
self.assertEqual(enfa.transition_function[("aa", "0")], {"ak"})
self.assertEqual(enfa.transition_function[("ah", "ε")], {"ag", "an"})
self.assertEqual(enfa.transition_function[("ag", "ε")], {"ae", "ac"})
self.assertEqual(enfa.transition_function[("ad", "ε")], {"ah"})
self.assertEqual(enfa.transition_function[("af", "ε")], {"ah"})
self.assertEqual(enfa.transition_function[("ac", "0")], {"ad"})
self.assertEqual(enfa.transition_function[("ae", "1")], {"af"})
self.assertEqual(enfa.transition_function[("ak", "ε")], {"ag", "an"})
self.assertEqual(enfa.transition_function[("an", "1")], {"am"})