I am building a turing machine that recognizes the following element distinctness problem and I also need the state transition diagram for it, and I just realized after you compare the first two strings and you already marked the first string with let's say 'x' to denote that it's been checked, you lose the string's contents so I was wondering how do we produce the stack on a state transition diagram?

Like if I want to remember the contents of a string before I overwrite them with a tape symbol, how to represent that in the diagram?

E ={#x1#x2#···#xl|each xi ∈{ 0,1}∗ and xi ̸= xj for each i̸= j}.

Like if x1 and x2 are not equal, then if they had one character in common, then the first character in x1 would be marked x, but I want to remember that character for when I compare with x3. How do I represent the stack and then reproduce the stack elements in a traditional state transition diagram.

  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – dkaeae Apr 1 at 9:36

Your Answer

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

Browse other questions tagged or ask your own question.