[Solved]: Design a Turing Machine Checking if Apples and Bananas are Even

ignougroup
Problem Detail: 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

Asked By : George Robinson

Answered By : Nik Bougalis

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!

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12200