1

I am a trying to prove that every regular language is decidable.

So in order to prove that I am trying to show that I can move from deterministic finite automaton (DFA) to a Turing decidable machine.

So I am not sure how to construct a Turing machine that simulates the original automate (DFA).

The states (in the automate and the Turing machine ) will be similar off course.. but I am not sure how to continue..

Thanks in advance. Shiran

Xoff
  • 10,310
Ohad
  • 111
  • What did you try ? This is a homework question. – Xoff Nov 23 '13 at 12:33
  • 1
    I took the mathematical definition of DFA and I tried to construct the mathematical definition of the Turing machine... I got stuck in when I tried to represent the halt state of the Turing machine.. – Ohad Nov 23 '13 at 12:35
  • you just need to write something on the tape if the word is accepted and nothing (or something else) if the word is not accepted. You need to explain what kind of Turing machine you need : one tape/2 tapes, what is the output… – Xoff Nov 23 '13 at 13:19
  • I think I got you..Could it be so simple ? and how do I create the table of Turing ? is it just by coping the the possible states(pairs of state and letter) from the DfS itself? I guess it's too abstract for me. – Ohad Nov 23 '13 at 13:31
  • yes, it is very simple :) You have to take care reading the word on the tape. – Xoff Nov 23 '13 at 13:46

0 Answers0