Assignment 1. For a given Alphabet (a, b) and Ll={x | x ends with aa draw FA that Accept L1 2. For a given Alphabet (a, b) and L2={x|x ends with b and does not contain the substring aa) draw FA that Accept L2 3. For a given Alphabet (a, b) and L3={x | x contains the substring abbaab) draw FA that Accept L3 4. Prove by induction 5. Define FA, TG, GTG, and draw GTG that accepts all strings without a double b 6. Define Moore, and Mealy Machine 7. Given TM, what language it accepts? 8. Define length, reverse, palindrome, Kleene star, with example a. Consider the language S*, where S={a b}. How many words does this language have of length 22, of length 3? of length n? b. If S={aa, b} then what is S* 9. Define the language Arithmetic Expression using recursion. Write recursive definition for the set of all polynomial in the two variable x and y. 10. Define the language associated with any regular expression a. Give RE for 1) all string that end in a double letter, 2) all strings that do not end in a double letter b. Define the language for the following RE i. ((a+b)a)* ii. (a(a+bb)*)* 11. (b(bb)*)*(aaa)*b(bb)*)*