Non deterministic Turing machine

Question

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?

Answer 1

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:

• When do we reject a word (what is our rejection state, what is on the stack)
• When do we accept a word (what is our accepting state, what is on the stack)
• How do we guarantee that M terminates.

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.).