Enumerating Strings In A Language

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. Let us assume that a string is a number is an | S| -ary number system. The strings in a language from a subset of the set of all strings over S. 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 S* 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 c do {

add the next string in S* 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 more;

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;

}

Non-recursively Enumerable Languages: A Language is a subset of S*. A language is “any” subset of S*. We have shown that Turing machines are enumerable. Since recursively enumerable languages are those whose strings are accepted by a Turing machine, the set of recursively enumerable languages is also enumerable. The power set of an infinite set is not enumerable i.e., it has more than c0 subsets. Each of these subsets represent a language. Hence there should be languages that are not computable by a Turing machine.

According to Turing Thesis, a Turing machine can compute any effective procedure. Therefore there are languages that cannot be defined by any effective procedure. It is possible to find a non-recursively enumerable language X by a process called “diagonalisation”.