1) Give a regular expression to describe the language that includes strings over the alphabet {a,b,c}, where strings have length at least four and in the last four symbols either of the substrings aa or cc occurs. So, the strings aaabaccbbaa, bbccb and aacc are in the language but acac and bbbbbabbc are not. 2 Draw the description of a fsa that accepts all strings over {x,y,z} such that all occurrences of symbols in {x,y} happen before any occurrences of the symbol z and the number of z's is even. 3) Consider the language over the alphabet {0,1} that includes all strings consisting of a prefix (a substring of k o's followed by a suffix (a substring of n l's, where k 0; i.e., strings of the form oki", where k 0. So, 0001111,011 and 1 are in the language. Can this language be recognized with a fsa? If you answer yes, draw the description of the machine. If your answer is no, give an informal reasoning for your answer. 4) Describe in detail (pseudocode) a one-stack fsa to recognize the language over the alphabet {a,b} that includes strings of the form a"b", where n > 0. Recall a" stands for a string with n occurrences of the symbol a