2
$\begingroup$

I came across following TM state diagram accepting language $\{a^nb^nc^n | n\geq 0\}$ enter image description here

After trying out some valid and invalid strings of various lengths, I was surprised how it is designed to accept language exactly as specified.

Now I have started wondering how I can come up with such TM design given any language specification. When I learned FAs and NFAs, I came across some minimal regexes ($\epsilon$, a, a+b, a*, ab) whose FAs are well known. Then we can combine these FAs to come up with more FAs/NFAs for more complex regexes / languages. Is there any such standard way / approach to come up with TM design for given language? Or is it pure creativity/intuition to design approach.

$\endgroup$
4
  • $\begingroup$ I would be surprised if there where a large enough body of examples for coming up with TMs that such design patterns could emerge. Unlike DFAs having concrete TMs for given problems doesn't seem very useful in practice. $\endgroup$
    – adrianN
    Jan 10 '17 at 8:42
  • $\begingroup$ As far as coming up with a TM is the same as programming on a computer, do you think there is a standard approach for all problems? Why then we need programmers at all? For easy languages there are easy TMs which are considered classical, but you can easily define sophisticated languages. $\endgroup$
    – Eugene
    Jan 10 '17 at 20:28
  • $\begingroup$ Moreover, answering the question about TM which solves SAT (determ. of course) would answer the question P=NP, and if there were a standardized way to do this, we wouldn't be struggling for so long. $\endgroup$
    – Eugene
    Jan 10 '17 at 20:30
  • $\begingroup$ Arghhh...right then, its a skill, programming is the skill...I was unnecessarily generalizing what was possible for FAs/NFAs should also be possible for TMs. May be sudden concentrated overdose of the subject made me forget this obvious fact. $\endgroup$
    – anir
    Jan 11 '17 at 20:18

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.