collection of legal English words is a set of strings over the alpliabet tliat consists of all the letters. Another example is C, or any other programming language, where the legal programs are a subset of the possible strings that can be formed from the alphabet of the language. This alphabet is a subset of the ASCII characters. The exact alphabet may differ slightly among different programming languages, but generally includes the upper- and lower-ca.se letters, the digits, punctuation, and mathematical symbols.

However, there are also many other languages that ajjpear when we study automata. Some arc abstract examples, such as:

1. The language of all strings consisting of n Os followed by n Ts, for some n>0: {e,01,00ll,000111,...}.

2. The set of strings of Os and Is with an equal number of each:

{6,01,10,0011,0101,1001,...}

3. The set of binary numbers whose value is a prime:

{10,11,101,111,1011,...}

4. £ is a language for any alphabet E.

5. 0, the empty language, is a language over any alphabet.

6. {e}, the language consisting of only the empty string, is also a language over any alphabet. Notice that 0 (e}; the former has no strings and the latter has one string.

The only important constraint on what can be a language is that all alphabets are finite. Thus languages, although they can have an infinite number of strings, are restricted to consist of strings drawn from one fixed, finite alphabet.

1.5,4 Problems

In automata theory, a problem is the question of deciding whether a given string is a member of some particular language. It turns out, as we shall see, that anything we more colloquially call a problem can be expressed as membership in a language. More precisely, if E is an alphabet, and L is a language over E, then the problem L is:

Given a string w in E*. decide whether or not w is in L.

Example 1.26: The problem of testing primaUty can be expressed by the language Lp consisting of all binary strings whose value as a binary number is a prime. That is, given a string of Os and Is, say yes if the string is the binary representation of a prime and say no if not. For some strings, this

Set-Formers as a Way to Define Languages

It is common to describe a language using a set-former :

{w I something about w)

This expression is read the set of words w such that (whatever is said about w to the right of the vertical bar). Examples are:

1. {w \w consists of an equal number of Os and 1 s }.

2. (uj I w is a binary integer that is prime }.

3. {uj I is a syntactically correct С program }.

It is also common to replace w by some expression with parameters and describe the strings in the language by stating conditions on the parameters. Here are some examples; the first with parameter n, the second with parameters i and j:

1. {0 1 I Ti > 1}. Read the set of 0 to the n 1 to the n such that n is greater than or equal to 1, this language consists of the strings (01,0011,000111,...}. Notice that, as with alphabets, we can raise a single symbol to a power n in order to represent n copies of that symbol.

2. {OV I 0 < г < j). This language consists of strings with some Os (possibly none) followed by at least as many Is.

decision is easy. For instance, 0011101 cannot be the representation of a prime, for the simple reason that every Integer except 0 has a binary representation that begins with 1. However, it is less obvious whether the string 11101 belongs to Lp, so any solution to this problem will have to use significant computational resources of some kind: time and/or space, for example. □

One potentially unsatisfactory aspect of our definition of problem is that one commonly thinks of problems not as decision questions (is or is not the following true?) but as requests to compute or transform some input (find the best way to do this task). For instance, the task of the parser in a С compiler can be thought of as a problem in our formal sense, where one is given an ASCII string and asked to decide whether or not the string is a member of Lc, the set of valid С programs. However, the parser does more than decide. It produces a parse tree, entries in a symbol table and perhaps more. Worse, the compiler as a whole solves the problem of turning a С program into object code for some

Is It a Language or a Problem?

Languages and problems are really the same thing. Which term we prefer to use depends on our point of view. When we care only about strings for their own sake, e.g., in the set {0 1 j n > 1}, then we tend to think of the set of strings as a language. In the last chapters of this book, we shall tend to assign semantics to the strings, e.g., think of strings as coding graphs, logical expressions, or even integers. In those cases, where we care more about the thing represented by the string than the string itself, we shall tend to think of a set of strings as a problem.

machine, which is feur from simply answering yes or no about the validity of a program.

Nevertheless, the definition of problems as languages has stood the test of time as the appropriate way to deal with the importjmt questions of complexity theory. In this theory, we are interested in proving lower bounds on the complexity of certain problems. Especially importtmt are techniques for proving that certain problems cannot be solved in an amount of time that is less than exponential in the size of their input. It turns out that the yes/no or language-based version of known problems are just as hard in this sense, as their solve this versions.

That is, if wc can prove it is hard to decide whether a given string belongs to the language Ly of \alid strings in programming language X, then it stands to reason that it will not be easier to translate programs in language X to object code. For if it were easy to generate code, then we could run the translator, and conclude that the input was a valid member of Lx exactly when the translator succeeded in producing object code. Since the final step of determining whether object code has been produced caimot be hard, we can use the fast algorithm for generating the object code to decide membership in Lx efficiently. We thus contradict the assumption that testing membership in Lx is haid. We liave a proof by contradiction of the statement if testing membership in Lx is hard, then compiling programs in programming language A is hard.

This technique, showing one problem hard by using its supposed efficient algorithm to solve efficiently another problem that is already known to be hard, is called a reduction of the second problem to the first. It is an essential tool in the study of the complexity of problems, and it is facilitated greatly by our notion that problems are questions about membership in a language, rather than more general kinds of questions.