Find regular expressions describing exactly each of the following strings (on A = {a, b} unless otherwise stated). A. All strings of a’s of odd length B. All strings of length exactly 4 C. All strings of a, b, and c that begin with a or c and end with b D. All strings with at least two b’s E. All strings with at least one a and at least one b F. All stings that contain at least one double letter G. All strings that do not contain a double letter H. All stings that contain the patters aba or bab or both I. All strings with an even number of a’s 2)
Describe in English, the strings that are defined by each of the following regular expressions: A. a* ba* ba* B. (a + b)*(aa + bb) The next questions refer to the following regular expression: b + a 3 (b + ) a2 (a + b)* 3) Indicate which of the following strings match the regular expression above. A. baaabbaaab B. baaabaaaab C. baaaaabbaa D. aaabaa 4) Circle the first letter in each string above that does not match the requirements of the regular expression. 5) What is the shortest possible string that WOULD NOT match the regular expression? 6) What is the shortest possible string that WOULD match the regular expression? 7) Create a Finate State Acceptor diagram that is equivalent to problem 1E above.
