-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathTMToTOne.py
112 lines (101 loc) · 5.14 KB
/
TMToTOne.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
import sys
from collections import defaultdict
# Turing machine configuration
try:
TM = open('TuringMachine.txt', 'r')
delta_function = []
start_state = 'start'
final_states = {'final'}
# need statesWithoutFinal without final one
statesWithoutFinal = set()
for line in TM:
statesWithoutFinal.add(line.split(',')[0])
delta_function.append(line[:-1].split(','))
sigma_alphabet = ['0', '1']
gamma_alphabet = sigma_alphabet + ['000', '001', '010', '011', '100', '101', '110', '111'] + \
['000#', '001#', '010#', '011#', '100#', '101#', '110#', '111#']
eps = 'e'
except IOError:
print('Couldn\'t read file with Turing machine')
sys.exit(1)
res_grammar = defaultdict(list)
# 1 group
for terminal in sigma_alphabet:
res_grammar["A1"] += ['[$ ' + start_state + ' ' + terminal + ' ' + terminal + ' @]']
for q, A, p, B, d in filter(lambda x: x[0] in statesWithoutFinal, delta_function):
for a in sigma_alphabet:
if A == '$' and d == 'r':
for X in gamma_alphabet:
# 2.1
res_grammar['[' + q + ' $ ' + X + ' ' + a + ' @]'] += ['[$ ' + p + ' ' + X + ' ' + a + ' @]']
# 5.1
res_grammar['[' + q + ' $ ' + X + ' ' + a + ']'] += ['[$ ' + p + ' ' + X + ' ' + a + ']']
else:
if A == '@' and d == 'l':
for X in gamma_alphabet:
# 2.4
res_grammar['[$ ' + X + ' ' + a + ' ' + q + ' @]'] += ['[$ ' + p + ' ' + X + ' ' + a + ' @]']
# 7.2
res_grammar['[' + X + ' ' + a + ' ' + q + ' @]'] += ['[' + p + ' ' + X + ' ' + a + ' @]']
else:
# X == A and Y == B
if d == 'l':
# 2.2
res_grammar['[$ ' + q + ' ' + A + ' ' + a + ' @]'] += ['[' + p + ' $ ' + B + ' ' + a + ' @]']
# 5.2
res_grammar['[$ ' + q + ' ' + A + ' ' + a + ']'] += ['[' + p + ' $ ' + B + ' ' + a + ']']
for Z in gamma_alphabet:
for b in sigma_alphabet:
# 6.2
res_grammar['[' + Z + ' ' + b + '][' + q + ' ' + A + ' ' + a + ']'] += \
['[' + p + ' ' + Z + ' ' + b + '][' + B + ' ' + a + ']']
# 6.4
res_grammar['[$ ' + Z + ' ' + b + '][' + q + ' ' + A + ' ' + a + ']'] += \
['[$ ' + p + ' ' + Z + ' ' + b + '][' + B + ' ' + a + ']']
# 7.3
res_grammar['[' + Z + ' ' + b + '][' + q + ' ' + A + ' ' + a + ' @]'] += \
['[' + p + ' ' + Z + ' ' + b + '][' + B + ' ' + a + ' @]']
else:
# 2.3
res_grammar['[$ ' + q + ' ' + A + ' ' + a + ' @]'] += ['[$ ' + B + ' ' + a + ' ' + p + ' @]']
for Z in gamma_alphabet:
for b in sigma_alphabet:
# 5.3
res_grammar['[$ ' + q + ' ' + A + ' ' + a + '][' + Z + ' ' + b + ']'] += \
['[$ ' + B + ' ' + a + '][' + p + ' ' + Z + ' ' + b + ']']
# 6.1
res_grammar['[' + q + ' ' + A + ' ' + a + '][' + Z + ' ' + b + ']'] += \
['[' + B + ' ' + a + '][' + p + ' ' + Z + ' ' + b + ']']
# 6.3
res_grammar['[' + q + ' ' + A + ' ' + a + '][' + Z + ' ' + b + ' @]'] += \
['[' + B + ' ' + a + '][' + p + ' ' + Z + ' ' + b + ' @]']
# 7.1
res_grammar['[' + q + ' ' + A + ' ' + a + ' @]'] += ['[' + B + ' ' + a + ' ' + p + ' @]']
for q in final_states:
for X in gamma_alphabet:
for a in sigma_alphabet:
# 3
res_grammar['[' + q + ' $ ' + X + ' ' + a + ' @]'] += [a]
res_grammar['[$ ' + q + ' ' + X + ' ' + a + ' @]'] += [a]
res_grammar['[$ ' + X + ' ' + a + ' ' + q + ' @]'] += [a]
# 8
res_grammar['[' + q + ' $ ' + X + ' ' + a + ']'] += [a]
res_grammar['[$ ' + q + ' ' + X + ' ' + a + ']'] += [a]
res_grammar['[' + q + ' ' + X + ' ' + a + ']'] = [a]
res_grammar['[' + q + ' ' + X + ' ' + a + ' @]'] += [a]
res_grammar['[' + X + ' ' + a + ' ' + q + ' @]'] += [a]
# 9
for b in sigma_alphabet:
res_grammar[a + '[' + X + ' ' + b + ']'] += [a + b]
res_grammar[a + '[' + X + ' ' + b + ' @]'] += [a + b]
res_grammar['[' + X + ' ' + a + ']'+ b] += [a + b]
res_grammar['[$ ' + X + ' ' + a + ']' + b] += [a + b]
# 4
for a in sigma_alphabet:
res_grammar['[A1]'] += ['[$ ' + start_state + ' ' + a + ' ' + a + '][A2]']
res_grammar['[A2]'] += ['[' + a + ' ' + a + '][A2]']
res_grammar['[A2]'] += ['[' + a + ' ' + a + ' @]']
with open('grammarTypeOne.txt', 'w') as f:
for k, v in res_grammar.items():
for right in v:
f.write(k + ' -> ' + right + '\n')