1. Let L1 be a formal language using the binary digits 0 and 1 as its character set, such that a string is in L1 if and only if it has 3 or more 1's in a row somewhere in it. A. (15 points) Draw a non-deterministic finite state automaton that recognizes L1. B. (15 points) Write a regular expression whose language is L1. 2. Let L3 be a formal language using the letters o, a, and y, such that a string is in L3 if and only if it has the string "yoya" somewhere within it. Note that yyyoyoyaaa is in L3, as are yyoya, yoyoya, and yoyaaya, but yoaya is not in L3 A. (15 points) Draw a nondeterminisic FSA that recognizes L3 B. (15 points) Write a regular expression whose language is L3. C. (5 points) Draw a Deterministic FSA that recognizes L3. 3. Describe in English the language of each of the following RE's: A. (15 points) a*b B. (15 points) (ab)* 4. (5 points) Draw a Deterministic FSA that accepts a string made up of the characters x and y if and only if it has at most two xs and has more xs than ys. E.g., your DFA should accept the strings "x" "wx" and "yxx" but not "y" or "Xy" or "Xyxyx". It may accept or not accept the empty string , whichever you prefer