Programming assignment 1
To turn in this assignment, please submit a single zip file of your
Java files to Moodle.
- 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.)
(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.