Construct a deterministic one way infinite single tape Turing machine that accepts the language { w | w in {x, y, z}* such that the number of x's in w < the number of y's in w and ((the number of x's in w divides the number of z's in w) or (the number of z's in w divides the number of x's in w)) }.

You may not make use of the fact that JFLAP has blank spaces to the left of the input. And you may not use blocks for this Turing machine. And finally, you can only use the left and right tape head moves (that is, do not use the stay directive).

Since JFLAP does not specifically have a reject state, you can either have a state that you transition to that has no outgoing transitions or you can simply leave off transitions that can never reach the accept state after taking, either will cause your Turing machine to reject the input.

My Turning machine has 31 states, but it appears that it could be reduced to 28 states or less, since I have two accept states and two reject states (states that go nowhere).

My implementation does the following:

1) Inserts a $ in front of the input string to mark the left end of the tape

2) As part of inserting the $, it rejects if the input consists of only y's

3) Verify that the number of x's < the number of y's 1. If not, reject

4) Check if x's = z's - if so, accept the input

     1. If the number of x's < z's - relabel x's as b's and z's as a's

     2. If the number of x's > z's - relabel x's as a's and z's as b's

5) Verify that the number of b's divides the number of a's

     1. If it does, accept

     2. If it doesn't, reject