How can I design a Turing machine that takes string $a^n b a^m$ and check if $n>m$ then convert the string to $a^{n-m}$, otherwise reject it?


Start with placing tape over $b$, then go to the rightmost $a$, put blank, go back to $b$ and delete the rightmost $a$.
Every time you scratch out $a$s on both sides, $n - m$ does not change until one side is blank.
Check if the left side is not empty, delete $b$ (and if it is required, go back to the beginning of the tape) and accept, otherwise reject.

  • $\begingroup$ Hi @Evil thanks a lot for your response . it's very helpful for me. $\endgroup$ – yaodao vang Oct 7 '18 at 15:47

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.