Assignment 3 -- Solution Q1 LI: a is the largest number in A[1..j-1] and b is the second largest number in this range. P(i): if there are at least i iterations then a_i is the largest number in A[1..j_i-1] and b_i is the second largest number in this range. To verify P(0) we need to notice that before entering the loop, a = a_0 is the largest of value between the first two elements of A, (namely A[1] and A[2]) and b is the second largest. Since j_0-1 = 2 this proves P(0). P(i) -> P(i+1): Notice that the j_{i+1} = j_i + 1, and also that the j in the first 4 lines of the loop in the i'th iteration is j_i-1. Hence, the value that is examined is in the i+1 st iteration is A[j_i]. If this vlue is largest than a_i than a_{i+1} is the value, and b_{i+1} becomes a_i, which means that the first two elements of the rang A[1...j_{i+1}-1] = A[1...j_i] is _{i+1},b_{i+1} as required. If the new value A[j_i] is bigger than b_i but smaller than a_i than b__{i+1} becomes A[j_i] and a_{i+1} = a_i, which still makes a_{i+1}, b_{i+1} the two biggest elelments. In the last case, A[j_i] is smaller than both a_j and b_j, and then we keep a_{j_i+1} = a_{j_i} and b_{j_i+1} = b_{j_i} which again shows that P(i+1) holds. We conclude that P(i) always hold. Since we return b we indeed return the second largest element. termintion: straight forward. length(A) - j_i decreses until is negative. s================================================================================ Q2 (a) Consider the string x = 01101, which has an odd number (three) of ones. String x is the concatenation of u = 01 and v = 101, where u is a concatenation of one 01, hence in L(01)*, and v is a concatenation of one 101, and hence in L(101)*, so x = uv is an element of L(01)*L(101)*, and x doesn't have an even number of 1s. So the regular expression (01)*(101)* doesn't denote L. (b) Consider an arbitrary x in L(0+(10*1))*. Then x is the concatenation of k strings from L(0+(10*1)), for some natural number k. Each of these substrings contains either 0 or 2 1s, so x contains some multiple of 2 1s, and is an element of L. Thus, L(0+(10*1))* is a subset of L. Now consider an arbitrary x in L, with an even number of 1s. Suppose x contains 2k 1s, for some natural number k. Then x is the contenation of u_1, ..., u_k, w, where each u_i consists of the substring following the (2i-2)th 1 (or the beginning of x if i=0), up to and including the 2ith 1, and w is a suffix consisting of zero or more 0s. Then each u_i is an element of L(0+(10*1))*, concatenating a prefix of zero or more 0s with the substring of the form 10*1, from the (2i-1)th 1 to the 2ith 1. Also, w is an element of L(0+(10*1))*, since it is the concatenation of zero or more 0s. Thus the concatenation of u_i, ..., u_k, w = x is an element of (L(0+(10*1))*)* = L(0+(10*1))*, and L is a subset of L(0+(10*1))*. Since they are subsets of each other, L(0+(10*1))* = L. (c) Consider x = 1010, which has an even number of 1s, and is hence in L. If x were in L(0*(10*1))*, then it would consist of one concatenation of 0*(10*1), since it has exactly two 1s. But in that case, x would end with a 1, a contradiction. So, the regular expression (0*(10*1))* doesn't denote L. (d) Consider an arbitrary x in L(0*(10*1)*)*. Then x is the concatenation of k strings from L(0*(10*1)*), where k is some natural number. Each of these substrings is comprised of a prefix of zero or more 0s, contributed by L(0)*, concatenated with j_k strings from L(10*1), contributing 2*j_k 1s. Thus, the sum of the number of 1s in x is a multiple of 2, so x is in L, and L(0*(10*1)*)* is a subset of L. Now consider an arbitrary string x, with an even number of 1s. Suppose x contains 2k 1s, from some natural number k. Then x is the concatenation of u_1, ..., u_k, w, where each u_i consists of the substring ending in the 2ith 1, and beginning just after the (2i-2)th 1 (or the first character of x, in the case of i=1), and w is a suffix of zero or more 0s. Then each u_i is in L(0*(10*1)), a subset of L(0*(10*1)*). Also, w is in L(0*(10*1)*), by concatenating zero or more zeros from L(0*) and zero strings from L(10*1). Thus, the concatenation of u_1, ..., u_k, w = x is in L(0*(10*1)*)*, and L is a subset of L(0*(10*1)*)*. Since they are subsets of each other, L = L(0*(10*1)*)*. ================================================================================ Q3 Proof (structural induction on definition of regular expressions without Kleene stars --- that is, the smallest set that obeys the basis of the definition of regular expressions, and the induction step without the Kleene star operation). Basis: The regular expressions \emptyset, \epsilon, and a (where a is a symbol in the alphabet) denote languages with 0 or 1 strings each, and are thus finite. So, the basis of regular languages that don't have Kleene stars denote finite languages. Induction step: Suppose R1 and R2 are two regular expressions that do not contain Kleene stars, and that they denote finite languages L(R1) and L(R2). Then (R1+R2) denotes the union L(R1) u L(R2), and has no more elements than |L(R1)| + |L(R2)|, and the sum of finite numbers is finite. Also, (R1R2) denotes the concatenation L(R1)L(R2), and has no more elements than |L(R1)| x |L(R2)|, and the product of finite numbers is finite. Thus, both (R1+R2) and (R1R2) denote finite languages. I conclude that all regular expressions that do not include the Kleene star denote finite languages. ================================================================================ Q4 a) In class we discussed how to find a DFSA that accepts the L= {x: x contains 011}. There is a smll modification that is needed to get a machine that accepts precisely the complement of L1, which is {x: x doesn't contain 101} and then, by changing accepting states to nonaccpting ones and vice versa we get the desired machine which accepts L1. b) Another way to describe L2 is L2 = {z: first character in z is zero} U {z: |z| is even} Why is this the case? If z=0z' we can present z as xy with x=0 y=z' or x=eps y=z. one of these will have y with even length. if z starts with 1 it will be in L2 exactly when z is of even size. Now the DFSA will simply have a transition from q_0 to an accepting state q_1 if the character is 0, and the transition fro q_1 will lead back to it. q_0, upon receiving 1 will go to q_2, and then move (regardless of the character) beteen q_3 and q_2. Being in q_2 means odd length and q_3 even length as it tkes one character to get to q_2, and then every character changes between q_2 to q_3. We make q_3 be the second accepting to get the desired DFSA.