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?

  • $\begingroup$ In general you can't. Partly the question is unclear: the Turing machine is itself a description of $L(M)$, so you need to say what different kind of description your would prefer. But also the problem in general is undecidable. For example, even to answer the question “Here is $M$; is $L(M)$ empty?” is undecidable in general. You need to use some kind of informal reasoning , arguing that state 7 is for skipping rightwards over a block of as, or whatever. $\endgroup$ – MJD May 23 '16 at 19:00
  • $\begingroup$ @MJD Understood. And say you would want $L(M)$ in the format $L(M) = \{a^{2n}b^{n}c^{n} \mid n \in ℕ \}$ what steps could I take, with the given information to derive that? $\endgroup$ – marcusvb May 23 '16 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.