CS–172 Computability & Complexity, Spring 2009February 10, 2009Homework 1 SolutionsNote: These solutions are not necessarily model answers. Rather, they are designed to be tutorial in nature,and sometimes contain a little more explanation than an ideal solution. Also, bear in mind that there maybe more than one correct solution. The maximum total number of points available is 32.1. DFAs for these three languages are as follows:(a) The set of all 0-1 strings that begin with 0 and end with 1. 3pts1001010,1(b) The set of all words over the English alphabet whose third-last letter is ‘b’. In the machine below, 3ptseach state “remembers” the sequence of the last three symbols seen, distinguishing only between ‘b’and non-‘b’ letters; thus it has eight states (corresponding to all 3-letter strings over an alphabet of twoletters). Here Σ denotes the English alphabet.Σ−bΣ−bΣ−bΣ−bΣ−bΣ−bΣ−bΣ−bbbbbbbbb(c) The set of all 0-1 strings that contain at least two 0’s and at most one 1. In the machine below, the 3ptsstate shifts one place to the right for each 0, and one place down for each 1, stopping when the countsreach 2. It accepts if the first count reaches 2 and the second does not.1 1 11 110 000000,12. As suggested in the Hint, we describe the sets of input strings w that cause the DFA to end in each of the 5ptsstates (starting from the initial state q0):• state q0: all strings w in which every 0 is followed by a 1;• state q1: all strings w that end in 0 in which every other 0 is followed by a 1;• state q2: all strings w with a pair of consecutive 0’s.Note that these definitions cover all possible input strings, so all we have to do to show the correctness ofthe DFA is prove that if we run the DFA on a string w then it will terminate in state qiif w satisfies theproperty ascribed to qiabove. (If some input strings were not covered, then we would have to prove the onlyif direction as well, as it might be possible for the DFA to accept more strings than we claim it does.)The proof is by induction on the length of the input string w.Base case: |w| = 0, that is, w = ǫ (the empty string). The DFA terminates in state q0, whose property issatisfied by the empty string: there are no 0’s that are not followed by a 1. The definitions for the other twostates are satisfied vacuously.Induction step: We make the induction hypothesis that our definitions hold for w′= {0, 1}nwith n ≥ 0;we now prove that they also hold for w = w′a with a ∈ {0, 1}. We consider the states in which the DFAmight have determined after processing w′:• state q0: If a = 0 then the DFA transitions to state q1. By the induction hypothesis every 0 in w′isfollowed by a 1; w′a now also ends in a 0 so the condition for q1is met. If a = 1 then the DFA staysin state q0. Again by the induction hypothesis every 0 in w′is followed by a 1; this remains true withthe addition of an extra 1.• state q1: If a = 0 then the DFA progresses to state q2. By the induction hypothesis w′ends in 0; theaddition of a gives the string a pair of consecutive 0’s, and so the condition for q2is met. If a = 1 thenthe DFA transitions back to state q0. As above, w′ends in 0 but otherwise has the properties of thestrings that end up in q0. Adding a 1 meets the requirement that every 0 in the whole string is followedby a 1, including the last 0.• state q2: By the induction hypothesis, w′already has a pair of consecutive 0’s, so any string containingw′will have this property; therefore the DFA stays in state q2as it should.We have now proved that the DFA will end up in state q2given any string w with a pair of consecutive 0’s.Since the other two states are accepting, the DFA accepts iff w does not contain a pair of consecutive 0’s.3. (a) Simply interchange the accepting and non-accepting states of M , but leave everything else unaltered. 2ptsI.e., if M = (Q, Σ, δ, q0, F ), then M′= (Q, Σ, δ, q0, Q − F ). Since δ is unchanged, we haveM accepts w ⇔ δ(q0, w) ∈ F⇔ δ(q0, w) /∈ Q − F⇔ M′does not accept w.(b) This construction does not work when M is nondeterministic. The reason is that, by our definition of 2ptsacceptance for NFAs, when M accepts only one, not all, of its computations has to be accepting. Thusin the above construction the modified machine M′could accept some of the same strings as M. Hereis a simple counterexample: both the automata below accept (for example) the string ‘0’.0,100,10M M’4. The following DFA shows the full construction. Note that if we pruned away states unreachable from the 4ptsstart state, the resulting DFA would be the same as in problem 1(a):2,31,2,31,21,33120 100,1011010100,1015. (a) An NFA for Lkis as shown. At each step, if it sees a 0 it “guesses” if this is in fact the kth last symbol 3ptsby going into state q1; from there, it verifies its guess by moving in exactly k − 1 more steps to thefinal state. This NFA has k + 1 states.0,10 0,1 0,1 0,1. . . . .q0 q1 q2 qk(b) We construct a DFA such that each of the states represents one of the 2kpossible length-k suffixes. 3ptsExactly half of these states, those representing suffixes that start with 0, are accepting states. (If astring ends up in one of the other states, the string must have had a 1 in the kth position from the end,and therefore must be rejected.) We transition from state to state by simply lopping off the first digitof the suffix and appending the next character to be read. (For instance, if k = 4 then one transition is(s1001, 0) → s0010.)Q = {sz: z ∈ {0, 1}k}Σ = {0, 1}δ = {(saw, b) → swb: a, b ∈ {0, 1}, w ∈ {0, 1}k−1}q0= s1kF = {sz: z starts with 0}Note the choice of initial state q0= s1k. This is in line with the fact that no zero has been seen whenthe computation begins.(c) Let Mkbe any DFA that accepts Lk. Let us call two strings x and y distinguishable by Lkif there is a 4ptsstring w such that exactly one of xw and yw is in Lk(i.e., either xw ∈ Lkand yw /∈ Lkor vice versa).The point about distinguishable strings is the following. We claim that for any pair of distinguishablestrings x and y, Mkmust end up in different states after processing x and y. We can prove this bycontradiction. Supose on the contrary that x and y are distinguishable but δ∗(q0, x) = δ∗(q0, y).1Then clearly for any symbol a we must have δ∗(q0, xa) = δ∗(q0, ya), and repeating, for any string wwe have δ∗(q0, xw) = δ∗(q0, yw).