CSC 124/258 Assignment 1. Due Thursday 2/9/06 ---- 0. Read chapter 2 of the text book. 1. Given regular expression (ab)*(b|c)+ Determine if the following strings are matched by the expression and explain why (hint: to check answer, Java has a String.matches method, but you'll still have to explain why). i. ababccc ii. ac iii. c iv. bbbb v. Write an regular expression over the alphabet {a,b} that represents all strings with an even number of a's. For example, it should match "aabababaa" because there are 6 a's in the string, but it should not match "aaa". vi. Sketch a (deterministic) finite state machine for the regular expression above. Hint: you should need no more than two states: one for even, and one for odd. 2. Implement the finite state machine in Figure 2.4, page 22 of your text. Be sure that your machine detects the longest matches. This particular machine is designed to recognize single tokens. Read the textbook's suggestions as to how to do this first. Your program should be flexible enough to accomodate different state machines. I suggest that you make a slight use of inheritance based on the following skeleton. That is, inside the adfa abstract superclass you will write code common to all DFAs. Arrays represent the state transition table and set of final states. The abstract method "setdfa" is to be defined by subclasses that implement particular DFAs. The superclass should contain a method "match" that determines if a DFA accepts a given string (heed the text's hint as to dead state and the "Last-Final" variable). By placing this method in the superclass it can be used on all DFAs. This is a form of polymorphism. You may also need additional methods to make "match" work. You can make modifications to the classes. For example, you might want to use an ArrayList instead of a regular array to represent the final states. ------ // abstract class for all DFAs: abstract class adfa { int[][] Table; // state transition table. int rows, cols; // rows=number of states, cols=size of alphabet int[] finals; // vector of final states String[] translation; // meaning of final states. int start; // start state // state 0 is always assumed to be the "dead state". public abstract void setdfa(); // to be defined by subclass for // specific DFA. public void match(String s) { //... should determine if s is accepted by the DFA defined by setdfa. } } //adfa // sample subclass for a dfa that accepts identifiers (from page 23 of text) class id extends adfa { public void setdfa() { rows = 3; cols = 128; //128=ascii set, rows=number of states Table = new int[rows][cols]; finals = new int[1]; // there is only one final state, 2 finals[0] = 2; translation = new String[rows]; translation[2] = "identifier"; // meaning of final state start = 1; int i, j; for(i=0;i