We have regular expression for DFA and NFA, at the same time, we have CFG for PDAs, What do we have for Turing Machine? If this questions is too obvious, please points me some reading, I am just learning Introduction to the theory of computation_third edition - Michael Sipser myself.

  • $\begingroup$ We have unrestricted grammars, which describe r.e. languages. See also this question. $\endgroup$ – Yuval Filmus May 20 '18 at 21:48
  • $\begingroup$ Can you explain the relationship between title and body of your question? Are there two different questions in there? $\endgroup$ – reinierpost May 21 '18 at 9: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.