a) (15 points) Assume that 2 = {a, b}. For each of the following regular expressions,...

 

Transcribed Image Text:

a) (15 points) Assume that 2 = {a, b}. For each of the following regular expressions, find a string x * that is not recognized by the given regular expression. If all strings are recognized, write None." 1) (b* + a*b)* 11) (a + ba + ab)*. b* iii) (b*a*ba)*a*b* b) (10 points) Let E = {a,b). Give a regular expression for the following languages 1) The set of strings that start with ab and ends with b. Note that ab and abb belong to the language. ii) The set of strings that contain the substring aa exactly once. Note that the substring baaab contains the substring aa twice. Hence, two different substrings may overlap and have shared characters. a) (15 points) Assume that 2 = {a, b}. For each of the following regular expressions, find a string x * that is not recognized by the given regular expression. If all strings are recognized, write None." 1) (b* + a*b)* 11) (a + ba + ab)*. b* iii) (b*a*ba)*a*b* b) (10 points) Let E = {a,b). Give a regular expression for the following languages 1) The set of strings that start with ab and ends with b. Note that ab and abb belong to the language. ii) The set of strings that contain the substring aa exactly once. Note that the substring baaab contains the substring aa twice. Hence, two different substrings may overlap and have shared characters.