AnBnCn Machine and Traces

On this page is illustrated a TM that accepts the language consisting of n A's followed by n B's followed by n C's where n > 0.      The figure to the right provides a graphical illustration of this TM and the table below the figure lists the Tuples that define the machine. Note the similarity to the previous machine. Again, the algorithm begins by erasing the first A and then moving to the right end of the input string. The read head is then moved to the left and at q3 a C is erased. Next the head is moved left until a B is encountered. However, instead of erasing the B a new non-terminal symbol is written, namely %. This symbol serves as a memory for the location of the segment of B's on the input tape. As before, the TM then traverses to the left bound of the tape and repeats this procedure of removing an A, then a C and then a B from the tape. When no more A's are encountered, state q6 is entered. This state serves to control the process of checking that no B's or C's remain, that is, ensuring that there in fact were an equal number of A's, B's, and C's in the input string.    Clicking on the "thumbnails" below provide access to traces of this machine for the input strings ABC#, AABBCC#, AAABBBCCC#, and AAAABBBBCCCC#.
ABC# Trace AABBCC# Trace  AAABBBCCC# Trace AAAABBBBCCCC# Trace	Tuples current control state symbol under read head new symbol action  new control state q0  A  #  R q2 q2  A  A  R q2 q2  B  B  R q2 q2 C C R q2 q2 % % R q2 q2  #  #  L q5  q5 C # L q3 q3 C C L q3 q3 % % L q3 q3  B  %  L q4 q4  A  A  L q4 q4  B  B  L q4 q4  #  #  R q1 q1  A  #  R q2 q1 # # R q6 q1 % % R q6 q6 % % R q6 q6  #  # S  qh
Note the similarity between this algorithm and that defined on the previous page. It is also interesting to compare these two algorithms with the corresponding grammars that were provided as examples of Type 0 and Type 2 grammars. A Type 0 grammar is required for the AnBnCn language while a Type 2 is sufficient for the AnBn language. Despite this difference in the power of the grammar or machine required by these two examples, the equations defining their "space complexity" are identical and the equations defining their "time complexity" are almost the same.      Recall the equation that defines the"time complexity" of the previous algorithm, namely: Steps(n) = [2jn + 1] - [ [2(j-1) x (2(j-1) +1)] / 2 ] + 1 The last term of this equation, the '1,' represented the step that checked that all letters had been erased; thus validating that the equality predicate held. In the algorithm for AnBnCn the B's were not erased. Rather a new symbol, in this case the symbol '%' , is substituted. Consequently, in order to implement this last step of checking for any remaining letters, the algorithm must move across these new symbols until a blank or '# ' is encountered. There will be exactly j of these to move across. Consequently we must add this term to the equation. This then yields the equation: Steps(n) = [2jn + 1] - [ [2(j-1) x (2(j-1) +1)] / 2 ] + j + 1 where the added term is shown in red. The table below illustrates the values obtained for various values of n using this equation.
Number of Steps as a Function of n  j  1 2 3  4 5  6 7 8 9  10 11 12  n  3 6 9 12 15 18 21 24 27 30 33 36  Steps  9  25  49  81 121  169  225 289 361 441 529  625

	Machine Chapter
© Charles F. Schmidt	Formal Models of Computation - Table of Contents