CopyPastor

Detecting plagiarism made easy.

Score: 0.8049189448356628; Reported for: String similarity Open both answers

Possible Plagiarism

Reposted on 2025-10-04
by trincot

Original Post

Original - Posted on 2024-09-27
by trincot



            
Present in both answers; Present only in the new answer; Present only in the old answer;

Moving like "a wall" to right is not the right approach, at least not just like that. You first need to identify the section that must be deleted. Once you have marked that, you can start shifting a block so to join the two parts that get disjoint by that deletion. Either the left block has to shift to the right, or the right block to the left. I chose to go for the second approach.
To mark the part to delete you need to count b's, i.e. mark them one by one, while also removing from the counter (which is the first part of the input string). Once the counter has been depleted, you know where the part starts that needs deletion. You can then fill that part will some marker (like X), and shift the remainder after that to the left. At the end you can wipe out the suffix of X.
This could be done with this transition table (underscore represents a blank):
| state | read | write | move head | next state | :--: | :--: | :--: | :--: | :--: | start | a | _ | right | get | start | b or _ | | right | reject | get | a | _ | right | findb | get | b | _ | right | wipe | get | B | _ | right | tostart | get | _ | | left | reject | findb | a or B | | right | findb | findb | b | B | left | rewind | findb | _ | | left | reject | rewind | a or B | | left | rewind | rewind | _ | | right | get | tostart | B | b | right | tostart | tostart | a | | right | tostart | tostart | b | X | right | toend | tostart | _ | | left | reject | toend | a | X | right | toend | toend | b | X | left | moveB | toend | _ | | left | clear | clear | X | _ | left | clear | clear | a or b | | left | clear | clear | _ | | right | accept | wipe | a | _ | right | wipe | wipe | b or _ | _ | right | accept | moveA | X | | left | moveA | moveA | a or b | | right | putA | moveB | X | | left | moveB | moveB | a | | right | putB | putA | X | a | right | next | putB | X | b | right | next | next | X | | right | next | next | a | X | left | moveA | next | b | X | left | moveB | next | _ | | left | clear

Here is an implementation using a JavaScript library that takes care of the TM execution, based on a given transition table:
<!-- begin snippet: js hide: false console: true babel: false babelPresetReact: false babelPresetTS: false -->
<!-- language: lang-js -->
createTuring({ transitions: [ { state: "start", read: "a", write: "_", move: "R", nextState: "get" }, { state: "start", read: "b_", move: "R", nextState: "reject" },
{ state: "get", read: "a", write: "_", move: "R", nextState: "findb" }, { state: "get", read: "b", write: "_", move: "R", nextState: "wipe" }, { state: "get", read: "B", write: "_", move: "R", nextState: "tostart"}, { state: "get", read: "_", move: "L", nextState: "reject" },
{ state: "findb", read: "aB", move: "R", nextState: "findb" }, { state: "findb", read: "b", write: "B", move: "L", nextState: "rewind" }, { state: "findb", read: "_", move: "L", nextState: "reject" }, { state: "rewind", read: "aB", move: "L", nextState: "rewind" }, { state: "rewind", read: "_", move: "R", nextState: "get" },
{ state: "tostart",read: "B", write: "b", move: "R", nextState: "tostart"}, { state: "tostart",read: "a", move: "R", nextState: "tostart"}, { state: "tostart",read: "b", write: "X", move: "R", nextState: "toend" }, { state: "tostart",read: "_", move: "L", nextState: "reject" },
{ state: "toend", read: "a", write: "X", move: "R", nextState: "toend" }, { state: "toend", read: "b", write: "X", move: "L", nextState: "moveB" }, { state: "toend", read: "_", move: "L", nextState: "clear" },
{ state: "clear", read: "X", write: "_", move: "L", nextState: "clear" }, { state: "clear", read: "ab", move: "L", nextState: "clear" }, { state: "clear", read: "_", move: "R", nextState: "accept" },
{ state: "wipe", read: "a", write: "_", move: "R", nextState: "wipe" }, { state: "wipe", read: "b_", write: "_", move: "R", nextState: "accept" },
{ state: "moveA", read: "X", move: "L", nextState: "moveA" }, { state: "moveA", read: "ab", move: "R", nextState: "putA" }, { state: "moveB", read: "X", move: "L", nextState: "moveB" }, { state: "moveB", read: "a", move: "R", nextState: "putB" }, { state: "putA", read: "X", write: "a", move: "R", nextState: "next" }, { state: "putB", read: "X", write: "b", move: "R", nextState: "next" }, { state: "next", read: "X", move: "R", nextState: "next" }, { state: "next", read: "a", write: "X", move: "L", nextState: "moveA" }, { state: "next", read: "b", write: "X", move: "L", nextState: "moveB" }, { state: "next", read: "_", move: "L", nextState: "clear" },

], initState: "start", tape: "aaababaabaaabaaaa", });
<!-- language: lang-html -->
<script src="https://trincot.github.io/turing.js"></script>
<!-- end snippet -->

You can keep track of the decreasing number of 𝑘 by mapping each `a` that belongs to the encoding of 𝑘 with a `b`. The idea to mark the characters that belong to such a pair is a good one. Once you have no more (unmarked) `a` left over, you can start to delete characters up until (and including) the first unmarked `b`. The `a` that follow should stay. Finally delete any characters that follow that series of `a`.
This approach would actually select the k+1<sup>th</sup> number, so just delete the first `a` without mapping it to a `b` to compensate for that.
You mentioned in comments that you are using a one-sided Turing Machine, where it is infinite to the right, but has a start at the left, where also the head starts. As you indicated that the expected output should be left-aligned at the start of the tape, you'll need some extra states and transitions to "move" the found sequence of `a` to the left. You can do this in different ways. One is to delete the rightmost `a` and write one at the left side of the sequence. Repeat this until you arrive at the start of the tape, which we could mark with a letter "A".
I would also wipe out the `a` that belong to 𝑘 instead of marking them with an uppercase, as in the end you'll want to delete or replace those anyway.
Here is a possible transition table:
| state | read | write | move head | next state | :--: | :--: | :--: | :--: | :--: | start | a | A | right | get | start | b or _ | | right | reject | get | a | _ | right | findb | get | B | _ | right | wipe | get | b | _ | right | keep | findb | a or B | | right | findb | findb | b | B | left | rewind | findb | _ | | left | reject | rewind | a or B | | left | rewind | rewind | _ | | right | get | wipe | a or B | _ | right | wipe | wipe | b | _ | right | keep | wipe | _ | | left | reject | keep | a | | right | keep | keep | _ | | left | pickup | keep | b | _ | right | trim | trim | a or b | _ | right | trim | trim | _ | | left | pickup | pickup | a | _ | left | roll | pickup | _ | | left | pickup | pickup | A | _ | | accept | roll | a | | left | roll | roll | _ | a | right | right | right | a | | right | right | right | _ | | left | pickup | roll | A | a | | accept
The initial state is "start" and a blank is represented by "_". If the input has a solution, the final state will be "accept".
Here is a runnable implementation with that transition table:
<!-- begin snippet: js hide: false console: true babel: false -->
<!-- language: lang-js -->
createTuring({ transitions: [ { state: "start", read: "a", write: "A", move: "R", nextState: "get" }, { state: "start", read: "b_", move: "R", nextState: "reject" }, { state: "get", read: "a", write: "_", move: "R", nextState: "findb" }, { state: "get", read: "B", write: "_", move: "R", nextState: "wipe" }, { state: "get", read: "b", write: "_", move: "R", nextState: "keep" }, { state: "findb", read: "aB", move: "R", nextState: "findb" }, { state: "findb", read: "b", write: "B", move: "L", nextState: "rewind" }, { state: "findb", read: "_", move: "L", nextState: "reject" }, { state: "rewind", read: "aB", move: "L", nextState: "rewind" }, { state: "rewind", read: "_", move: "R", nextState: "get" }, { state: "wipe", read: "aB", write: "_", move: "R", nextState: "wipe" }, { state: "wipe", read: "b", write: "_", move: "R", nextState: "keep" }, { state: "wipe", read: "_", move: "L", nextState: "reject" }, { state: "keep", read: "a", move: "R", nextState: "keep" }, { state: "keep", read: "_", move: "L", nextState: "pickup" }, { state: "keep", read: "b", write: "_", move: "R", nextState: "trim" }, { state: "trim", read: "ab", write: "_", move: "R", nextState: "trim" }, { state: "trim", read: "_", move: "L", nextState: "pickup" }, { state: "pickup", read: "a", write: "_", move: "L", nextState: "roll" }, { state: "pickup", read: "_", move: "L", nextState: "pickup" }, { state: "pickup", read: "A", write: "_", nextState: "accept" }, { state: "roll", read: "a", move: "L", nextState: "roll" }, { state: "roll", read: "_", write: "a", move: "R", nextState: "right" }, { state: "right", read: "a", move: "R", nextState: "right" }, { state: "right", read: "_", move: "L", nextState: "pickup" }, { state: "roll", read: "A", write: "a", nextState: "accept" }, ], initState: "start", tape: "aaababaaaaabaa" });
<!-- language: lang-html -->
<script src="https://trincot.github.io/turing.js"></script>
<!-- end snippet -->


        
Present in both answers; Present only in the new answer; Present only in the old answer;