1
$\begingroup$

Can someone explain to me what this statement implies? I am assuming that it means that a string consisting of three characters repeated. What I don't understand is if the repeated string is all 0s or all 1s or both?

Give the state diagram of a machine (any Turing-Complete model) that decides the following languages over {0,1}:

{w : w = xxx, x ∈ Σ*}

$\endgroup$
1
$\begingroup$

The language you are trying to decide here is xxx: that is, three copies of x. What is x? Well, it can be anything in $\Sigma *$: any string in your alphabet. (Usually this means "any binary string", but you can also use a different alphabet, the principle will be the same.)

So you're looking for any string which consists of something repeated three times. So strings in the language include 111, and 000, and ε (the empty string), and 100100100, and 101011010110101.

As for the machine that recognizes this, recognizing the language xx : $x \in \Sigma *$ is a classic demonstration of the power of Turing machines (since this language is neither regular nor context-free). Try starting from that machine and seeing what changes you'd need to make for xxx.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.