Reference no: EM13287328

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 of instance one 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.
5. Define a language that is not a regular language using a context-free grammar that is not ambiguous. The alphabet of the language must contain at least five characters. Describe in English the strings of the language. Choose any string that is in the language and demonstrate that it is in the language by showing the left-most derivation that derives it. Draw the parse tree that corresponds to the left-most derivation. Give an example of one string that is not in the language.