[Overview] [Previous] [Next]

Enumerating Strings in a Language

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 (think of a string as a number in an |sigma|-ary number system). The strings in a language form a subset of the set of all strings over sigma. But can we 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 sigma* 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. We do this by "time sharing." Here's how:

 W := null set;  N := 0;
 for i := 1 to aleph0 do {
   add the next string in sigma* to set W;
   initialize a Turing machine for this new string;
   for each string in set W do {
     let the Turing machine for it make one move;
     if the Turing machine halts {
       accept or reject the string as appropriate;
       if the string is accepted {
         N := N + 1;
         let this be string N of the language;
             remove the string from set W;

Copyright 1996 by David Matuszek
Last modified Apr 1, 1996