Deterministic Turing machine for a duplicate concatenation of a string

1.3k Views Asked by At

What's the best approach for building a deterministic Turing machine for the language $$L = \{vv : v \in \{a,b\}^+ \}$$ where there is no midpoint marker in the string? How can we determine where one v ends and where the other v begins?

1

There are 1 best solutions below

0
On

May not be the best approach but I would suggest: insert a marker after the first letter; see if it works; if not, shift the marker to after the second letter; and so on.