1
$\begingroup$

I am having trouble with a past exam paper. I have to design a Turing Machine to do the following, but I don't really know where to start with this question. Any help would be very much appreciated.


Design a Turing Machine TM checking if the numbers of sold apples and bananas are even. Formally, given a string w over the alphabet {a,b}, TM should terminate with the following result string.

ab if the number of apples and bananas are even
a if the number of apples is even but bananas are odd
b if the number of apples is odd and bananas are even
ϵ if the number of apples and bananas are both odd

enter image description here

Thanks

$\endgroup$
  • 2
    $\begingroup$ What have you tried? Where did you get stuck? Do you have an overall design on how your TM is supposed to work? $\endgroup$ – vonbrand May 21 '13 at 20:20
  • $\begingroup$ I have first tried to design a Finite State Machine to show how to design the Turing Machine, but I am not even able to get that far. I know how to design a Turing Machine to say if the number of 1s are even or odd, but adding a second variable has made it so complicated. $\endgroup$ – George Robinson May 21 '13 at 20:40
  • $\begingroup$ Turing machines are rather abstract. But Fruit Programming is what I like! Here is what you do. Initialization. Add an apple and a banana before the fruit present (this is essential). Program. Look at the fruit. If you spot a pair of the same, eat them. Repeat. Note: do not attempt with large input. $\endgroup$ – Hendrik Jan May 22 '13 at 20:10
5
$\begingroup$

I'm not going to give you a direct solution, but let's think about this problem together, shall we? We will focus on 4 states. Why four? Well, you have two variables, each with two possible states, so $2^2 = 4$. So, for right now let's call our states $1$, $2$, $3$ and $4$:

  • $1$ is the state denoting an even number of apples and bananas. This is our start state.
  • $2$ is the state denoting an odd number of apples and an even number of bananas.
  • $3$ is the state denoting an even number of apples and an odd number of bananas.
  • $4$ is the state denoting an odd number of apples and an odd number of bananas.

Now, let's see how we move between states. For the moment, let's ignore the possibility of $\varepsilon$ for the input.

From state $1$ ($a$=even, $b$=even):

  • If we get an $a$, go to state $2$. Eat the apple and output nothing.
  • If we get a $b$, go to state $3$. Eat the banana and output nothing.

From state $2$ ($a$=odd, $b$=even):

  • If we get an $a$, we go to state $1$. Eat the apple and output nothing.
  • If we get a $b$, we go to state $4$. Eat the banana and output nothing.

From state $3$ ($a$=even, $b$=odd):

  • If we get an $a$, we go to state $4$. Eat the apple and output nothing.
  • If we get a $b$, we go to state $1$. Eat the banana and output nothing.

From state $4$ ($a$=odd, $b$=odd):

  • If we get an $a$, we go to state $3$. Eat the apple and output nothing.
  • If we get a $b$, we go to state $2$. Eat the banana and output nothing.

At this point we are pretty full and sick of apples and bananas. So let's consider what happens when we run out of food. It should be clear that we are going to be in one of the four states above. So let's augment each of them with an additional rule each:

The rule is simple: when the input for any one of those states is $\varepsilon$, output the correct sequence of characters for that state and then go to a $halt$ state.

I hope this helps!

$\endgroup$
0
$\begingroup$

This is the answer to my question. I have used four states each with an arc to the halting state. http://i.stack.imgur.com/iAsdO.jpg

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.