Construct a TM that inserts the symbol x after every three symbols of the input string. For example, if the input is: $abbababba∆∆∆…… then the output should be $abbxabaxbbax∆∆∆……
Sol:
So first we understand the basic concept of inserting the symbol x after every three symbols with little examples then we move on to the actual question such as:
1) Input is: $abba∆ & Output is: $abbx∆
2) Input is: $abbaab∆ & Output is: $abbxaabx∆
3) Input is: $babababba∆ & Output is: $ babxabaxbbax∆
Then the actual question is in 4 parts so this is final your answer first three parts to understand the basic concept
4) Input is: $abbababba∆∆∆ & Output is: $abbxabaxbbax∆∆∆
So in Turing Machine From start 1 state to state 2 $ replace with $ and right move. From state 2 to state 3 ‘a’ replace with the ‘a’ and right move. From state 3 to state 4 ‘b’ replace with ‘b’ and the right move. Again from state 4 to state 5 ‘b’ replace with ‘b’ and the right move. Now from state 5 to state 6 ‘a’ replace with ‘x’ and the right move. In the end, we move from state 6 to halt or final state ‘∆’ replace with ‘∆’ and right move.
So in Turing Machine From start 1 state to state 2 $ replace with $ and right move. From state 2 to state 3 ‘a’ replace with the ‘a’ and right move. From state 3 to state 4 ‘b’ replace with ‘b’ and the right move. Again from state 4 to state 5 ‘b’ replace with ‘b’ and the right move. Now from state 5 to state 6 ‘a’ replace with ‘x’ and the right move. On state 6 ‘a’ replace with the ‘a’ and right move. From states, 6 to 7 ‘b’ replace with the ‘a’ and right move.
Now in Turing Machine from state 7 to 15 ‘∆’ replace with ‘b’ and left move. On state 15 ‘a replace with ‘a’ and ‘b’ replace with ‘b’, the right move. Now from state 15 to state 16 ‘x’ replace with ‘x’ and the right move. From state 16 to state 17 ‘a’ replace with the ‘a’ and right move. From state 17 to state 18 ‘a’ replace with the ‘a’ and right move. From state 18 to state 5 ‘b’ replace with ‘b’ and the right move. From state 5 to state 14 ‘∆’ replace with ‘x’ and the right move. At the end from state 14 to halt or final state ‘∆’ replace with ‘∆’ and the right move.
So in Turing Machine From start 1 state to state 2 $ replace with $ and right move. From state 2 to state 3 ‘b’ replace with ‘b’ and the right move. From state 3 to state 4 ‘a’ replace with the ‘a’ and right move. Again from state 4 to state 5 ‘b’ replace with ‘b’ and the right move. Now from state 5 to state 6 ‘a’ replace with ‘x’ and the right move. From states, 6 to 7 ‘b’ replace with the ‘a’ and right move. From states 7 to 6 ‘a’ replace with ‘b’ and the right move. Now again from states, 6 to 7 ‘b’ replace with the ‘a’ and right move. On state 7 ‘b’ replace with ‘b’ and the right move. From states 7 to 6 ‘a’ replace with ‘b’ and the right move. From state 6 to 8 ‘∆’ replace with ‘a’ and left move.
Now in Turing Machine on state 8 ‘b’ replace with ‘b’ and ‘a’ replace with ‘a’, left move. From state 8 to state 9 ‘x’ replace with ‘x’ right move. From state 9 to state 10 ‘a’ replace with the ‘a’ and right move. From state 10 to state 11 ‘b’ replace with ‘b’ and the right move. From state 11 to state 5 ‘a’ replace with the ‘a’ and right move. Now from state 5 to state 7 ‘b’ is replaced with ‘x’ and the right move. On state 7 ‘b’ replace with ‘b’ and the right move. From state 7 to state 6 ‘a’ replace with ‘b’ and the right move. From states 6 to 8 ‘∆’ replace with the ‘a’ and left move.
Again in Turing Machine on state 8 ‘b’ replace with ‘b’ and left move. From state 8 to state 9 ‘x’ replace with ‘x’ and the right move. From state 9 to state 10 ‘b’ replace with ‘b’ and the right move. From state 10 to state 11 ‘b’ replace with ‘b’ and the right move. From state 11 to state 5 ‘a’ replace with the ‘a’ and right move. From state 5 to state 14 ‘∆’ replace with ‘x’ and the right move. At the end from state 14 to halt or final state ‘∆’ replace with ‘∆’ and the right move.
So in Turing Machine From start 1 state to state 2 $ replace with $ and right move. From state 2 to state 3 ‘a’ replace with the ‘a’ and right move. From state 3 to state 4 ‘b’ replace with ‘b’ and the right move. Again from state 4 to state 5 ‘b’ replace with ‘b’ and the right move. Now from state 5 to state 6 ‘a’ replace with ‘x’ and the right move. From states, 6 to 7 ‘b’ replace with the ‘a’ and right move. From states 7 to 6 ‘a’ replace with ‘b’ and the right move. Now again from states, 6 to 7 ‘b’ replace with the ‘a’ and right move. On state 7 ‘b’ replace with ‘b’ and the right move. From states 7 to 6 ‘a’ replace with ‘b’ and the right move. From state 6 to 8 ‘∆’ replace with ‘a’ and left move.
Now in Turing Machine on state 8 ‘b’ replace with ‘b’ and ‘a’ replace with ‘a’, left move. From state 8 to state 9 ‘x’ replace with ‘x’ right move. From state 9 to state 10 ‘a’ replace with the ‘a’ and right move. From state 10 to state 11 ‘b’ replace with ‘b’ and the right move. From state 11 to state 5 ‘a’ replace with the ‘a’ and right move. Now from state 5 to state 7 ‘b’ is replaced with ‘x’ and the right move. On state 7 ‘b’ replace with ‘b’ and the right move. From state 7 to state 6 ‘a’ replace with ‘b’ and the right move. From states 6 to 8 ‘∆’ replace with the ‘a’ and left move.
Again on state 8 ‘b’ replace with ‘b’ and left move. From state 8 to state 9 ‘x’ replace with ‘x’ and the right move. From state 9 to state 10 ‘b’ replace with ‘b’ and the right move. From state 10 to state 11 ‘b’ replace with ‘b’ and the right move. From state 11 to state 5 ‘a’ replace with the ‘a’ and right move. From state 5 to state 14 ‘∆’ replace with ‘x’ and the right move. At the end of the Turing Machine from state 14 to halt or final state ‘∆’ replace with ‘∆’ and the right move.
