0

I want to create a diagram of a turing machine that decides the following language.

$\{w \in $ $\{a,b\}^*: w = u^n, u \in \{a,b\}^+, n \geq 2\}$

The diagram I had planned to make was a very simple one, but I don't know if it would meet the goal of making the machine Turing-decidable.

The problem can be solved with non-deterministic and multiple tapes.

Sebastian
  • 31
  • 1
    Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. – Community Jul 14 '22 at 19:53
  • Thanks for updating to use MathJax. As a hint to solving the problem: you need to find out what $u$ is? You know that $u$ must be an initial substring of the input $w$ and that $w$ must then be what you get by concatenating copies of $u$. So a simple approach is to try each initial substring $u$ of $w$ and see if $w$ is the concatenation of copies of $u$. – Rob Arthan Jul 14 '22 at 20:46

0 Answers0