Cpt S 317 Homework #0
Please print your name!
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 a’s;
L2, 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 conclude 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.
1
