0
$\begingroup$

This is a practice problem for a midterm in a class I'm taking:

Given a regular language $L$, describe formally a Turing machine that recognize $L$.

I'm not sure how I should do that.

$\endgroup$
5
  • 4
    $\begingroup$ What have you tried? Where did you get stuck? What other models do you know of that can accept regular languages, and how could you simulate them with a Turing Machine? $\endgroup$ Commented Jul 29, 2013 at 20:02
  • $\begingroup$ My ideal is since every regular language has a DFA..so, the problem is how Turing Machine simulates DFA? Am I right? $\endgroup$
    – user67584
    Commented Jul 29, 2013 at 20:08
  • 1
    $\begingroup$ That's right. Now, a DFA consists of 5 parts: state-set, alphabet, initial-state, final-state-set and transition-function. What does a Turing Machine consist of, and which would correspond to each part of a DFA? $\endgroup$ Commented Jul 29, 2013 at 21:37
  • $\begingroup$ I solved it..really appreciated it.. $\endgroup$
    – user67584
    Commented Jul 29, 2013 at 21:46
  • $\begingroup$ @user67584 You should add your answer here, both for review and for later visitors. $\endgroup$
    – Raphael
    Commented Jul 30, 2013 at 10:27

2 Answers 2

3
$\begingroup$

Hint: A DFA consists of 5 parts: state-set, alphabet, initial-state, final-state-set and transition-function. What does a Turing Machine consist of, and which would correspond to each part of a DFA?

$\endgroup$
0
$\begingroup$

$L$ is regular and so accepting by a dfa. for each transition $\delta(p,a)=q$ in the dfa accepting $L$ let $\delta(p,a)=(q,a,R)$ for define a TM which accepting $L$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.