CS241 — Spring 2018 — Assignment 4

Assignments for CS 241
← Assignment 3 Assignment 4 Assignment 5 →
Wednesday, May 30 at 5:00pm Wednesday, June 6 at 5:00pm Friday, June 15 at 5:00pm
P1P2P3P4P5P6P7P8P9BonusP10P11

Part I: Regular Languages (DFAs and NFAs)

For problems 1-8, 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 the DFA File Format page. For problem 9, you will write a Racket or C++ program that reads such a file from stdin and implements the DFA recognizer. For bonus marks, you may modify your solution to Problem 9 to support NFAs and epsilon NFAs.

For problems 1-8, your submission to Marmoset 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 (on the order of 100 lines) and you may wish to write a program to help you generate them. For problems 1-8, every failed test will result in a message giving the specific input causing the failure, and there are no release tests.

For testing, an implementation of a DFA recognizer is available on the student environment. To use it, enter cs241.DFA < _inputfile_, where inputfile is a DFA plus a set of test inputs as described in the problem 9 specification.

Problem 1 — 10% (notdiv3.dfa)

Write a DFA with alphabet {0,1} that recognizes binary integers that have no useless (leading) zeroes and are not divisible by 3.

Click here to return to the top of the page.

Problem 2 — 10% (not23.dfa)

Write a DFA with alphabet {0,1} that recognizes binary integers that have no useless (leading) zeroes and are not divisible by 2 or 3.

Click here to return to the top of the page.

Problem 3 — 7% (coins.dfa)

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 of the coins: {nickel, dime, quarter, loonie}.

Click here to return to the top of the page.

Problem 4 — 7% (int.dfa)

Write a DFA that recognizes a decimal number between -128 and 127 inclusive, with no useless zeroes. The alphabet symbols are {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -}.

Click here to return to the top of the page.

Problem 5 — 7% (pets.dfa)

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".

Click here to return to the top of the page.

Problem 6 — 7% (abcd.dfa)

Write a DFA that recognizes any string from the alphabet {a, b, c, d} containing abcabd as a substring.

Click here to return to the top of the page.

Problem 7 — 7% (nfa1.dfa)

Write a DFA with the alphabet {E, F, +, id, #} that recognizes the same set of strings as the epsilon NFA shown below:

First epsilon NFA

Click here to return to the top of the page.

Problem 8 — 7% (nfa2.dfa)

Write a DFA with the alphabet {E, F, +, id, #, $} that recognizes the same set of strings as the epsilon NFA shown below:

Second epsilon NFA

Click here to return to the top of the page.

Problem 9 — 22% (dfa.rkt or dfa.cc)

Write a Racket or C++ program that implements a DFA recognizer. Your program should read on stdin 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

Click here to return to the top of the page.

Bonus Problem — 5% (nfa.rkt or nfa.cc)

Modify your solution to Problem 9 to support NFAs. For full marks, you must support both NFAs and epsilon NFAs, where an epsilon-transition is specified by writing "epsilon" as the symbol to be transitioned on (epsilon need not be included in the alphabet). For partial marks you may support only NFAs. You may assume that the input to your program is valid according to the definition given in the file format specification.

Click here to return to the top of the page.

Part II: WLP4

This is the beginning of a series of several assignments that involve learning WLP4 and writing a compiler that translates WLP4 to MIPS assembly language.

Please consult the WLP4 Programming Language Tutorial for an informal explanation of WLP4; the WLP4 Language Specification should be consulted for the definitive specification of the WLP4 language.

The following WLP4 program computes the sum of two integers, a and b.

//
// WLP4 program with two integer parameters, a and b
//     returns the sum of a and b
//
int wain(int a, int b) {
    return a + b; // unhelpful comment about summing a and b
}

You may test this program on the student.cs environment by placing it in a file named test.wlp4 and entering the following commands, which compile it to MIPS machine language and run it with the familiar mips.twoints and mips.array commands from Assignments 1 and 2:

wlp4c < test.wlp4 > test.mips
mips.twoints test.mips

Problem 10 — 8% (exp.wlp4)

Read about exponentiation by squaring, a method to compute x^n more efficiently than simply multiplying a variable by x n times. You may not use while loops in this question — you must solve it recursively.

Click here to return to the top of the page.

Problem 11 — 8% (binsearch.wlp4)

Write a WLP4 function that performs binary search on an array of integers. The function must be called binsearch and must accept three parameters: a pointer to the beginning of the array, an integer representing the array's size, and an integer value to search for in the array, in that order. You may assume that the array is sorted in ascending order and contains each unique value exactly once. If the search value is in the array, your function should return its index. If not, your function should return -1. To test your function, you will need to write a wain function as well, but do not submit this wain function; marmoset will reject submissions with a wain. We will use our own wain to test your implementation.

You may find the relevant Wikipedia article helpful.

Click here to return to the top of the page.