1. (1 pt) ALEX is the set of valid algebraic expressions recursively defined by: Rule 1: All polynomials are in ALEX Rule 2: If f(x) and g(x) are in ALEX, then so are: i. (f(x)) ii. -(f(x)) iii. f(x) + g(x) iv. f(x) - g(x) v. f(x)g(x) vi. f(x) g(x) vii. f(x) viii. f(g(x)) Assuming that the rules seen in class recursively defining polynomials can be used here to prove x+2 and 3x are polynomials, show that (x + 2)" is in ALEX. 2. (1 pt) Let x and y be two words (both different than the empty string) and xy is their concatenation. Show that if x, y and xy are all in PALINDROME, then there is a word z such that x= Z' and y=z" for some integers n and m. 3. (1 pt) Let S={ab, bb) and T={ab, bb, bbb). Show that S**T* but that S*ct*. 4. (1 pt) Write the regular expression for the language of all strings, over alphabet (a, b), that end in a double letter, i.e. ending in aa or bb but not ab or ba 5. (1 pt) Draw Deterministic Finite Automata to accept the following sets of strings, over the alphabet {0,1}, that contain exactly four Os (not necessarily consecutive zeros) Extra Credit: (1 pt) Write the regular expression for the language of all strings, over alphabet {0,1), the set of all strings in which every pair of adjacent zeros appears before any pair of adjacent ones. Justify. 1. (1 pt) ALEX is the set of valid algebraic expressions recursively defined by: Rule 1: All polynomials are in ALEX Rule 2: If f(x) and g(x) are in ALEX, then so are: i. (f(x)) ii. -(f(x)) iii. f(x) + g(x) iv. f(x) - g(x) v. f(x)g(x) vi. f(x) g(x) vii. f(x) viii. f(g(x)) Assuming that the rules seen in class recursively defining polynomials can be used here to prove x+2 and 3x are polynomials, show that (x + 2)" is in ALEX. 2. (1 pt) Let x and y be two words (both different than the empty string) and xy is their concatenation. Show that if x, y and xy are all in PALINDROME, then there is a word z such that x= Z' and y=z" for some integers n and m. 3. (1 pt) Let S={ab, bb) and T={ab, bb, bbb). Show that S**T* but that S*ct*. 4. (1 pt) Write the regular expression for the language of all strings, over alphabet (a, b), that end in a double letter, i.e. ending in aa or bb but not ab or ba 5. (1 pt) Draw Deterministic Finite Automata to accept the following sets of strings, over the alphabet {0,1}, that contain exactly four Os (not necessarily consecutive zeros) Extra Credit: (1 pt) Write the regular expression for the language of all strings, over alphabet {0,1), the set of all strings in which every pair of adjacent zeros appears before any pair of adjacent ones. Justify