Skip to content

Commit c614d8c

Browse files
author
codehouseindia
authored
Merge pull request codehouseindia#336 from arryan231/patch-1
Added NFA to DFA Program
2 parents 98d95ec + 2c638ee commit c614d8c

1 file changed

Lines changed: 148 additions & 0 deletions

File tree

‎dfa_nfa.py‎

Lines changed: 148 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,148 @@
1+
#https://www.facebook.com/arryan.sinha/posts/3315806428532978
2+
#Subscribed By Code House
3+
4+
import pandas as pd
5+
6+
# Taking NFA input from User
7+
8+
nfa = {}
9+
n = int(input("No. of states : "))
10+
t = int(input("No. of transitions : "))
11+
for i in range(n):
12+
state = input("state name : ")
13+
nfa[state] = {}
14+
for j in range(t):
15+
path = input("path : ")
16+
print("Enter end state from state {} travelling through path {} : ".format(state,path))
17+
reaching_state = [x for x in input().split()] that
18+
nfa[state][path] = reaching_state
19+
20+
print("\nNFA :- \n")
21+
print(nfa)
22+
print("\nPrinting NFA table :- ")
23+
nfa_table = pd.DataFrame(nfa)
24+
print(nfa_table.transpose())
25+
26+
print("Enter final state of NFA : ")
27+
nfa_final_state = [x for x in input().split()]
28+
29+
30+
new_states_list = []
31+
dfa = {}
32+
keys_list = list(list(nfa.keys())[0])
33+
path_list = list(nfa[keys_list[0]].keys())
34+
35+
36+
37+
# Computing first row of DFA transition table
38+
39+
dfa[keys_list[0]] = {}
40+
for y in range(t):
41+
var = "".join(nfa[keys_list[0]][path_list[y]])
42+
dfa[keys_list[0]][path_list[y]] = var
43+
if var not in keys_list:
44+
new_states_list.append(var)
45+
keys_list.append(var)
46+
47+
48+
49+
while len(new_states_list) != 0:
50+
dfa[new_states_list[0]] = {}
51+
for _ in range(len(new_states_list[0])):
52+
for i in range(len(path_list)):
53+
temp = []
54+
for j in range(len(new_states_list[0])):
55+
temp += nfa[new_states_list[0][j]][path_list[i]]
56+
s = ""
57+
s = s.join(temp)
58+
if s not in keys_list:
59+
new_states_list.append(s)
60+
keys_list.append(s)
61+
dfa[new_states_list[0]][path_list[i]] = s
62+
63+
new_states_list.remove(new_states_list[0])
64+
65+
print("\nDFA :- \n")
66+
print(dfa)
67+
print("\nPrinting DFA table :- ")
68+
dfa_table = pd.DataFrame(dfa)
69+
print(dfa_table.transpose())
70+
71+
dfa_states_list = list(dfa.keys())
72+
dfa_final_states = []
73+
for x in dfa_states_list:
74+
for i in x:
75+
if i in nfa_final_state:
76+
dfa_final_states.append(x)
77+
break
78+
79+
print("\nFinal states of the DFA are : ",dfa_final_states) #Printing Final states of DFA
80+
81+
82+
83+
"""
84+
# Code Ouput Example
85+
86+
No. of states : 4
87+
No. of transitions : 2
88+
state name : A
89+
path : a
90+
Enter end state from state A travelling through path a :
91+
A B
92+
path : b
93+
Enter end state from state A travelling through path b :
94+
A
95+
state name : B
96+
path : a
97+
Enter end state from state B travelling through path a :
98+
C
99+
path : b
100+
Enter end state from state B travelling through path b :
101+
C
102+
state name : C
103+
path : a
104+
Enter end state from state C travelling through path a :
105+
D
106+
path : b
107+
Enter end state from state C travelling through path b :
108+
D
109+
state name : D
110+
path : a
111+
Enter end state from state D travelling through path a :
112+
113+
path : b
114+
Enter end state from state D travelling through path b :
115+
116+
117+
NFA :-
118+
119+
{'A': {'a': ['A', 'B'], 'b': ['A']}, 'B': {'a': ['C'], 'b': ['C']}, 'C': {'a': ['D'], 'b': ['D']}, 'D': {'a': [], 'b': []}}
120+
121+
Printing NFA table :-
122+
a b
123+
A [A, B] [A]
124+
B [C] [C]
125+
C [D] [D]
126+
D [] []
127+
Enter final state of NFA :
128+
D
129+
130+
DFA :-
131+
132+
{'A': {'a': 'AB', 'b': 'A'}, 'AB': {'a': 'ABC', 'b': 'AC'}, 'ABC': {'a': 'ABCD', 'b': 'ACD'}, 'AC': {'a': 'ABD', 'b': 'AD'}, 'ABCD': {'a': 'ABCD', 'b': 'ACD'}, 'ACD': {'a': 'ABD', 'b': 'AD'}, 'ABD': {'a': 'ABC', 'b': 'AC'}, 'AD': {'a': 'AB', 'b': 'A'}}
133+
134+
Printing DFA table :-
135+
a b
136+
A AB A
137+
AB ABC AC
138+
ABC ABCD ACD
139+
AC ABD AD
140+
ABCD ABCD ACD
141+
ACD ABD AD
142+
ABD ABC AC
143+
AD AB A
144+
145+
Final states of the DFA are : ['ABCD', 'ACD', 'ABD', 'AD']
146+
147+
148+
"""

0 commit comments

Comments
 (0)