Turing machine that accepts language with more a's than b's

Question

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.

Answer 1

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.

Answer 2

Erase one a, erase one b, repeat until you can't. Then see whether as or bs remain.

Answer 3

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 :)