next up previous
Next: About this document Up: LANGUAGE GENERATED BY M Previous: Pair Genetator: :

Characterization of Recursive Sets by Generators

Lemma: If L is recursive, then there is a generator for L that prints the words of L in canonical order. Converse If L is generated in canonical order, then L is recursive.

figure315

Does this work if L is finite?

L is regular tex2html_wrap_inline535 an FA.



Sushil Prasad
Thu Jul 30 17:32:57 EDT 1998