3. (Universal DFA) This short programming exercise aims to make the idea of designing a Tur- ing machine that takes a DFA as input less disturbing. Recall the language ADFA = {(D,W) | D is a DFA accepting input w}. Deciding membership in this language corresponds to the compu- tational problem of determining whether DFA D accepts input w. (a) The file universal_dfa.py contains starter code that will help you implement a Turing machine Python program solving this problem. Implement a program that prompts the user for an (appropriately encoded) DFA D and a binary string w, outputting i) the sequence of states D enters when run on w, and ii) whether D accepts or rejects input w. The starter code file describes the expected syntax for the input and output of your solution. This is not a software engineering class, so your program is allowed to fail arbitrarily (including failing silently) if its inputs do not correctly encode a DFA and a binary string. If you don't like Python, you can implement your program in another high-level programming language (Java, C++, Haskell, ...) that the grading staff can read. (No Malbolge, please.) The downside is that you won't have the starter code to parse the input for you. (b) Let x be your special binary input from HW4 Problem 3a. Record the input and output of your program when you use it to determine whether the DFA represented by the following state diagram accepts input r. 0 1 start 90 93 1 0 0 1 0 91 92 1 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[o], trip_list[1])] trip_list[2] start_state = list[1] final_states = list[2].split(",") return (transitions, start_state, final_states) # 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#q@#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 = "(0,0,1),(0,1,90), (q1,0,90), (q1,1,q1)#q0#q1" encodes a DFA testing whether its input contains an odd number of o's # The transition function d is d(0, 0) = q1, d(0, 1) = q0, d(q1, 0) = qo, 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 = ["90", "q1", "90", "90", "q1", "91", "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 = {("90", "0"): "q1", ("90", "1"): "90", ("q1", "0"): "90", ("90", "1"): "91"} # print(transitions) # print(transitions[("90", "0")]) ## start state is a string, e.g., "90" # print (start_state) ## final_states is a list of the accepts of the DFA, e.g., ["91"] # print(final_states) # # YOUR CODE HERE # return transcript 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 II name == : __main universal_DFA = UniversalDFAO) universal_DFA.prompt() 3. (Universal DFA) This short programming exercise aims to make the idea of designing a Tur- ing machine that takes a DFA as input less disturbing. Recall the language ADFA = {(D,W) | D is a DFA accepting input w}. Deciding membership in this language corresponds to the compu- tational problem of determining whether DFA D accepts input w. (a) The file universal_dfa.py contains starter code that will help you implement a Turing machine Python program solving this problem. Implement a program that prompts the user for an (appropriately encoded) DFA D and a binary string w, outputting i) the sequence of states D enters when run on w, and ii) whether D accepts or rejects input w. The starter code file describes the expected syntax for the input and output of your solution. This is not a software engineering class, so your program is allowed to fail arbitrarily (including failing silently) if its inputs do not correctly encode a DFA and a binary string. If you don't like Python, you can implement your program in another high-level programming language (Java, C++, Haskell, ...) that the grading staff can read. (No Malbolge, please.) The downside is that you won't have the starter code to parse the input for you. (b) Let x be your special binary input from HW4 Problem 3a. Record the input and output of your program when you use it to determine whether the DFA represented by the following state diagram accepts input r. 0 1 start 90 93 1 0 0 1 0 91 92 1 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[o], trip_list[1])] trip_list[2] start_state = list[1] final_states = list[2].split(",") return (transitions, start_state, final_states) # 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#q@#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 = "(0,0,1),(0,1,90), (q1,0,90), (q1,1,q1)#q0#q1" encodes a DFA testing whether its input contains an odd number of o's # The transition function d is d(0, 0) = q1, d(0, 1) = q0, d(q1, 0) = qo, 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 = ["90", "q1", "90", "90", "q1", "91", "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 = {("90", "0"): "q1", ("90", "1"): "90", ("q1", "0"): "90", ("90", "1"): "91"} # print(transitions) # print(transitions[("90", "0")]) ## start state is a string, e.g., "90" # print (start_state) ## final_states is a list of the accepts of the DFA, e.g., ["91"] # print(final_states) # # YOUR CODE HERE # return transcript 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 II name == : __main universal_DFA = UniversalDFAO) universal_DFA.prompt()