I am trying to construct a Turing machine which will double every 'b' in all inputted strings over{c,b}. How can I double 'b' in inputted string? because I cannot replace b with bb because one cell of tape can contain only one character.
7
-
$\begingroup$ A simple Turing Machine ( as I am just learning its basics ) .Yes every time when I 'll read 'b' I can replace it with any symbol but my problem is that every time when 'b' comes machine will double it 'bb' .For example {c,bc,b,cb} will became {c,bbc,bb,cbb} $\endgroup$– ZunairaCommented Mar 27, 2019 at 1:34
-
1$\begingroup$ If you "cannot replace b with bb because one cell of tape can contain only one character.", locate other cells to write. $\endgroup$– John L.Commented Mar 27, 2019 at 1:42
-
$\begingroup$ @Apass.Jack Sorry for that its {c,b} $\endgroup$– ZunairaCommented Mar 27, 2019 at 1:56
-
$\begingroup$ @Apass.Jack "locate other cells to write" How am I supposed to do that? $\endgroup$– ZunairaCommented Mar 27, 2019 at 1:57
-
$\begingroup$ @Zunaira How about locating the first blank cell after the input, putting $bb$ there? This step alone will not solve the problem. That is the idea, though. $\endgroup$– John L.Commented Mar 27, 2019 at 2:06
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
When you encounter $b$ change state to shifting tape right: move to next cell read content and put blank character.
Keep replacing characters until you encounter blank character (end of your tape content).
Put your last character at the end and move head left until you find blank character. Pur $b$ there.
Keep moving right until you find $b$ and repeat.
In your example:
$\color{green}cbcbcb\_$
Move right
$c\color{green}bcbcb\_$
Change state to copy and put blank:
$cb\color{green}\_bcb\_$ switch state to put $c$ and memorize next element
$cb\_\color{green}ccb\_$ switch state to put $b$ and memorize next element
$cb\_c\color{green}bb\_$ switch state to put $c$ and memorize next element
$cb\_cb\color{green}c\_$ switch state to put $b$ and memorize next element
$cb\_cbc\color{green}b\_$ blank encountered, move back to blank
$cb\_cb\color{green}cb\_$
$cb\_c\color{green}bcb\_$
$cb\_\color{green}cbcb\_$
$cb\color{green}\_cbcb\_$ blank encountered put $b$
$cbb\color{green}cbcb\_$ now repeat move right and switch to copy mode when another $b$ is found. When you reach end of the tape then all $b$'s are doubled.
$\begingroup$
$\endgroup$
Alternatively, use another tape to write your result on : if it is a b, write two b, otherwise juste copy the character. This works as well as having one tape because one can show that a one tape TM can simulate a k-tape TM for any fixed k.
