-
Notifications
You must be signed in to change notification settings - Fork 0
/
q3.py
120 lines (101 loc) · 4.09 KB
/
q3.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
111
112
113
114
115
116
117
118
119
120
from copy import deepcopy
import sys
import json
def objectFA(s,l,tm,ss,fs):
return {
'states': s,
'letters': l,
'transition_matrix': tm,
'start_states': ss,
'final_states':fs
}
def makeGNFA(DFA):
deltaFunction = {}
new_start_state = 'START'
new_final_state = 'FINAL'
deltaFunction[new_start_state] = {}
deltaFunction[new_final_state] = {}
deltaFunction[new_start_state][new_final_state] = None
for st in DFA['states']:
deltaFunction[st] = {}
for st1 in DFA['states']:
deltaFunction[st][st1] = None
deltaFunction[new_start_state][st] = None if (st not in DFA['start_states']) else '$'
deltaFunction[st][new_final_state] = None if (st not in DFA['final_states']) else '$'
for arc in DFA['transition_matrix']:
[ss, l, fs] = arc
deltaFunction[ss][fs] = l if (deltaFunction[ss][fs]==None) else deltaFunction[ss][fs] + "+" + str(l)
return new_start_state, new_final_state, deltaFunction
def getParentChildren(ripState, deltaFunction):
parent = []
children = []
for childKey in deltaFunction[ripState]:
label = deltaFunction[ripState][childKey]
if (label==None) or (childKey==ripState):
continue
children.append(childKey)
for stateKey in deltaFunction:
if stateKey != ripState:
childrenDict = deltaFunction[stateKey]
if ripState not in childrenDict:
continue
elif childrenDict[ripState]==None:
continue
else:
parent.append(stateKey)
return parent, children
def updateArc(delPR, delRR, delRC, delPC):
R1 = '' if (delPR==None) else '('+str(delPR)+')'
R2 = '' if (delRR==None) else '('+str(delRR)+')*'
R3 = '' if (delRC==None) else '('+str(delRC)+')'
R4 = '' if (delPC==None) else '+('+str(delPC)+')'
return R1+R2+R3+R4
def updateStateTransition(deltaFunction, parents, children, ripState):
updatedDeltaFunction = deepcopy(deltaFunction)
for child in children:
for parent in parents:
delPR = deltaFunction[parent][ripState]
delRR = deltaFunction[ripState][ripState]
delRC = deltaFunction[ripState][child]
delPC = deltaFunction[parent][child]
updatedDeltaFunction[parent][child] = updateArc(delPR, delRR, delRC, delPC)
return updatedDeltaFunction
def eliminateState(ripState, updatedDeltaFunction):
retDeltaFunction = {}
for stateKey in updatedDeltaFunction:
if stateKey != ripState:
retDeltaFunction[stateKey] = {}
for child in updatedDeltaFunction[stateKey]:
if child != ripState:
val = updatedDeltaFunction[stateKey][child]
retDeltaFunction[stateKey][child] = val
return retDeltaFunction
def stateElimination(new_start_state, new_final_state, deltaFunction, dfaStates):
for ripState in dfaStates:
parents, children = getParentChildren(ripState, deltaFunction)
updatedDeltaFunction = updateStateTransition(deltaFunction, parents, children, ripState)
deltaFunction = eliminateState(ripState, updatedDeltaFunction)
return deltaFunction[new_start_state][new_final_state]
def convertDFAToRegex(DFA):
new_start_state, new_final_state, deltaFunction = makeGNFA(DFA)
finalRegex = stateElimination(new_start_state, new_final_state, deltaFunction, DFA['states'])
return finalRegex
if __name__=="__main__":
if len(sys.argv) != 3:
print("Unexceptable Format!")
quit()
try:
input_file = open(sys.argv[1])
rawDFA = json.load(input_file)
s = rawDFA['states']
l = rawDFA['letters']
tm = rawDFA['transition_function']
ss = rawDFA['start_states']
fs = rawDFA['final_states']
myDFA = objectFA(s, l, tm, ss, fs)
except:
print("Error accessing `input_file`")
quit()
finalRegex = convertDFAToRegex(myDFA)
with open(sys.argv[2], "w+") as outfile:
json.dump({'regex': finalRegex}, outfile, indent=4)