Answer the following questions:

1. Write a regular expression defining strings that begin with an a and end with a b and can contain any number (including zero) of c's or d's in the middle. Every c that is in the string must be followed by at least one d.

2. Construct a deterministic finite state automaton with no more than four states that accepts the language defined by the regular expression in problem 1.

3. Define an unambiguous context free grammar that generates the language of strings containing a series of a's followed by a series of b's followed by a series of c's concluding with a series of d's. The number of a's must be exactly the sames as the number of d's and the number of b's must be exactly the same as the number of c's. The strings must contain at least one instance of each of the four letters. Examples of valid stings are:

aaabbccddd abbbcccd

Is this a regular language? Explain your answer.

4. Provide a left-most derivation of the second example shown in the previous problem and a parse tree that corresponds to that derivation.

**Subject Computer Science Theoretical Computer Science**