HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Construct Turing Machine which accepts the language $ww$

Submitted by: @import:stackexchange-cs··
0
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?

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.