-2
$\begingroup$

Can every recursively enumerable language be defined with regular expression?

I came across this question, when studying for my test: Prove that for any finite language $L$, there is a Turing machine $M$ with $L(M) = L$ with time and space complexity $t(n) \leq n+1, s(n) \leq n+2$, respectively ($n$ is the length of the input word).

My proof goes as follows:

We can create a DFA from a regular expression defining the language. Then we read the input symbol by symbol and output YES, if we finished in a final state or NO otherwise.

Every DFA can be transformed into a TM where every transition of the DFA corresponds to one transition of the TM. It is obvious that we only need $n+1$ steps to read the input (+1 for the blank in the end) and $s+1$ cells.

However, I am not sure, if I can assume here, that there is a regular expression for every recursively enumerable language. And if not, would my proof be still valid? Can I create a DFA for arbitrary RE language?

$\endgroup$
3
$\begingroup$

Of course you can't create a DFA for every RE language. The language $\{0^n1^n\mid n\geq 0\}$ is well known to not be regular and is obviously RE.

But you don't need that for this question. The question refers to finite languages, which are all regular. Also, given that finite languages are regular, they can be decided by a DFA, which is a Turing machine that uses zero storage space (so much less than the $O(n)$ allowed by the question) and which always moves the head forwards.

$\endgroup$
  • $\begingroup$ Thanks, I kind of missed the fact that finite languages are all regular! $\endgroup$ – Smajl Oct 23 '14 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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