Computer Science 456/656
Automata and Formal Languages
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.
-
Addition:
- 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.