-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathuniversal_dfa.py
103 lines (76 loc) · 4.02 KB
/
universal_dfa.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
https://powcoder.com
代写代考加微信 powcoder
Assignment Project Exam Help
Add WeChat powcoder
https://powcoder.com
代写代考加微信 powcoder
Assignment Project Exam Help
Add WeChat powcoder
# Universal DFA
# Boston University CS 332
# This file contains starter code to help you design a program that
# 1) Prompts the user for a string encoding a DFA D and a binary string w
# 2) Prints the sequence of states D enters when run on w, as well as whether D accepts or rejects on input w
#
# Your job is to implement the function simulate_DFA that simulates running D on w and outputs the list of states it enters
import re
class UniversalDFA(object):
# Parse an encoded DFA into a 3-tuple
def encoding_to_triple(self, encoded_DFA):
list = encoded_DFA.split("#")
raw_transitions = list[0]
# Use regular expression(!) to split string encoding transition function into list of triples [(p, a, q), ...]
list_transitions = re.findall(r'(\w+,\w+,\w+)', raw_transitions)
# Convert list of transitions into dictionary
transitions = {} # initialize empty dictionary
for triplet in list_transitions:
trip_list = triplet.split(",")
transitions[(trip_list[0], trip_list[1])] = trip_list[2]
start_state = list[1]
final_states = list[2].split(",")
return (transitions, start_state, final_states)
######################################################
######## DON'T TOUCH THE CODE ABOVE THIS LINE ########
######################################################
# Input:
# -----------------
# A string encoded_DFA encoding a DFA over the alphabet {0, 1}, and a string input_string over alphabet {0, 1}
# The format of the encoding for a DFA is "d#q0#F" where d is a list of triples capturing the transition function, q0 is the start state, and F is a comma-separated list of accept states
# Example: encoded_DFA = "(q0,0,q1),(q0,1,q0),(q1,0,q0),(q1,1,q1)#q0#q1" encodes a DFA testing whether its input contains an odd number of 0's
# The transition function d is d(q0, 0) = q1, d(q0, 1) = q0, d(q1, 0) = q0, d(q1, 1) = q1
# input_string = "00101111" specifies a binary input to the above DFA
#
# Output:
# ----------------
# Return a list of strings consisting of the states the DFA enters upon reading input_string, followed by whether the DFA accepts or rejects
# Example: transcript = ["q0", "q1", "q0", "q0", "q1", "q1", "q1", "q1", "q1", "accept"]
def simulate_DFA(self, encoded_DFA, input_string):
(transitions, start_state, final_states) = self.encoding_to_triple(encoded_DFA)
transcript = []
## OPTIONAL STUFF:
## You may want to uncomment some of the code snippets below to get a feel for the syntax of the various components output by the parser
## transitions is a dictionary (set of key-value pairs). Keys are pairs of strings (current_state, character) and values are strings next_state
## Example: transitions = {("q0", "0"): "q1", ("q0", "1"): "q0", ("q1", "0"): "q0", ("q0", "1"): "q1"}
# print(transitions)
# print(transitions[("q0", "0")])
## start_state is a string, e.g., "q0"
# print(start_state)
## final_states is a list of the accepts of the DFA, e.g., ["q1"]
# print(final_states)
#
# YOUR CODE HERE
#
return transcript
######################################################
######## DON'T TOUCH THE CODE BELOW THIS LINE ########
######################################################
def prompt(self):
# Prompts the user for an encoded DFA and a string, and simulates the DFA on that string
encoded_DFA = input("Enter your DFA: ")
input_string = input("Enter your string: ")
transcript = self.simulate_DFA(encoded_DFA, input_string)
for str in transcript:
print(str)
if __name__ == "__main__":
universal_DFA = UniversalDFA()
universal_DFA.prompt()