COMP3803 - Introduction to Theory of Computation
COMP3803 � Introduction to Theory of Computation Midterm Exam February 27, 2020 Name: Student Number: Problem 1. [10 points] Let Σ = {[ a b ] : a, b ∈ {0, 1} } . A string w ∈ Σ∗ can then be understood as encoding two natural numbers in binary notation. More precisely, if w = 0∏ i=n−1 [ ai bi ] = [ an−1 bn−1 ] · · · [ a0 b0 ] , then the numbers encoded are n−1∑ i=0 2iai and n−1∑ i=0 2ibi. Consider the language LESS = { 0∏ i=n−1 [ ai bi ] : n−1∑ i=0 2iai < n−1∑="" i="0" 2ibi="" }="" .="" draw="" a="" diagram="" describing="" a="" dfa="" that="" recognizes="" less.="" solution:="">< q=""> [ 0 1 ] [ 1 0 ] [ 0 0 ] , [ 0 1 ] , [ 1 0 ] , [ 1 1 ][ 0 0 ] , [ 0 1 ] , [ 1 0 ] , [ 1 1 ] [ 0 0 ] , [ 1 1 ] 1 Problem 2. [30 points] Let Σ be an alphabet. A proper pre�x of a string w ∈ Σ∗ is a string x ∈ Σ∗ for which there exists a non-empty string y ∈ Σ∗ \ {ε} such that xy = w. Similarly, a proper su�x of a string w ∈ Σ∗ is a string y ∈ Σ∗ for which there is a non-empty string x ∈ Σ∗ \ {ε} such that xy = w. Given an arbitrary DFA M = (Q,Σ, δ, q0, F ), construct a DFA M ′ = (Q′,Σ, δ′, q′0, F ′) by formally de�ning Q′, δ′, q′0 and F ′ in such a way that L(M ′) = {w ∈ L(M) : no proper pre�x of w is in L(M)}. Construct also a DFA M ′′ = (Q′′,Σ, δ′′, q′′0 , F ′′) by formally de�ning Q′′, δ′′, q′′0 and F ′′ in such a way that L(M ′′) = {w ∈ L(M) : w is not a proper pre�x of any string in L(M)}. Let A be a regular language. Is it always true that {w ∈ A : no proper su�x of w is in A} is regular? Prove that your answer is correct. Solution: To de�ne M ′, let Q′ = Q ∪ {⊥} (where ⊥ /∈ Q), q′0 = q0, F ′ = F and δ′ : Q′ × Σ → Q′ (q, a) 7→ { ⊥, q ∈ F ∪ {⊥} δ(q, a), otherwise. To de�ne M ′′, let Q′′ = Q, q′′0 = q0, δ ′′ = δ and F ′′ = { f ∈ F : @w ∈ Σ∗ \ {ε} : δ(f, w) ∈ F } . We will show that the language is indeed regular whenever A is regular. First, however, note that whenever x ∈ Σ∗ is a proper su�x of w ∈ Σ∗ \ {ε}, x> is a proper pre�x of w> and vice-versa (recall Assignment 2 Problem 1). Therefore, we have {w ∈ A : no proper su�x of w is in A} = {w ∈ A : @x ∈ A : x is a proper su�x of w} = {w ∈ A : @x ∈ A : x> is a proper pre�x of w>} = {w ∈ A> : @x ∈ A> : x is a proper pre�x of w} = {w ∈ A> : no proper pre�x of w is in A>}, which, from the �rst item and our knowledge that A> is regular, is a regular language. 2 3 Problem 3. [20 points] LetA be a language over an alphabet Σ. De�neA+ = {xay : x, y ∈ Σ∗, a ∈ Σ and xy ∈ A}, i.e., A+ is the language of strings that can be obtained by inserting a character into a string in A. Is A+ guaranteed to be regular whenever A is regular? Prove that your answer is correct. Less detailed solution, part A: Let A and B be two languages. As to insert a character in a string from A ∪B we can either insert a character in a string from A or in a string from B, we have (A ∪B)+ = A+ ∪B+. Similarly, to insert a character in a string from AB, we can put the character in the part from A or in the part from B, so we have (AB)+ = A+B ∪AB+. Finally, to insert a character in a string from A∗ we need to insert it in one of the parts from A, so (A∗)+ = A ∗A+A ∗. More detailed solution, part A: Let A and B be languages. We have (A ∪B)+ = {xay : x, y ∈ Σ∗, a ∈ Σ, xy ∈ A ∪B} = {xay : x, y ∈ Σ∗, a ∈ Σ, xy ∈ A} ∪ {xay : x, y ∈ Σ∗, a ∈ Σ, xy ∈ B} = A+ ∪B+. Next note that whenever x, y ∈ Σ∗ and xy ∈ AB, there is a pre�x of x in A or a su�x of y in B, so (AB)+ = {xay : x, y ∈ Σ∗, a ∈ Σ, xy ∈ AB} = {wxay : w ∈ A, x, y ∈ Σ∗, a ∈ Σ, xy ∈ B} ∪ {xayw : w ∈ B, x, y ∈ Σ∗, a ∈ Σ, xy ∈ A} = AB+ ∪A+B. Let us now show that (A∗)+ = A ∗A+A ∗. First, take a string w ∈ A∗A+A∗, which, by de�nition, can be written as w0 · · ·wm−1xayw′0 · · ·w′n−1 with w0, . . . , wm−1, w′0, . . . , w′n−1 ∈ A \ {ε}, x, y ∈ Σ∗, a ∈ Σ and xy ∈ A. Then w0 · · ·wm−1xyw′0 · · ·w′n−1 ∈ A∗, so w ∈ (A∗)+. Next, to show the other inclusion, take a string w ∈ A∗, which, by de�nition, can be written as w0 · · ·wn−1 with w0, . . . , wn−1 ∈ A \ {ε}. If x, y ∈ Σ∗ satisfy xy = w, then there must be an i ∈ {0, . . . , n − 1} and strings x′, y′ ∈ Σ∗ such that x = w0 · · ·wi−1x′, y = y′wi+1 · · ·wn−1 and x′y′ = wi. Then xay = w0 · · ·wi−1x′ay′wi+1 · · ·wn−1 ∈ A∗A+A∗. Solution, part B: As every regular language can be described by a regular expression, it is enough to show that every regular expression R has a regular expression R+ such that L(R+) = L(R)+ (note: R+ is just notation). We prove this by induction on R considering all possible cases of R's de�nition: • R = � or R = w ∈ Σ∗: L(R) is �nite and so is then L(R)+, so we construct R+ as a disjunction of the strings in L(R)+; • R = R0|R1: by the induction hypothesis, there are regular expressions R0+ and R1+ such that L(R0+) = L(R0)+ and L(R1+) = L(R1)+. We then let R+ = R0+|R1+ so we have L(R+) = L(R0+) ∪ L(R1+) = L(R0)+ ∪ L(R1)+ = (L(R0) ∪ L(R1))+ = L(R)+; • R = R0R1: similarly to the �rst case, we obtain from the induction hypothesis two regular expressions R0+ and R1+ such that L(R0+) = L(R0)+ and L(R1+) = L(R1)+. We then let R+ = R0+R1|R0R1+, which gives us L(R+) = L(R0+)L(R1) ∪ L(R0)L(R1+) = L(R0)+L(R1) ∪ L(R0)L(R1)+ = (L(R0)L(R1))+ = L(R)+; • R = R∗0: again we use the induction hypothesis, this time obtaining a regular expression R0+ with L(R0+) = L(R0)+. Here we let R+ = R ∗ 0R0+R ∗ 0 since then L(R+) = L(R0) ∗L(R0+)L(R0) ∗ = L(R0) ∗L(R0)+L(R0) ∗ = (L(R0) ∗)+ = (L(R ∗ 0))+ = L(R)+. 4 Problem 4. [10 points] Show a context-free grammar describing the language {0a1b0a+b : a, b ∈ N}. Solution: S → 0S0 | X X → ε | 1X0 5 Problem 5. [15 points] Prove that the language {x#y : x, y ∈ {0, 1}∗ and x 6= y} over the alphabet {0, 1,#} is not regular and show a context-free grammar describing it. Solution: If the language were regular, there would be a DFA M = (Q, {0, 1,#}, δ, q0, F ) recognizing it. De�ne qi = δ(q0, 0 i) for all i ∈ N (note that this agrees with q0). Let now i, j ∈ N with i 6= j. Since 0i#0i is not in the language but 0j#0i is, we have that δ(qi,#1 i) /∈ F but δ(qj ,#1i) ∈ F , so qi 6= qj . Therefore Q is an in�nite set, a contradiction. Let us write a context-free grammar to describe the language (the textual description is just commentary). We start by introducing a variable X that derives all strings in {0, 1}∗: X → ε | 0X | 1X Next let us introduce a variable A that derives zeroes and ones: A → 0 | 1 If x, y ∈ {0, 1}∗ and x 6= y, at least one of the three cases below occurs: • |x| < |y|;="" •="" |x|=""> |y|; or • There is a natural number k < min="" {="" |x|,="" |y|="" }="" such="" that="" the="" characters="" at="" (0-based)="" index="" k="" in="" x="" and="" y="" di�er.="" let="" us="" introduce="" a="" variable="" l="" that="" derives="" am#an="" with="" m="">< n="" to="" handle="" the="" �rst="" case:="" l="" →="" l′a="" l′="" →="" #="" |="" l′a="" |="" al′a="" similarly,="" we="" introduce="" a="" variable="" r="" that="" derives="" am#an="" with="" m=""> n to handle the second case: R → AR′ R′ → # | AR′ | AR′A In the third case, for some k ∈ N, x ∈ Σk{0}Σ∗ and y ∈ Σk{1}Σ∗ or vice-versa. Let us introduce a variable S0 that derives strings of the form Ak0X#Ak1X: S0 → S′01X S′0 → 0X# | AS′0A We then introduce a variable S1 to derive A k1X#Ak0X: S1 → S′10X S′1 → 1X# | AS′1A To close it o�, we introduce the starting symbol branching into all of the cases: S → L | R | S0 | S1 6 Problem 6. [15 points] Prove that the language {xy : x, y ∈ {0, 1}∗, |x| = |y| but x 6= y} is not regular and show a context-free grammar describing it. Solution: Similar to the previous one. If the language were regular, there would be a DFAM = (Q, {0, 1}, δ, q0, F ) recognizing it. De�ne qi = δ(q0, 0 i) for all i ∈ N (note that this agrees with q0). Let now