CS20a HW2 Solutions Exercise 1. The mealy machine is: (1,0)/0 (0,1)/0 (1,1)/1 (1,1)/0 no carry carry (0,0)/1 (0,0)/0 (1,0)/1 (0,1)/1 Exercise 2. To prove that a language is not regular, we need to apply the first pumping lemma. Let us start by defining the first pumping property of length k: Let k ∈ N and L be a language. Then a string w ∈ L has the first pumping property of length k iff ∃x, y, z (not necessarily in L) such that w = xyz, | xy |≤ k, | y |≥ 1 and xy n z ∈ L for all n ≥ 0. Using this definition, we can state the first pumping lemma as: Let L be a regular language. Then for some k ∈ N, every w ∈ L with | w |≥ k has the first pumping property of length k. We can write the equivalent contrapositive form as: If for all k ∈ N, ∃w ∈ L that fails the pumping property of length k, then L is not regular. – {0m 1n 0m+n | n ≥ 1 ∧ m ≥ 1} is not regular. For any k and | w |≥ k we split w ∈ L into xyz s.t. x = , y = 0m , and z = 1n 0m+n . This clearly satisfies | xy |≤ k, | y |≥ 1. However, if we “pump" y (e.g. xy 2 z), then w = xyz ∉ L since the number of zeros in z will be less than what it should be. Therefore, L fails the contrapositive of the first pumping lemma and we conclude that it is not regular. The set of all strings that do not have 3 consecutive 0’s is regular. If we let a = Σ − {0}, then the regular expression for the language is: (0 + 00 + a∗ ) + (a(0 + 00)a∗ ) + (a∗ (0 + 00)a)∗ {xwx R | x, w ∈ (0 + 1)+ } is regular. Because we can make w arbitrarily long, we can WLOG set it equal to all the letters in xwx R except for the first and last. Thus the language is equivalent to {0w0 + 1w1 | w ∈ (0 + 1)+ } which is the language of all strings of length 3 or greater whose first and last letters are the same. A regular expression for this language is: 0(0 + 1)+ 0 + 1(0 + 1)+ 1 {xx R w | x, w ∈ (0 + 1)+ } is not regular. To prove we split w ∈ L, | w |≥ k for any k ∈ N into xyz such that | xy |≤ k, and | y |≥ 1. We let | xy |= 2 and | y |= 1. Thus, y must be a letter in either x or x R . If we now pump y to give xy n z, then clearly the substring xx R becomes unbalanced for any n 6= 2i, i ∈ N if y is the first letter of x R or the last of x and for n 6= 1 if y is not on the boundary. Thus the contrapositive of the first pumping lemma is not satisfied and L is not regular. Exercise 3. If L is finite then L∗ must be regular since we can construct a regular expression to match it. To do so, just build a RE for each element of L and take the union of their Kleene closures. If L is infinite, then our task is harder. We begin by noting that, since the alphabet of L has only one letter, there is an injection from elements of L∗ to N. Let M = {|x|, x ∈ L}, and let M ∗ = {|x|, x ∈ L∗ }. Concatenation of two strings in L corresponds to addition of their images in M, and thus M ∗ is the set of all integers m that can be written as: m= ∞ X ci mi , ci ∈ N, mi ∈ M i=1 Assuming the greatest common devisor (gcd) g of M is well-defined, it is clear that all elements of M ∗ are multiples of the gcd. Also, any multiple of the gcd is a linear combination of numbers in M with (possibly negative) integer coefficients. We would like to prove that for large enough multiples of the gcd we can always find non-negative coefficients. Doing so will tell us that for some integer f , we can write a regular expression for L∗ as 0f (0g )∗ unioned with a finite number of strings of length less than f . First we prove that the GCD of an infinite set always exists: Let S = {s1 , s2 , s3 , ...} and consider a finite S 0 ⊆ S = {s10 , s20 , s30 , ..., sk0 }. Let g = GCD(S 0 ). If we start increasing the size of S 0 , then either the g will remain the same or it will go down. Since g is bounded below by 1, the GCD of an infinite set always exists. Let M = {m1 , m2 , ...} with mi < mj whenever i < j. Next we need to find f , such that ∀k ∈ N, f + kg = n X i=1 , with all ci ≥ 0. ci mi Let S = {m1 , m2 , ..., mn } be a subset of M such that GCD(S) = GCD(M), and let g be that GCD. We Pn Pn know that g = i=1 ci mi , ci ∈ Z. Let f = m1 i=1 |ci |mi . Clearly all coefficients can be non-negative in f + kg if k < m1 , since in this case ∀i, m1 |ci | + kci > 0. Furthermore, every number f + kg with k any element in N can be written as f + kg = (f + (k − pm 1 )g) + pm1 g, where k − pm1 < m1 and p ∈ N. We just showed that the first term can be written as a non-negative linear combination of elements in S, and the second term is clearly a non-negative multiple of a1 , so we have proven that f satisfies our requirement, and that every multiple of g greater than f is in M ∗ . Consequently, we have shown that L∗ is regular. Exercise 4. Let M = (Q, Σ, δ, q0 , F ) be a DFA that implements L. HALF(L) Construct a new machine M 0 for HALF (L). Essentially, within HALF (L), we record the state that the input string leads us to in |w| moves, as well as the set of states that can be reached by taking |w| backward moves from any final state. Given a set of states S, the function B(S) computes the states that can move to any state in S in one move. Let M 0 = (Q × 2Q , Σ, δ0 , [q0 , F ], F 0 ), where B(S) = {q | ∃a ∈ Σ, t ∈ S.δ(q, a) = t} F0 = {[q, S] | q ∈ S} δ([q, S], a) = [δ(q, a), B(S)] SQUARE(L) LOG(L) For the log machine, we produce a similar construction, but we have to keep track of more states. Given a DFA M = (Q, Σ, δ, s, F ) that implements L, let Q = {q1 , . . . , qn }. We construct M 0 = (Q × (2Q )n , Σ, δ0 , s 0 , F 0 ), where B(S) = {q | ∃a ∈ Σ.δ(q, a) ∈ S} s0 = [s, B({q1 }), . . . , B({qn })] 0 = {[q, S1 , . . . , Sn ] | ∃i.qi ∈ F ∧ q ∈ Si } [ [ Sn ] Si , . . . , δ ([q, S1 , . . . , Sn ], a) = [δ(q, a), F 0 qi ∈Sn qi ∈S1 We claim that L(M 0 ) = LOG(L). Next, we prove the following by induction on k: k k δ0 ([s, B({q1 }), . . . , B({qn })], x) = [δ(s, x), B 2 ({q1 }), . . . , B 2 ({qn })] Base This is clearly true for k = 0. Step Next, assume the equation is true for k, and show it is true for k + 1. δ0 ([s, B({{q1 }), . . . , B({qn })], xa) = δ0 (δ0 ([s, B({{q1 }), . . . , B({qn })], x), a) = k k δ0 ([δ(s, x), B 2 ({q1 }), . . . , B 2 ({qn })], a) Now we have to show that for j ∈ {1, . . . , n}, [ k k+1 A= B 2 ({qi }) = B 2 ({qi }) k qi ∈B 2 ({qj }) k Well, if q ∈ A, then ∃i with qi ∈ Sj and q ∈ B 2 ({qi }). So, ∃α, β ∈ Σ∗ with |α| = |β| = 2k , δ(q, α) ∈ {qi }, and δ(qi , β) ∈ {qj }, Hence δ(q, αβ) = qj , For the reverse direction, if q ∈ B 2 k+1 ({qi }), then ∃ϕ with |ϕ| = 2k+1 and δ(q, ϕ) = qj , Let α, β be k k of length 2k where αβ = ϕ. Then qi = δ(q, α) ∈ B 2 ({qj }), So B 2 ({qi }) ⊂ A. Finally, suppose x ∈ LOG(L), and choose y so that xy ∈ L. Then δ(s, xy) = q f for some qf ∈ F , and δ(s, x) ∈ B 2 δ(s, x) ∈ B 2|x| |x| ({qf }) when M 0 accepts x. Conversely, the x ∈ L(M 0 ), then ({qf }) for some qf ∈ F , and so y exists. Exercise 5. We know that: xRy ⇒ wxzRwyz for all w and z. Define [x] = {y | xRy}. If R is a congruence relation of a finite index, then there are a finite number of congruence classes [x 1 ], [x2 ], ..., [xn ]. If we let S = [x1 ] ∪ [x2 ] ∪ ... ∪ [xk ] where k ≤ n (we can arbitrarily select which [x]’s are in the first k, then all we need to show is that S is regular a S = L(MS ) for some DFA MS . Define MS as: Q = {[x] | x ∈ Σ∗ } Σ = any finite alphabet δ([x], a) = [xa] S = {[]} F = {[x] | x ∈ S} Since xRy ⇒ xaRya ⇒ [xa] = [ya] ⇒ δ(x, a) = δ(y, a), δ is well defined. δ̂([x], y) = [xy] can be proved by induction on the length of y: Base case: δ̂([x], ) = [x] = [x] Inductive Hypothesis: δ̂([x], y) = [x, y] Inductive Step: δ̂([x], ya) = δ(δ̂([x], y), a) = δ([xy], a) = [xya]. Using the last property we can write: x ∈ L(MS ) a δ̂([], x) ∈ F a [x] ∈ F a x ∈ S. Since L(MS ) is regular, all x ∈ L(MS ) are regular so all x ∈ S are regular.