Assignment - Specifying Some Machines

Shown below are formulae which specify two "languages;" L1 and L2. The vocabulary for both of these languages is {A, B, C}. Note that the letters are superscripted. The superscripts are shown in small letters. The formula for L1 says that any string that has n A's followed by m B's followed by r C's followed by s B's followed by t A's is a member of the language, L1. For example, AAABCCBBA would be a member of L1. The string, BAAABCCBBA would not be a member of L1. We will always assume for purposes of this assignment that none of the superscripts can take on the value of 0, but any positive integer is a possible value of any of the superscripts. The formula for the language L2 is very similar to the formula for the language L1. The difference is that the number of B's that occur before the C's must be the same as the number of B's that occur after the C's. Similarly, the number of A's that occur before the first string of B's must be the same as the number of A's that occur after the second string of B's. Finally, the number of C's must be an even number.
Your assignment is to write down two machines; one that accepts L1 and another that accepts L2. A machine is said to accept an input string if at the end of the string the machine is in a halt state. A machine does not accept a string if either it is not in a halt state at the end of the string or the machine hangs. A machine hangs when it contains no instruction that applies to its current state and the element under the read head. The set of strings accepted by a machine is referred to as the language of the machine. Thus, your task is to write machines that correspond to the two languages shown above. For each language, try to write down the simplest and least powerful machine that can be used to accept the language.
Some Review
Recall that we have spoken of two different classes of machines, Finite State Machines and Turing Machines. Recall that an instruction is of the form:
	current control state  symbol under read head  action  new control state
where the <control states> are from a finite set of state names, and one of the control states must be identified as the starting state of the computation and a finite set of states (at least one) must be designated as final states. A final state is a state that signals termination of the computation. The <symbol> is from the vocabulary of the machine. And the <action> is: to move right, R, in the case of a Finite State Machine; or to move right, R; or left, L; or to Write an element of the vocabulary in the current square of the tape. Recall that the blank is indicated by the symbol, #. Thus, writing # is equivalent to erasing the contents of the cell on which # is written. In the Introduction section I used a slightly different variant of a Turing Machine which you may use if you wish. In this variant a rule is of the form:
	current control state current symbol   new symbol  action  new control state
In this case we think of the machine as writing a symbol at each step. If we want it to leave the current symbol unaffected we have it write the current symbol as the new symbol. The only advantage to this specification of an instruction as a quintuple rather than a quadruple is that one can usually write down fewer rules.
After Specifying the Machines:
Some questions: Could you have written both machines as a Finite State Machines? Why or why not? Do you think that a single machine could be specified that accepted both languages? Can you identify the constraints that were specified by these formula? Can you explain why some of the constraints required the ability to write to the tape and others did not?

	Formal Models of Computation - Table of Contents
© Charles F. Schmidt	ABCBA Machines and Their Traces