turing-machinesnon-deterministic

Non deterministic Turing machine for words that are a repetition of a subword


I am new to NDTM, but I do understand the concept of a turing machine. when it comes to NDTM I get a little confused, I m supposed to develop a NDTM for language {a,b,c} and

L = {w ∈ Σ*| Ǝv ∈ Σ*, Ǝn >= 2 with w = v (to the power of) n }

First thing that I want to know is how to read L, for example what is the meaning of Ǝ. I do understand that a NDTM gives twp possibilities of one outcome, like for example for a: we would have with a and without a if i am correct, Can someone help me fugure this out?


Solution

  • This should be marked as "Homework" I think.

    Ǝ is "there exists"
    Σ is "the set of symbols in the language" ({a, b,c}) in this case
    is "element of"

    Now that we have that, we can read this language. So L is the set of words w in {a, b, c}* such that there exists a word v and there exists a n >= 2 such that w is a repetition of v n times. E.g. ababab = (ab)^3 ∈ L.

    Now you want to come up with a Turing machine, M, to represent this language, so you have to consider:

    We can see that a is not in L because n >= 2 which implies that the length of v^n is at least 2 (0 in the case of the empty string though, which is an outlier). Similarly for b and c. With that consideration and the knowledge that n >= 2, figure out what words are not accepted (e.g. consider b, abc, cab, cca, etc.).