1. Consider the following two languages on alphabet = {a, b}: L1, the set of all words w on the alphabet such that w contains at least

three as; L2, the set of all words w on the alphabet such that w contains the same

number of as and bs. 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 L1. Indeed, this is true. However, this conclusion does not imply that every word in L2 is more complex than every word in L1. For instance, consider the following two words:

w1 = aaababaababaaabbaab L1

w2 = aaaaaaaaabbbbbbbbb L2 It is clear that w1 is more complex than w2, 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.