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

three a’s;
L2, the set of all words w on the alphabet such that w contains thesame

number of a’s and b’s.
Now, I have a robot M holding two flowers, red and blue, and, ateach second, shows exactly one of the two. When the red isobserved, this event is called a; when the blue is oserved, thisevent is called b. (The programs below may use some interruptmechanism as I showed in class.)

(1). Please program the robot such that the set of all itsobservable behaviors is exactly L1;

(2). Please program the robot such that the set of all itsobservable behaviors is exactly L2;

(3). Please argue intuitively why you only need a fixed andfinite amount memory for the program in (1) while you have to usean unbounded amount of memory for the program in (2).

(4). Because of the arguments established in (3), we are readyto con- clude that L2 is more complex than L1. Indeed, this istrue. However, this conclusion does not imply that every word in L2is more complex than every word in L1. For instance, consider thefollowing two words:

w1 = aaababaababaaabbaab ? L1

w2 = aaaaaaaaabbbbbbbbb ? L2
It is “clear” that w1 is more complex than w2, actually. In otherwords, we may need a completely new method in measuring thecomplexity of a single word (herein, I am not interested inmeasuring the complexity of a languages as in (3)). Please suggesta way to measure the complexity of a word.

Answer rating: 100% (QA)

Answer Lets address each part of the problem step by step Program the robot for L1 Program for L1 wh... View the full answer