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?
Asked
Active
Viewed 1,369 times
1 Answers
1
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.
David
- 82,662