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$ May 20, 2018 at 21:48
  • $\begingroup$ Can you explain the relationship between title and body of your question? Are there two different questions in there? $\endgroup$ May 21, 2018 at 9:18


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.