Cheap and Secure Web Hosting Provider : See Now

Are all functions with constant space complexity in $REG$?

, , No Comments
Problem Detail: 

The Wikipedia article about regular languages mentions that $DSPACE(O(1))$ is equal to $REG$. Can I conclude from this that every function in $R$ with constant space complexity is in $REG$?

Asked By : Peter
Answered By : adrianN

A regular automaton can do anything a Turing machine can do, as long as the TM uses only O(1) memory. This is because with finite memory, the number of possible states the TM can be in is also finite (It's the number of possible tape contents * the number of possible head positions * the number of states of your TM). You can encode the whole computation graph as one big finite automaton.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback