Turing machine for the language $a^nb ^{2n}c^{3n}$

Question

How can we give a Turing Machines that accept following language.

$$a^nb^{2n}c^{3n}$$

I am allowed to use also pseudo-code descriptions (i.e. high level descriptions of movements of r/w head).

Answer 1

you can just go over the word and replace every letter that you found the corresponding sequnces of other letter tag (a->a' , b->b' , c->c') then at each stage:

• if all the letters are tagged accept

• tag the first untagged a, if there's none reject (that means that there's at least one letter that's not tagged)

• go to the first and second untagged b and tag them, if there's only one or none untagged b's reject.
• go to the first second and third untagged c's and tag them, if there's only two, one or none untagged c's reject.