=========================================================================== CSC 363 Homework Assignment 1 -- Sample Solutions Winter 2008 =========================================================================== 1. High-level description: Print the empty string, then write 101 on the tape and print it, then repeatedly add 101 to the binary integer on the tape and print it. Implementation-level description: 1. Start in the print state (this prints the empty string, from configuration "q_P _"). After printing, we must either add 5 to the binary integer on the tape, or write 5 on the tape (to get things started). To tell the difference between this first stage and subsequent stages, later stages will ensure the head is always on the rightmost nonblank square when we reach the print state. 2. Write 101 on the tape, preceded by a single blank square (to be able to tell the left edge), and print it (with the head on the rightmost bit, i.e., in configuration "_10 q_P 1"). 3. (At this point, the tape contains one blank followed by a binary integer, with the head on the rightmost non-blank square, and the TM is in the print state.) Add 1 to the current bit, move left and go to different states to indicate the presence or absence of a carry. 4. Add 0 and the current carry to the current bit, move left and go to different states to indicate the presence or absence of a carry. 5. Add 1 and the current carry to the current bit, move left and go to different states to indicate the presence or absence of a carry. 6. As long as there is still a carry, continue moving left and adding the carry -- this only happens as long as the current bit is 1. 7. If the head reads a blank, then there was a carry into a new bit position: shift the entire tape content one square right, preceded by a new 1 (leaving the first blank intact). 8. Move the head to the rightmost non-blank square and go back to stage 3 in the print state. Formal-level description: Q = {P,W_4,W_2,W_1,A_0,A_1,B_0,B_1,C,E,S_0,S_1,ACC,REJ} initial state = P; print state = P; accept state = ACC; reject state = REJ \Sigma = {0,1} \Gamma = {_,0,1} \delta is given by the table below -- superfluous transitions (that can never be encountered by design) are entirely blank _ 0 1 # purpose/comment P W_4,_,R A_0,1,L A_1,0,L # add low-order 1 / write 101 W_4 W_2,1,R # write high-order 1 W_2 W_1,0,R # write middle 0 W_1 E ,1,R # write low-order 1 A_0 B_0,0,L B_0,1,L # add 0 without carry A_1 B_0,1,L B_1,0,L # add 0 with carry B_0 E ,1,R C ,0,L # add 1 without carry B_1 C ,0,L C ,1,L # add 1 with carry C S_1,_,R E ,1,R C ,0,L # add 1 (carry) S_0 E ,0,R S_0,0,R S_1,0,R # shift 0 right S_1 E ,1,R S_0,1,R S_1,1,R # shift 1 right E P ,_,L E ,0,R E ,1,R # move to rightmost bit Simplifications -- it was *not* necessary to do this; showing it for the sake of curiosity: - Transitions identical for states B_0 and C (except for transition on _, which does not matter for B_0), which makes sense (adding 1 is adding 1, whether from carry or otherwise), so merge states. - Transitions become identical for states A_0 and B_1, which makes sense (in both cases, we are adding "10"), so merge both states. - Rather than having separate states to write initial "101", fill in "unused" transitions from A_0 and A_1 on _, and eliminate state W_1 (its transition on _ is identical to S_1). - Result is below, with new meaning associated with each state. Q = {P,A_1,A_0,C,E,S_1,S_0,ACC,REJ} initial state = P; print state = P; accept state = ACC; reject state = REJ \Sigma = {0,1} \Gamma = {_,0,1} \delta is given by the table below -- no superfluous transition _ 0 1 # purpose/comment P A_1,_,R A_0,1,L A_1,0,L # add 101 / write 101 A_1 A_0,1,R C ,1,L A_0,0,L # add 11 / write first 1 A_0 S_1,0,R C ,0,L C ,1,L # add 10 / write first 0 C S_1,_,R E ,1,R C ,0,L # add 1 (carry) S_1 E ,1,R S_0,1,R S_1,1,R # shift 1 right / write last 1 S_0 E ,0,R S_0,0,R S_1,0,R # shift 0 right E P ,_,L E ,0,R E ,1,R # move to rightmost bit 2. Theorem: Right-bound TMs (RBTMs) are equivalent to FSAs. Proof: We must prove the equivalence in both directions. => Let A be a FSA with input alphabet \Sigma = {a_1,a_2,...,a_m}, states Q = {q_1,q_2,...,q_n}, initial state q_1, final (accepting) states F (_ Q, and transition function \delta. Consider the RBTM M_A with input alphabet \Sigma, tape alphabet \Gamma = \Sigma U {_}, states Q' = Q U {ACC,REJ}, initial state q_1, and transition function \delta' defined as follows: \delta'(q_i,a_k) = (\delta(q_i,a_k),a_k,R) for all q_i (- Q, a_k (- \Sigma \delta'(q_i,_) = (ACC,_,L) for all q_i (- F \delta'(q_i,_) = (REJ,_,L) for all q_i (- Q - F Each string accepted by A is also accepted by M_A and each string rejected by A is also rejected by M_A, so L(M_A) = L(A). => Let M be a RBTM with input alphabet \Sigma = {a_1,a_2,...,a_m}, tape alphabet \Gamma = \Sigma U {_,b_1,b_2,...,b_s}, states Q = {q_1,q_2,...,q_n,q_A,q_R}, initial state q_1, accepting state q_A, rejecting state q_R, and transition function \delta. Idea: Create a FSA A_M with the same states as M (including the accept and reject states q_A, q_R), with q_A the only final state (initially), and with alphabet \Sigma. Each transition of M (q,a) -> (q',a',R) becomes (q,a) -> q' in A_M. Each transition of M (q,a) -> (q',a',S) must be traced through M's transition table (i.e., follow more transitions (q,a) -> (q_1,a_1,S) -> ...) until one of the following happens: - we reach a transition moving right: ... -> (q',a',R), in which case set transition (q,a) -> q' in A_M; - we reach the accepting state of M: ... -> (q_A,...), in which case set transition (q,a) -> q_A in A_M; - we reach the rejecting state of M: ... -> (q_R,...), in which case set transition (q,a) -> q_R in A_M; - we repeat a state and symbol that have been encountered before, i.e., there is a loop (q,a) -> ... -> (q_s,a_s,S) -> ... -> (q_t,a_t,S) -> (q_s,a_s,S) -> ..., in which case set transition (q,a) -> q_R in A_M. Note that exactly one of these cases must happen, because there are a fixed, finite number of combinations (q,a) in the transition table of M. Unlike a TM, states q_A and q_R have no special meaning in a FSA, so add transitions (q_A,a) -> q_A and (q_R,a) -> q_R for all symbols a (- \Sigma -- once a string is accepted/rejected by M, it remains that way in A_M. There is one last issue to deal with: if M reaches the blank portion of the tape. The problem is that the blank symbol is *not* part of the input string, so we cannot simply add transitions to A_M on symbol '_'. The trick is to make more states of A_M final (accepting), as follows: for each state q, trace through the transitions of M starting from (q,_), until one of the following happens (exaclty one must, as above): - M reaches its accepting state q_A, in which case add q to the set of final states; - M reaches its rejecting state q_R or M loops, either as before (by staying put on some (q,a) that's been encountered before), or by getting back to a state previously encountered while reading a blank (since blanks are the only symbols that can be encountered on the tape once the first blank has been reached), in which case leave q out of the set of final states. By design, A_M will accept exactly the strings that M accepts, and will reject every string that M rejects or loops on. Corollary: RBTMs are not equivalent to TMs; they are strictly weaker, since FSAs are strictly weaker than TMs -- TMs can recognize every regular language and also some non-regular languages, such as { 0^n 1^n : n (- N }. 3. "k-head" TMs (kHTMs) are equivalent to TMs. => Let M be a TM with tape alphabet \Gamma, state set Q, and transition function \delta, and consider the kHTM M' with the same alphabets and states as M but with transition function \delta' defined as follows, for all q (- Q, a_1,...,a_k (- \Gamma, and where \delta(q,a_1) = (q',b,d): \delta'(q,a_1,...,a_k) = (q',b,d,b,d,...,b,d) i.e., M' simulates M by keeping every head on the same square. Then, clearly, L(M') = L(M) -- M' accepts/rejects/loops on its input exactly when M accepts/rejects/loops on the same input. <= Let M be a kHTM with tape alphabet \Gamma, state set Q, and transition function \delta. Idea: Create a TM M' by replacing each symbol a (- \Gamma with 2^k symbols, one for each possible subset of {1,2,...,k} -- symbol a^S represents tape square that contains symbol a and each of the heads in S, e.g., a^{} is tape square with no heads, a^{1,3,5} is tape square with heads number 1, 3, and 5, etc. Each transition of M is replaced by two sweeps of the tape in M': one to read the symbols under each head (using a large number of different states in M' to "remember" each head's symbol), the second to update the tape and "move" the heads (again, using a large number of states to keep track of the fixed, finite amount of information necessary), all according to the transition table of M. By design, behaviour of M' on any input is identical to behaviour of M on same input (accept/reject/loop). 4. Let L be a finite language, i.e., L = {s_1,s_2,...,s_m} for some strings s_1,...,s_m (- \Sigma*. Then there is a TM whose behaviour is to check whether the input is equal to s_1 or s_2 or ... or s_m, one after the other: the TM has one state for each symbol of s_1, one state for each symbol of s_2, ..., and one state for each symbol of s_m, with extra states at the beginning to shift the input one square to the right (to leave a blank square on the left) and more extra states to move the head back to the leftmost input square in between each scan of the tape. The TM accepts if its input is exactly equal to any one of the strings; otherwise, once each string has been checked, the TM rejects. This TM is a decider: by construction, it always halts. And it accepts exactly the strings s_1, s_2, ..., s_m but no others, i.e., it decides language L. Hence, every finite language is decidable.