[Math] how to a draw a turing machine that has the same number of a’s ,b’s and c’s

computer scienceformal-languagesturing-machines

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}

Best Answer

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.

Related Question