Exercise 1.

Write a regular expression for strings (or sentences) over the alphabet {a, b}, that start and end with the same letter, that is, either as or bs. For example, strings abba, aa, babab should be in the regular set defined by the regular expression.

Exercise 2.

Draw a DFA for the above set.

1)Implement the DFA of (b) in Java. As the hint, the following is the code for a DFA for recognizing string ing. The final state is 3 and in this state it prints a message Accepted. The print out statement is not shown.

String s = scan.next();

int state = 0;

for (char c : s.toCharArray()) {

switch (state) {

case 0: state = (c=='i')? 1 : 0;

break;

case 1: state = (c=='n')? 2 : ((c=='i')? 1 : 0);

break;

case 2: state = (c=='g')? 3 : ((c=='i')? 1 : 0);

break;

case 3: state = (c=='i')? 1 : 0;

}

}

Exercise 2.

Draw and implement a DFA for Java identifiers. It should accept identifier names like: count4, cou67nt, _count, etc. But it should not accept identifiers such as 3count, %x, #@hello, hello@.