1
$\begingroup$

L = {x=y ⊕ z|x, y, z are binary integers, and x is the XOR of y and z}

is non-regular, i.e., no FA exists that could recognize the language. How can I give an implementation level description of a TM that decides on L?

$\endgroup$
1
$\begingroup$

There is an important gap between human reasoning ("high level") and the formal definition of a Turing Machine ("low level"). If you are approaching these exercises for the first time and you are not yet familiar with TMs, what I recommend is to write down a pseudocode description of the algorithm which is nothing more than a high level description of the Turing machine itself) and then to "break up" the algorithm into smaller entities, until the transition function of the machine is achieved.

In the case of your example you can consider $x$, $y$ and $z$ as binary encodings of integers, then you need a function that does the following:

  1. Read the input $($$x$, $y$, $z$$)$
  2. Compute $y \oplus z$
  3. Compare $($$y \oplus z$$)$ to $(x)$

If the equality in point 3 is verified, accept the language. This TM will always accept membership in your language $L$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You can also avoid explicitly computing the XOR. $\endgroup$ – Yuval Filmus Oct 21 '19 at 18:26

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.