0
$\begingroup$

Suppose an enumerator E can enumerate some language L in a finite amount of time (3 days, 3 hours, etc.). What properties does this language have?

My guess:

  • L is finite, so L is a context-free language.
  • Since L is a context-free language, L is also decidable
  • Since L is decidable, L is also Turing-recognizable and co-Turing recognizable

My Questions:

  • Is L also a regular language?
  • A theorem says that:

A language is Turing-recognizable iff some enumerator enumerates it

  • Is there anything more or less we can say about L, compared to a Turing-recognizable language?
$\endgroup$
2
1
$\begingroup$

If the language can be enumerated in finite time, then the language itself is finite. Almost all natural classes of languages include all finite languages: they're regular, context-free, decidable, recursively enumerable, co-RE, ...

I'm not sure what else you'd want to say about finite languages compared to RE languages. It's enough to say that the language is finite; for any property you might be interested in, it's usually very straightforward to prove that finite languages do or do not have that property.

$\endgroup$
1
  • $\begingroup$ Thank you! So the very least you could say is that it's decidable (and therefore RE, and co-RE)? $\endgroup$ – user3400223 Dec 13 '16 at 20:53

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.