4. There are two circles, let's call them L and R. You are standing in circle L. Someone calls out a string of letters, each of which is either a or b. Whenever you hear a you stay in or move to L. Whenever you hear b you move to the circle you are not standing in. Let S be the set of all finite strings containing only as and/or bs, which we'll consider to be defined structurally as follows: S (recall from a previous course that is often used to refer to the empty string). If se S then sa and sb are in S (recall from a previous course, and the lecture(s) on structurally-defined expressions, that we put two strings beside each other to mean concatenation, and usually leave out quotes for literal strings if there's no ambiguity). If you have any trouble with this question, do the following first. In particular, before asking about this question on the bulletin board or in office hours, make sure you have done this "warmup" first-and feel free to ask about it: Write out a good set of examples/test cases illustrating the kinds of elements that are in S. In particular, include boundary/extreme/special cases. There are an infinite number of elements, so as usual for example/test cases you want to illustrate the "variety" of possibilities. But what "variety" means can depend a lot on what you are doing with the elements of S so as you explore the problem consider whether to extend your set of illustrative elements. For each of your examples, determine which circle you end up in. (a) Give a brief non-recursive (i.e., it should not reference the character-by-character process) single- sentence English description to decide whether a string from S causes you to end up in circle L. (b) Prove, by Structural Induction on S, your claim from part (a). Depending on how you phrased your claim, adding something like and if not then it makes you end up in R (if that's not already explicit) will likely help.