CSC 456/656 Assignment 9, Answers, modified November 15, 2002.

Due date, November 12, 2002, 4:00 PM.

1. Prove that the set of all IDs of M is a regular language. (Be sure to tell me what the alphabet for that language is.)
   Let Gamma be the tape alphabet of M. L_id is the intersection of (Gamma + {B})*Q(Gamma + {B})* and (Gamma + {B} + Q)*(Gamma + Q), both of which are regular. The intersection of two regular languages is regular. Thus L_id is a regular language over the alphabet Gamma + Q + {B}.
2. A final ID is an ID whose state is in F. (See page 326 of your textbook.)
   Prove that the set of all final IDs of M is a regular language.
   L_id is the intersection of (Gamma + {B})*F(Gamma + {B})* and (Gamma + {B} + Q)*(Gamma + Q), both of which are regular.
3. An initial ID of M is an ID of the form q₀w where w is any string over Sigma and q₀ is the start state.
   Prove that the set of initial IDs of M is a regular language.
   L_iid = q₀Sigma*, which is regular.
4. If x and y are IDs of M, we say that y is the successor of x if, given that the ID of M is x at a given step, the ID at the next step will be y. Prove that L_notsuc, the set of all strings of the form x#y such that x and y are IDs of M and x is not the successor of y, is a context-free language.
   Recall that the union of any finite number of context-free languages is a context-free language, and that the intersection of a context-free language with a regular language is a context-free language.
   We define a padded ID of M to be a string of the form $x$$$ where x is an ID of M. ($ stands for blank. Padding a string allows the construction of the Li below to proceed more uniformly, by eliminating the need for special cases in the proof dealing with the ends of the ID.) L_padid = $L_id$$$ is also a regular language. If y is the successor of x, we say that $y$$$ is the successor of $x$$$. Let L_padnotsuc, be the set of all strings of the form u#v such u, v are padded IDs of M and v is not the successor of u. Then
   h(L_padnotsucc) = L_notsucc
   where h is the homomorphism that takes $ to the empty string and every other symbol to itself. We will prove that L_padnotsucc is context-free, hence we will have that L_notsucc
   is context-free.
   Let L_2padid be the language of all strings of the form u#v such that x and y are padded IDs of M. Then L_2padid = L_padid#L_padid, which is regular, since it is the concatenation of regular languages.
   Let L_padsucc be the set of all strings u#v in L_2padid such that v is the successor of u.
   Let L_padnotsuc be the set of all strings u#v in L_2padid such that v is not the successor of u. The basic technique for proving that L_padnotsuc is a context free language is to find a finite set of context free languages, say L₀, L₁, ... L_m, such that L_padnotsuc is the intersection of L_2padid with the union of all the L_i. The number m depends on M. If v is not the successor of u, there must be a certificate of that fact. We will prove that, whatever that certificate is, u#v is a member of at least one of the L_i.
   We begin by proving that a certificate consists of only 5 symbols in the right positions.
   Define a 4-string to be any string of length 4 over the alphabet Q+Gamma+{B,$}. If alpha is a 4-string and s in Q+Gamma+{B,$}, we say that f(alpha) = s if the following holds:
   For any u,v in L_padid, if v is the successor of u, and if alpha = u[n-1:n+2], then v[n] = s.
   If alpha is a 4-string and if f(alpha) is defined, we call alpha a possible 4-string. Otherwise we call alpha an impossible 4-string.
   Lamma A: Let alpha be any impossible 4-string. If any u in L_padid has alpha as a substring, then v does not have a successor.
   The basic idea of Lemma A is that each symbol of the successor of x can be computed by looking at at most 4 symbols of x. The introduction of the symbol $ is to make the statement of Lemma A uniform, rather than having special cases for the left and right ends of the string.
   We now prove Lemma A. Let alpha be a string over Gamma+Q+{B,$} of length 4. There is a simple algorithm, using the transition function of M, for verifying whether alpha is possible, and if so, what the value of s is. (The basic idea is that, if we know the current state, the contents of the current cell, and the contents of the cells immediately to the left and right of the current cell, we can compute whether M halts or hangs, and if not, the new contents of the current cell and the new state.) The full proof of Lemma A involves several cases.
   If alpha contains $ in an impossible place, then alpha is impossible. (I won't bother to list the ways that could happen; one example is if alpha[3] is $ and alpha[4] is not $.)
   If alpha contains more than one symbol of Q, then alpha is impossible.
   If alpha contains the substring qa where delta(q,a) is undefined, or if alpha contains the substring q$ where delta(q,B) is undefined, then alpha is impossible.
   In all other cases, alpha is possible, and s = f(alpha) is determined as follows:
   1. If alpha [1:3] has no symbol in Q, then s = alpha[2]. Comment: If a cell is far away from the tape head, the symbol on that cell does not change, and the position in the ID representing that cell also does not change.
   2. If alpha[1] = q in Q, alpha[2] = g in Gamma+B, and delta(q,g) = (q',g',R), then s = q'.
   3. If alpha[1] = q in Q, alpha[2:4] = $$$, and delta(q,B) = (q',g',R), then s = q'.
   4. If alpha[1] = q in Q, alpha[2] = g in Gamma, and delta(q,g) = (q',B,L), and alpha[3:4] = $$, then s = $.
   5. If alpha[1] = q in Q, alpha[2] = g in Gamma+B, and delta(q,g) = (q',g',L), and either g' is not B or alpha[3:4] is not $$, then s = g'.
   6. If alpha[1] = q in Q, alpha[2:4] = $$$, and delta(q,B) = (q',g',L), and g' is not B, then then s = g'.
   7. If alpha[1] = q in Q, alpha[2:4] = $$$, and delta(q,B) = (q',B,L), then then s = $.
   8. If alpha[2] = q in Q, alpha[3] = g in Gamma+B, and delta(q,g) = (q',g',L), then s = alpha[1].
   9. If alpha[2] = q in Q, alpha[3:4] = $$, and delta(q,B) = (q',g',L), and g' is not B, or alpha[1] is not B, then s = alpha[1].
   10. If alpha[2] = q in Q, alpha[3:4] = $$, and delta(q,B) = (q',B,L), and alpha[1] is B, then s = $.
   11. If alpha[2] = q in Q, alpha[3] = g in Gamma+B, and delta(q,g) = (q',g',R), then s = g'.
   12. If alpha[3] = q in Q, alpha[4] = g in Gamma+B, and delta(q,g) = (q',g',L), then s = q'.
   13. If alpha[3] = q in Q, alpha[4] = $, and delta(q,B) = (q',g',L), then f(alpha) = q'.
   14. If alpha[3] = q in Q, alpha[4] = g in Gamma+B, and delta(q,g) = (q',g',R), then s = alpha[2].
   15. If alpha[3] = q in Q, alpha[4] = $, and delta(q,B) = (q',g',R), then f(alpha) = alpha[2].
   We now define the L_i, in such a way that L_i cannot contain any member of L_padsucc, and also that every member of L_padnotsucc is in at least one of the L_i.
   Let Alpha_pos = {alpha₁, alpha₂, ... alpha_m} be the set of possible 4-strings. Let Alpha_imp be the set of impossible 4-strings, a finite set also.
   Let
   L₀ = (Gamma+Q+{B,$})*Alpha_imp(Gamma+Q+{B,$})*#(Gamma+Q+{B,$})*
   which is a regular, hence a context-free, language.
   For each i = 1,...m, Let s_i = f(alpha_i). Then, for each i, we define L_i to be the language of strings z which contain exactly one #, which have a copy of alpha_i to the left of the #, and which have a symbol which is not s_i to the right of the # positioned in just such a way as to certify that z cannot be in L_padsuc. That means, there exist n,p such that 1 < n < p, z[n-1:n+2] = alpha_i, z[p] = #, and z[p+n] is not s_i.
   L_i is generated by the following context-free grammar:
   1. S -> UXYV
   2. U -> XUX
   3. U -> alpha_iV#
   4. V -> XV
   5. V -> epsilon
   6. X -> any symbol of Q+Gamma+{B,$}
   7. Y -> any symbol of Q+Gamma+{B,$} except s_i
   
   Note that L_i contains strings that are not in L_2padid. These strings play no role, but are harmless to the proof.

   

   Back to Course Page