(a) (3pts) For each of the following languages give two strings that are members of the language and two strings that are not. Assume that the alphabet is $ = {a,b} b*abab* (au bau bb) . (U a)b+ (b) (2pts) Give a regular expression for the following language over alphabet S = {x,y} Lo = {w w contains at least two y's and at most one x} (c) (8pts) Give a regular expression for the following languages. The alphabet is {x,y}. L1 = {w w begins with y ends with x} L2 = {w/ w the length of w is at most 4} L3 = {wl w starts with a y and has odd length, or starts with a r and has even length} Ls = {wl is any string except 1 and yy} (a)(5pts) Use the procedure described in class to convert the following regular expression to nondeterministic finite automata. You need to show your work and intermediate steps for full credit. (yu ry*)* (e)(7pts) Use the procedure described in class to convert the following FAs to regular expressions. You need to show the intermediate steps for full credit B y y D Use the pumping lemma to show that the following languages are not regular (a) (5 pts) {0"1"O" | m,n >0} (b) (5 pts) {uruw | W {0,1}*} (c) (5 pts) Let S = {0, 1,-- =} and SUB = {x=y=2|,y,z are binary integers, and x is the result of the subtraction of z from y}. For example: 1 = 1-0, 10 = 11 - 01 are strings in SUB but not 1=1 - 1 or 11 = 11 10