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:
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.
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.