How to derive Turing Machine language?

154 Views Asked by At

Say you're given a TM (Turing Machine) $M = (Q, \Sigma, \Gamma, \vdash, \sqcup, \Diamond)$ and given the partial $\delta$:

$$\begin{array}{c|cc} \delta&\vdash&a&b&c&\sqcup&\Diamond\\ \hline 1&(1,\vdash,R)&(2,\vdash,R)&(r,-,-)&(r,-,-)&(t,-,-)&(6,\Diamond,R)\\ 2&-&(3,\vdash,R)&(r,-,-)&(r,-,-)&(t,-,-)&(6,\Diamond,R)\\ 3&-&(3,a,R)&(4,\Diamond,R)&(r,-,-)&(r,-,-)&(3,\Diamond,R)\\ 4&-&(r,-,-)&(4,b,R)&(5,\Diamond,L)&(r,-,-)&(4,\Diamond,L)\\ 5&(1,\vdash,R)&(5,a,L)&(5,b,L)&-&-&(5,\Diamond,L)\\ 6&-&(r,-,-)&(r,-,-)&(r,-,-)&(t,-,-)&(6,\Diamond,R)\\ t&-&-&-&-&-&-\\ r&-&-&-&-&-&- \end{array}$$

What steps can I take to get $L(M)$?

So far I have drawn $M$, and I can think of strings which will make it halt, but I have no idea how to get $L(M)$

I know $L(M) = \{a^{2n}b^{n}c^{n} \mid n \in ℕ \}$. What steps do I take to get there?