Computer Science 456/656
Automata and Formal Languages

What is a language?

Why do we introduce the concept "language" in a course about the theory of computation?

The answer is simple and striking:

Every problem that has a mathematical definition is a language problem.

The above statements seems quite radical, but it is simple to explain by giving a few examples.

Let L1 be the language of all non-empty strings of decimal digits.
Let L2 be the language of all two term addition problems, that is, L2 consists of all strings of the form x+y, where x and y are in L1.
The function which we call "addition" has domain L2 and range L1, and, for example, takes the string 34+689 to the string 723.
The problem of "adding" is then the problem of computing this function.
Existence of a Cycle in a Directed Graph:
Consider the following problem. Given a directed graph G, does G contain a cycle?
We can encode G as a string. (Think: if you were to write a computer program to solve this problem, you would take as input some sort of file which encodes G. This file is in fact a string of symbols.)
We can then define L1 to be the language of all encodings of directed graphs, and L2 to be the language of all encodings of cyclic directed graphs.
Our problem is then, given a string w in L1, is w in L2?
Your Computer:
Your computer has various components, each of which must be in a given state at a given time. The current state of each component could be described (i.e., encoded) as a string of symbols. The state of the entire computer could be described by a single (long) string of symbols obtained by concatenating the strings describing the states of the various components. Such a string we call the current id of your computer. At each computational step the id of your computer changes. This change each step can be viewed as a function from the language of all possible ids of your computer to itself.
The question of what your computer can compute can be phrased in terms of this function on the language of all the ids of your computer.
Of course, your computer is connected to external input/output devices, and the states of these devices must be incorporated into the id.