CODEWITHSUNDEEP
binaryautomataturing-machinesautomatonjflap
sangonm
sangonm

Reputation: 11

Turing Machine that outputs the number of a's and b's in binary representation

I'm trying to design a Turing Machine that takes as input a word formed by symbols of the alphabet Σ = {𝑎, 𝑏} and counts, in binary, the occurrences of symbol 𝑎 and the occurrences of symbol 𝑏.

The final contents of the tape must correspond to:

Example:

Input: aababbbabaaba

Output: 111$110aababbbabaaba

Explanation: There are 7 𝑎 in the input, which in binary is 111. There are 6 𝑏 in the input, which in binary is 110.

My attempt

My first attempt counts only the 𝑏's as unary 1s:

enter image description here

I duplicated the same mechanism to count the 𝑎's:

enter image description here

But I don't see how can I encode the outputs in binary. How can this be done?

Upvotes: 1

Views: 209

Answers (1)

trincot
trincot

Reputation: 350831

A nice way to generate binary from a unary representation, is to mark one out of two bits in the unary representation and log a 1 when one more was marked than not. Otherwise log a 0. Then repeat until all the unary representation has been marked.

If we do this from right to left, logging the bits at the left side of the written part of the tape, and have it grow to the left, we get the binary representation of the unary encoded value.

As we have to do this for both 𝑎 and 𝑏, we can swap the 𝑎 and 𝑏 after the 𝑏 have been encoded in binary, so that in a second phase we can apply exactly the same procedure again. In fact, you could first exchange the 𝑎 and 𝑏, and then again before the second phase. That way they are again in their original order.

We can also first set all unary 𝑎 to A, and when marked, they turn back to 𝑎.

Here is a transition table for that process. Some specific states serve to write a 0 when there were no 𝑎 at all, and to write the $ separator:

state read write move head next state
start a b right start
start b A right start
start _ left scan
start 0 or 1 right start
right a, b, A, 0, 1 or $ right right
right _ left scan
scan A a left odd
scan a or b left scan
scan _ 0 left dollar
scan 0 or 1 left end
odd A left even
odd a, b, 0, 1 or $ left odd
odd _ 1 right right
even A a left odd
even a, b, 0, 1 or $ left even
even _ 0 right right
end 0 or 1 left end
end _ $ right start
end $ left check
dollar _ $ right start
check 0 or 1 right accept
check _ 0 right accept

And here is a runnable snippet to test this Turing machine with your own input:

createTuring({
    transitions: [
        { state: "start",  read: "a",   write: "b", move: "R", nextState: "start"  },
        { state: "start",  read: "b",   write: "A", move: "R", nextState: "start"  },
        { state: "start",  read: "_",               move: "L", nextState: "scan"   },
        { state: "start",  read: "01",              move: "R", nextState: "start"  },
        { state: "right",  read: "abA01$",          move: "R", nextState: "right"  },
        { state: "right",  read: "_",               move: "L", nextState: "scan"   },
        { state: "scan",   read: "A",   write: "a", move: "L", nextState: "odd"    },
        { state: "scan",   read: "ab",              move: "L", nextState: "scan"   },
        { state: "scan",   read: "_",   write: "0", move: "L", nextState: "dollar" },
        { state: "scan",   read: "01",              move: "L", nextState: "end"    },
        { state: "odd",    read: "A",               move: "L", nextState: "even"   },
        { state: "odd",    read: "ab01$",           move: "L", nextState: "odd"    },
        { state: "odd",    read: "_",   write: "1", move: "R", nextState: "right"  },
        { state: "even",   read: "A",   write: "a", move: "L", nextState: "odd"    },
        { state: "even",   read: "ab01$",           move: "L", nextState: "even"   },
        { state: "even",   read: "_",   write: "0", move: "R", nextState: "right"  },
        { state: "end",    read: "01",              move: "L", nextState: "end"    },
        { state: "end",    read: "_",   write: "$", move: "R", nextState: "start"  },
        { state: "end",    read: "$",               move: "L", nextState: "check"  },
        { state: "dollar", read: "_",   write: "$", move: "R", nextState: "start"  },
        { state: "check",  read: "01",              move: "R", nextState: "accept" },
        { state: "check",  read: "_",   write: "0", move: "R", nextState: "accept" },
    ],
    initState: "start",
    tape: "aababbbabaaba"
});
<script src="https://trincot.github.io/turing.js"></script>

Upvotes: 0

Related Questions