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.
$\begingroup$
$\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$– jmiteJul 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$– user67584Jul 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$– jmiteJul 29, 2013 at 21:37
-
$\begingroup$ I solved it..really appreciated it.. $\endgroup$– user67584Jul 29, 2013 at 21:46
-
$\begingroup$ @user67584 You should add your answer here, both for review and for later visitors. $\endgroup$– Raphael ♦Jul 30, 2013 at 10:27
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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?
$\begingroup$
$\endgroup$
$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$.
