0
$\begingroup$

im looking for a formal proof to demonstrate that all regular language is in L (logarithmic space). I deduced that all regular languages has a DFA that accept them, so if i find a way to transform all DFA to a L-Space Turing Machine, i would be able to prove this.

Thanks for helping.

$\endgroup$
4
  • $\begingroup$ In fact, you don’t need any space at all. $\endgroup$ May 29 '20 at 18:27
  • $\begingroup$ Thanks for answering. I dont know if im understanding your answer, but you mean that i can prove this with a Turing Machine that only reads right? It is not necessary to write nothing in any tape. $\endgroup$
    – John
    May 29 '20 at 18:39
  • $\begingroup$ That’s exactly right. $\endgroup$ May 29 '20 at 18:51
  • $\begingroup$ Every regular language has a finite state machine. You can turn that reasonably easy into a Turing machine. $\endgroup$
    – gnasher729
    May 29 '20 at 21:06

This site is temporarily in read only mode and not accepting new answers.

Browse other questions tagged .