CS 2200 Fall 2020 HW 04 Dr. George Markowsky Computer Science Department Missouri Science & Tech Due Thursday, November 19, 2020, 11:59PM Submit your HW as a SINGLE PDF file that includes your answers, your programs, and their output. Also include any data files if you used them. Please make sure that your PDF is well-organized so we can quickly find all the pieces of each problem that belong together. PROBLEMS 1. (25 points) Write a Python NDFSA+ simulator that meets the following speci- fications. The machine definition and tape will be stored in a text file that has the extension “.ndfsa”. Note that we are not going to write a Python NDFSA simulator because it is very similar to this simulator. Also, if you have a file with no moves the NDFSA+ simulator can run it without any issues. Each line of the text file shall begin with one of the following capital letters: A, B, D, O, S, T. We will explain the meaning of these letters below. The letters appear at the very beginning of the line and there is a single blank space after the letter for readability. Each line must begin with a letter. If the file does not meet the specifications, it is rejected. If a line does not have a letter on some line, the file is rejected. The first line must be an A line which contains just a single string consisting of all the characters in the alphabet. There is only one A line per file. To simplify coding, we make the restriction that the alphabet can never contain the character @ since we want to use it to represent . Note that you can enter into a Graphviz file and Graphviz will incorporate the in arrow labels but not in state labels. Depending on what text editor you are using, entering might be tricky, which is why I am letting you use @ instead of if you wish. The A line is followed by a series of S lines. S stands for state. An S line states that the line gives information about states such as their names and whether they are final or not. An S line has the following structure S S1,Bool1,S2,Bool2,...,Sk,Boolk where Si is the name of a state and Booli is 1 if the state is final and 0 is the state is not final. 1 Next comes a B line which contains the beginning (start) state There is only one such line and it looks like B State. Next come the D lines where D stands for delta. The structure of a D line is as follows: D S1,C*1,N1,S2,C*2,N2...,Sk,C*k,Nk where Si is the current state, C*i is the character being read or @ if we are denoting an move, and Ni is the new state that the machine enters. Each line contains a whole number of triples although the number of complete triples per line is not specified. The lines could lack any entries, but they still should have the blank following the letter. Note, the .ndfsa file does not do anything special for non-determinism – it just lists all the possible moves just as for a FSA. It is up to your simulator to group the moves in a useful manner. After the last D line, come a series of alternating T and O lines. T stands for tape and contains a character string representing a initial tape. Every T line is followed by an O line. The O line is blank if the preceding T line has not been processed by the machine. The line contains the word ”accepted” if the machine would accept the string on the T line and contains the word ”rejected” if the machine would reject the string on the T line. After the program processes the file it should process any T lines for which there are no answers on the corresponding O lines. Once the simulator finishes, it should reconstruct the file that it read, but add any new computations to the updated file. Include your program with comments in the PDF file that you will submit. Be sure that the comments include the information that I gave you about the format of the file. You will use this simulator to test all of the solutions to the remaining problems. For each problem you will include the .ndfsa file that contains the solution. 2. (20 points) Write a program that can generate a Graphviz file from either a .fsa or .ndfsa file. The straightforward way of doing this can generate multiple arrows between the same two nodes. Your generator should combine the arrows into a single arrow and merge the labels into one. For example, let’s say that a machine transistions from state 1 to state 2 when it encounters either an a or a b. The Graphviz file should have just a single arrow from state 1 to state 2 with the label ’a,b’. Of course, if there are additional arrows from state 1 to state 2, the labels on those arrows should be added to the ’a,b’ label. To test your program, produce the Graphviz files for all the FSA’s that you produced for HW 03 and also for the NDFSA+ that you will produce for the next problem. 3. (30 points) Write a Python program that takes regular expression written in our notation, and produces an NDFSA+ that has exactly the same language as the regular expression. The NDFSA+ should be specified by a .ndfsa file. To test your program, produce the NDFSA+ to recognize the language generated by the regular expression (a+b)*abc(b+c)*. Produce at least 10 strings generated by the 2 regular expression of length 15 and run them through your NDFSA+ simulator to prove that they are all accepted. Be sure to include a Graphviz diagram in your PDF of the NDFSA+ that you produced. We will discuss the Graphviz program in class the week of October 26. 4. (25 points) For each of the following, find a FSA automaton that recognizes the language or prove that there is no FSA that recognizes the language. If it can be solved by a FSA give the .fsa file, at least 10 sample cases, and a Graphviz diagram. If there is no FA that can recognize the language, prove that fact. (a) L1 = { all binary strings divisible by 3 } (b) L2 = { all binary strings divisible by 5 } (c) L3 = { all unary strings that represent prime numbers} (d) L4 = { all unary strings that represent composite numbers } (e) L5 = { w ∈ {a,b,c}* such that w is a palindrome} 3
欢迎咨询51作业君