Programming assignment 1

Question 0.

Download the dfa code provided for this assignment. Read the JavaDoc first. Then read the code itself. Make a note of anything you don't understand, but don't spend too much time on minor details.

Question 1. (80 points.)

Complete the code of the accepts() method in the Dfa class.

Question 2. (20 points.)

Alter the code so that transitions can be labeled with multiple symbols, as introduced in Linz, Example 2.2. In other words, lines such as Q1 acd Q3 should now be permitted in dfa files. (The intended meaning of this line is that the dfa transitions from Q1 to Q3 on encountering a or c or d.)

Extra credit. (20 points.)

(If you attempt any extra credit problems, please make a new copy of your Java files and submit them separately, so that your attempt on the previous questions can be graded. In comments at the top of one of your Java files, indicate clearly which parts of the extra credit you have attempted) (i) Alter the code so that it works for nfas. (ii) Write code that converts an nfa to an equivalent dfa. (iii) Read Linz, Section 2.4, then implement an algorithm that minimizes the number of states in a dfa.