Submission deadline: Thursday, February 9, 2012 at 10:00 pm.
Problem 1 concerns linking MIPS code and MERL format files. Click here for the MERL file format specification.
To produce the needed binary output, first figure out what each word in the result needs to be, and create an assembly file with a .word directive for each word in the result. Then run cs241.wordasm on this file to produce the needed output. Note that you will need to include the hex encodings of the MERL header and symbol table in your assembly file.
Example: Suppose you determine that the correct MERL output will consist of the words 0x10000002 0x00000010 0x00000010 0x03e00008. Then you should create a file with contents
.word 0x10000002 .word 0x00000010 .word 0x00000010 .word 0x03e00008and run cs241.wordasm on this file to produce the needed MERL file for submission.
Note: The result of linking these two files may be a standalone program or it may be a piece of a larger program. Therefore, you should not remove any ESD entries after linking. Your handling of ESR and relocation entries is, of course, prescribed by the linking procedure.
For problems 2-9, you are to define DFAs (deterministic finite automata) to recognize several formal languages. Each DFA is represented as a file that will enumerate the alphabet, states, initial state, final states, and transitions that comprise the DFA, in the format described in http://www.student.cs.uwaterloo.ca/~cs241/dfa/DFAfileformat.html. For bonus marks, you may write a Java, Scheme, or C++ program that reads such a file and implements the DFA recognizer.
You must submit to the Marmoset grading system. For all except the bonus problem, your submission is a text file containing the description of a DFA. You may create this text file with any editor on the Unix environment. Hint: some of the DFA description files may be large (of the order of 100 lines) and you may wish to write a program to help you generate them. For all except the bonus problem, every failed test will result in a message giving the specific input causing the failure. There are no release tests.
For testing (all of your submissions, not just the bonus) an implementation of the bonus problem is available in the student.cs environment. To use it, enter
java cs241.DFA < inputfile
where inputfile is a DFA plus a set of test inputs as described in the bonus problem specification.
Write a DFA with alphabet {0,1} that recognizes binary integers that have no useless (leading) zeroes and are not divisible by 3.
Write a DFA with alphabet {0,1} that recognizes binary integers that have no useless (leading) zeroes and are not divisible by 2 or by 3.
The vending machines on campus sell candy for $1.25. They accept nickels (worth $0.05), dimes (worth $0.10), quarters (worth $0.25) and loonies (worth $1.00). Write a DFA that describes a sequence of coins that can be put into the machine to total exactly $1.25. The alphabet symbols are the names for the coins: { nickel, dime, quarter, loonie }.
Write a DFA that recognizes a decimal number between -128 and 127 inclusive, with no useless zeroes. (Zeroes are required and only permitted if removing them changes the meaning of the number.) The alphabet symbols are {0,1,2,3,4,5,6,7,8,9,- }.
Write a DFA with alphabet {cat, dog, iguana, mouse} that recognizes any sequence of these animals so long as it contains the name of each animal at least once, in alphabetical order. That is, "cat dog mouse iguana dog mouse" and "iguana cat mouse dog iguana iguana mouse iguana" are in the language, but not "cat dog mouse iguana dog" .
Write a DFA that recognizes any string from the alphabet {a,b,c,d} containing abcabd as a substring.
Write a DFA with the alphabet {E,F,+,id,#} that recognizes the same set of strings as the NFA shown below:
Write a DFA with the alphabet {E,F,+,id,#,$} that recognizes the same set of strings as the NFA shown below:
Write a Java, Scheme, or C++ program that implements a DFA recognizer. Your program should read a file containing a DFA description as defined above, followed by several additional lines of input. Each additional line of input is a string of alphabet symbols separated by spaces. For each string, your program should print true if the string is in the language, and false if it is not. You may assume that the input to your program is valid according to the definition given in the file format specification.
Sample input:
2 0 1 5 start zero 0mod3 1mod3 2mod3 start 2 zero 0mod3 8 start 0 zero start 1 1mod3 1mod3 0 2mod3 1mod3 1 0mod3 2mod3 0 1mod3 2mod3 1 2mod3 0mod3 0 0mod3 0mod3 1 1mod3 0 1 1 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
Correct output for sample input:
true false false true false false true false