A language is “recursively enumerable” if there exists a Turing machine
that accepts every string of the language, and does not accept strings that are
not in the language. Strings which are not in the language may be rejected or
may cause the Turing machine to go into an infinite loop.
Every Recursive language is also recursively enumerable. But it is not
clear if every recursively enumerable language is also recursive.
Turing Machines are not “recursive”. The terminology is borrowed from
recursive function theory.
4.4.3 Enu mer ating Strings in a Lan guage
To enumerate a set is to place the elements of the set in a one-to-one
correspondence with the natural numbers. The set of all strings over an
alphabet is denumerable. Let us assume that a string is a number is an | |
Σ -ary
number system. The strings in a language from a subset of the set of all strings
over Σ. But is it possible to enumerate the strings in a language?
If a language is recursive, then there exists a Turing machine for it that is
guaranteed to halt. We can generate the strings of Σ
* in a shortest first order to
guarantee that every finite string will be generated, test the string with the
Turing machine, and if the Turing machine accepts the string, assign that string
the next available natural number. We can also enumerate the recursively
enumerable languages. We have a Turing machine that will halt and accept any
string that belongs to the language; the trick is to avoid getting hung up on
strings that cause the Turing machine to go into an infinite loop. This is done
using “Time sharing”. Let us illustrate this now.
w
N
:
; :
;
= ∅
= 0
for i: = 1
0
to χ do {
add the next string in Σ
* to set W;
ini tial ize a Turing machine for this new string;
for each string in set W do {
let the Turing machine for it make one more;
if the Turing machine halts {
accept or reject the string as appro pri ate;
if the string is accepted {
N: = N + 1;
198
Theory of Automata, Formal Languages and Computation
Recursively
Enumerable
Languages
Recursive
Languages