Im trying to learn the concept of turing machines.I have understood the basic stuff like its a simple mathematical model of a computer and its parts.Now im asked to create a turing machine.

Design a turing machine that accept strings belonging to the language
(a + b)* from the alphabet (a, b)

Can someone describe to me how it is done?

  • $\begingroup$ What does the "+" denote here? $\endgroup$ – mrp Dec 7 '14 at 11:35
  • $\begingroup$ @mrp Its a Terminal $\endgroup$ – techno Dec 7 '14 at 11:41
  • $\begingroup$ So you want to make a Turing machine that accepts everything? $\endgroup$ – Henning Makholm Dec 7 '14 at 12:16
  • 1
    $\begingroup$ The plus is NOT a terminal, $(a+b)^*$ is a regular expression meaning that you choose $a$ or $b$ and then take the Kleene star to iterate this. Hence the expression stands for all strings over the alphabet $\{a,b\}$. $\endgroup$ – MHS Dec 8 '14 at 13:08
  • 1
    $\begingroup$ Now to construct the Turing machine, what do you know about Turing machines? How would you start constructing one piece by piece (selecting the tape alphabet, machine states, transition function/relation etc.)? $\endgroup$ – MHS Dec 8 '14 at 13:09

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.