how to a draw a turing machine that has the same number of a's ,b's and c's

SOMELANGUAGE = {abc acb bac bca cab cba aabbcc aabcbc}


1 Answer 1


Let's focus on the procedure here. So we start with the tape-head at the far left. It proceeds right looking for the first unmarked $A$. When it finds it, it marks it. The TM then moves the tape head to the far left and starts looking for an unmarked $B$. If it finds one, it marks it. Otherwise, it rejects. It then does the same for a $C$. After marking the $C$, the Turing Machine checks for an unmarked $A$ again. If no such $A$ is found, it checks for any unmarked characters. If it finds any, it rejects. Otherwise, it accepts.

Start with this to formalize the state machine diagram.

  • $\begingroup$ how would I do the tape first ? something like this |a|b|c|a|b|c|a|b|c|null|null|null| or just |a|b|c|null|null|null|...I think this should would work |a|a|b|b|c|c|null|null|null| ...because it has same amount now $\endgroup$
    – Bob
    Apr 16, 2014 at 17:51
  • $\begingroup$ What do you mean "how would you do the tape?" Are you asking how to draw the tape? Note that my procedure will accept strings such as $cab$ or $bca$, just in case that wasn't clear. $\endgroup$
    – ml0105
    Apr 16, 2014 at 17:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .