patternMinor
Construct Turing Machine which accepts the language $ww$
Viewed 0 times
acceptsthewhichlanguagemachineturingconstruct
Problem
I try to construct a TM that accepts the language $\{ ww \mid w \in \{a,b\}^* \}$.
Between the words $w$ is no delimeter, so I don't know, how my TM can know where the first $w$ ends and the second $w$ begins.
Is there a trick for this?
Between the words $w$ is no delimeter, so I don't know, how my TM can know where the first $w$ ends and the second $w$ begins.
Is there a trick for this?
Solution
Here is a sketch for how a deterministic machine might work:
- place a marker in front of the input.
- go through the input, checking if the length is even. If not, reject.
- place a marker behind the input.
- going back and forth, move the markers towards each other until they meet in the middle.
- as long as the halves are nonempty, compare and erase their first letters and reject if not equal.
- accept.
Context
StackExchange Computer Science Q#43639, answer score: 5
Revisions (0)
No revisions yet.