0
$\begingroup$

Does the question mean draw a Turing machine that takes input with any number of a's and any number of b's (eg. aaabbb, ab, abababab, etc.). The turing machine should only then accept or reject the input and should not be stuck in loop?

Example of a drawing to answer the question: enter image description here

$\endgroup$
0
$\begingroup$

A decider is a TM that halts (i.e either accepts or rejects) on any input.

The TM that is requested should accept any input that has an odd number of $a$s and an odd number of $b$s, and should reject all other input.

The TM you have depicted does not meet the requirements (HINT: consider the string $aa$).

$\endgroup$
0
$\begingroup$

Yes. "Words over the alphabet $\Sigma=\{a,b\}$" means that the input can be any string containing $a$s and $b$s in any order, and "decide" means that the machine must halt (accept or reject) on every input, and not get into an infinite loop.

$\endgroup$

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.