I. Consider the following two languages on alphabet = {a , the set of all words w on the alphabet such that w contains at least three a's 12, the set of all words w on the alphabet such that w contains the same number of a's and b's Now, I have a robot M holding two flowers, red and blue, and, at each second, shows exactly one of the two. When the red is observed, this event is called a; when the blue is oserved, this event is called b. (The programs below may use some interrupt mechanism as I showed in class.) (1). Please program the robot such that the set of all its observable behaviors is exactly L1; (2). Please program the robot such that the set of all its observable behaviors is exactly L2; (3). Please argue intuitively why you only need a fixed and finite amount memory for the program in (1) while you have to use an unbounded amount of memory for the program in (2) (4). Because of the arguments established in (3), we are ready to con- clude that L2 is more complex than L. Indeed, this is true. However, this conclusion does not imply that every word in L2 is more complex than every word in L\. For instance, consider the tollowing two words: un = aaababaababaaabbaab E L1 w2aaaaaaaaabbbbbbbbb L2 It is "clear" that w is more complex than w/2, actually. In other words, we may need a completely new method in measuring the complexity of a single word (herein, I am not interested in measuring the complexity of a languages as in (3). Please suggest a way to measure the complexity of a word I. Consider the following two languages on alphabet = {a , the set of all words w on the alphabet such that w contains at least three a's 12, the set of all words w on the alphabet such that w contains the same number of a's and b's Now, I have a robot M holding two flowers, red and blue, and, at each second, shows exactly one of the two. When the red is observed, this event is called a; when the blue is oserved, this event is called b. (The programs below may use some interrupt mechanism as I showed in class.) (1). Please program the robot such that the set of all its observable behaviors is exactly L1; (2). Please program the robot such that the set of all its observable behaviors is exactly L2; (3). Please argue intuitively why you only need a fixed and finite amount memory for the program in (1) while you have to use an unbounded amount of memory for the program in (2) (4). Because of the arguments established in (3), we are ready to con- clude that L2 is more complex than L. Indeed, this is true. However, this conclusion does not imply that every word in L2 is more complex than every word in L\. For instance, consider the tollowing two words: un = aaababaababaaabbaab E L1 w2aaaaaaaaabbbbbbbbb L2 It is "clear" that w is more complex than w/2, actually. In other words, we may need a completely new method in measuring the complexity of a single word (herein, I am not interested in measuring the complexity of a languages as in (3). Please suggest a way to measure the complexity of a word