(40 points) Give a predicate that exactly characterizes each of the following sets of strings. That is to say, your predicate should have a free variable (say w), and should hold if and only if w is instantiated to a string in the set. (a) Strings containing both 101 and 010. (b) Strings that contain 101 if they contain 10. (c) Strings that contain the substring 11 in two different ways. (So 111 is included, but 011 is not.) (d) Strings that contain at least four 1s. Reasoning About Strings This homework explores a logic over strings of the symbols 0 and 1. We define strings as either the empty string e, or as a (finite, but potentially arbitrarily long) series of Os and 1s. For example, the following are strings 0 0010 11111 10100100010000 We can also concatenate strings. If w and v are strings, we write their concatenation as wv. For example: 010^101 = 010101 010 = 010 01 0101 = 010101 101 = 101 To reason about strings, we have two atomic predicates. The first is string equality, written w = v. For example, the following predicates hold: 1010 = 1010 10 10 = 1010 Vw.w = w In contrast, the following predicates do not hold: 1010 = 0101 0101 = 101Vw.w = ww Our second atomic predicate is the substring predicate, written w [ v. The predicate w S v holds if w appears in order in v. For example, the following predicates hold: 01