I am doing an assignment for my 1st year langauges and automata class. I have been having trouble with the last question which is this: Create a Turing machine that acccepts more a's than b's. I think I am supposed to pair the a's and b's together and then do some more but I can't wrap my head around it. Would help greatly if someone can post the algorithm and explain a little.
$\begingroup$
$\endgroup$
-
$\begingroup$ The answers to this recent question can be adapted relatively easily. The only difference is that you don't have the strict order, so you have to search for the $a$s and $b$s, and have to deal with how to erase them without losing track of where you're up to. $\endgroup$ – Luke Mathieson Dec 6 '13 at 7:23
$\begingroup$
$\endgroup$
Sit before a big empty sheet of paper. Write down a sequence of a's and b's. Now mechanically check whether that string should be accepted. You cannot use counting, that would be requiring an infinite number of "states" inside your head. You can however use additional symols. A striked out b is just a new symbol that is written on the tape.
Turn your intuition into an algorithm. First informally, that is what Karolis has done. Then add information on how to implement this on a Turing tape. What direction is the head moving? Where will it stop? Then translate the whiles and untils into states and transitions (sort of goto-programming, which is improper unless you are programming a TM).
If you are a CS student, then you can do these steps. You can program. No matter whether it is C++, assembler, or Turing. That is just details.
$\begingroup$
$\endgroup$
Erase one a, erase one b, repeat until you can't. Then see whether as or bs remain.
$\begingroup$
$\endgroup$
When I was a TA for a course on this stuff, I always recommended students think about it in terms of how you'd recognize patterns of colored marbles. This problem becomes: how do you recognize a row of marbles with more red marbles than blue marbles?
There are lots of approaches to such a problem. You could first count the red marbles, and then count the blue marbles. If you're allowed to give a multi-tape TM for this problem, this is a pretty straightforward solution:
while not at the end of the tape do
if marble is red then
write a symbol to the red auxiliary tape
move the red auxiliary tape head to the right
if marble is blue then
write a symbol to the blue auxiliary tape
move the blue auxiliary tape head to the right
move the input tape head to the right
rewind the red tape to the front
rewind the blue tape head to the front
until you reach the end of the red tape do
move the red tape head to the right
move the blue tape head to the right
if at the end of the blue tape and not at the end of the red tape then
return Accepted
return Rejected
If you'd rather have a single tape solution, other procedures might lend themselves better to this problem. How else might you tell whether you have more blue or red marbles? As another answer points out, you can remove one blue and one red marble from the row of marbles, and repeat until you run out of one color of marble. This looks something like this:
while true do // forever
enter the green state
while not at the end of the tape do
move the tape head right
if in the green state and marble is blue then
enter red state
replace with green marble
else if in the green state and marble is red then
enter blue state
replace with green marble
else if in the red state and marble is red then
enter black state
replace with green marble
else if in the blue state and marble is blue then
enter black state
replace with green marble
if in the red or green states then
// red state means we needed a red and didn't find one; #red < #blue
// green state means that we removed all marbles and
// had as many red as blue; #red = #blue
return Rejected
else if in the blue state then
// blue state means we needed a blue and didn't find one; #red > #blue
return Accepted
else
// in the black state, so we removed a red and a blue;
// there may still be marbles to remove, so we start over.
rewind the tape head to the beginning
Are there other possibilities? Sure there are. You could first sort the marbles to make it easier to find pairs, for instance. Remember: as far as we know, human beings can't do anything computationally more powerful than what a TM can do. That means that if you can answer this question for an arbitrary sequence of marbles, so can a Turing machine :)
