A New Approach to Formal Language Theory by Kolmogorov Complexity.
We present a new approach to formal language theory using Kolmogorov complexity. The main results presented here are an alternative for pumping lemma(s), a new characterization for regular languages, and a new method to separate deterministic context-free languages and nondeterministic context-free languages. The use of the new "incompressibility arguments" is illustrated by many examples. The approach is also successful at the high end of the Chomsky hierarchy since one can quantify nonrecursiveness in terms of Kolmogorov complexity.
Introduction
It is feasible to reconstruct parts of formal language theory using algorithmic
information theory (Kolmogorov complexity). We provide theorems on how to
use Kolmogorov complexity as a concrete and powerful tool. We do not just want
A preliminary version of part of this work was presented at the 16th International Colloquium
on Automata, Languages, and Programming, Stresa, Italy, July 1989.
y Supported in part by National Science Foundation Grant DCR-8606366, Office of Naval
Research Grant N00014-85-k-0445, Army Research Office Grant DAAL03-86-K-0171, and by
operating grants OGP-0036747 and OGP-046506. Part of the work was performed
while he was with the Department of Computer Science, York University, North York, Ontario,
Canada. Address: Computer Science Department, University of Waterloo, Waterloo, Ontario,
Canada N2L 3G1. Email: mli@math.waterloo.edu
z Partially supported by NSERC International Scientific Exchange Award ISE0046203, and
by NWO through NFI Project ALADDIN under Contract number NF 62-376. Address: CWI,
Kruislaan 413, 1098 SJ Amsterdam, The Netherlands. Email: paulv@cwi.nl
to introduce fancy mathematics; our goal is to help our readers do a large part
of formal language theory in the most essential, usually easiest, sometimes even
obvious ways. In this paper it is only important to us to demonstrate that the
application of Kolmogorov complexity in the targeted area is not restricted to
trivialities. The proofs of the theorems in this paper may not be easy. However,
the theorems are of the type that are used as a tool. Once derived, our theorems
are easy to apply.
1.1 Prelude
The first application of Kolmogorov complexity in the theory of computation
was in [19, 20]. By re-doing proofs of known results, it was shown that static,
descriptional (program size) complexity of a single random string can be used
to obtain lower bounds on dynamic, computational (running time) complexity.
None of the inventors of Kolmogorov complexity originally had these applications
in mind. Recently, Kolmogorov complexity has been applied extensively
to solve classic open problems of sometimes two decades standing, [16, 12, 9, 10].
For more examples see the textbook [13].
The secret of Kolmogorov complexity's success in dynamic, computational
lower bound proofs rests on a simple fact: the overwhelming majority of strings
has hardly any computable regularities. We call such a string 'Kolmogorov ran-
dom' or `incompressible'. A Kolmogorov random string cannot be (effectively)
compressed. Incompressibility is a noneffective property: no individual string,
except finitely many, can be proved incompressible.
Recall that a traditional lower bound proof by counting usually involves all
inputs of certain length. One shows that a certain lower bound has to hold
for some 'typical' input. Since an individual typical input is hard (sometimes
impossible) to find, the proof has to involve all the inputs. Now we understand
that a typical input of each length can be constructed via an incompressible
string. However, only finitely many individual strings can be effectively proved
to be incompressible. No wonder the old counting arguments had to involve
all inputs. In a proof using the new 'incompressibility method', one uses an
individual incompressible string that is known to exist even though it cannot
be constructed. Then one shows that if the assumed lower time bound would
not hold, then this string could be compressed, and hence it would not be
incompressible.
1.2 Outline of the Paper
The incompressibility argument above also works for formal languages and automata
theory proper. Assume the basic notions treated in a textbook like
The first result is a powerful alternative to pumping lemmas for regular
languages. It is well known that not all nonregular languages can be shown to be
nonregular by the usual uvw-pumping lemma. There is a plethora of pumping
lemmas to show nonregularity, like the 'marked pumping lemma', and so on.
In fact, it seems that many example nonregular languages require their own
special purpose pumping lemmas. Comparatively recently, [8, 22, 4], exhaustive
pumping lemmas that characterize the regular languages have been obtained.
These pumping lemmas are complicated and complicated to use. The last
reference uses Ramsey theory. In contrast, using Kolmogorov complexity we
give a new characterization of the regular languages that simply makes our
intuition of 'finite state'ness of these languages rigorous and is easy to apply.
Being a characterization it works for all non-regular languages. We give several
examples of its application, some of which were quite difficult using pumping
lemmas.
To prove that a certain context-free language (cfl) is not deterministic context-free
(dcfl) has required laborious ad hoc proofs, [7], or cumbersome-to-state and
also difficult-to-apply pumping lemmas or iteration theorems [5, 25]. We give
necessary (Kolmogorov complexity) conditions for dcfl, that are very easy to ap-
ply. We test the new method on several examples in cfl \Gamma dcfl, which were hard
to handle before. In certain respects the KC-DCFL Lemma may be more powerful
than the related lemmas and theorems mentioned above. On the high end
of the Chomsky hierarchy we present, for completeness, a known characterization
of recursive languages, and a necessary condition for recursively enumerable
languages.
From now on, let x denote both the natural number and the xth binary string
in the sequence 0; That is, the representation '3' corresponds
both to the natural number 3 and to the binary string 00. This way we
obtain a natural bijection between the nonnegative integers N and the finite
binary strings f0; 1g   . Numerically, the binary string corresponds to
the integer
We use notation l(x) to denote the length (number of bits) of a binary
string x. If x is not a finite binary string but another finite object like a finite
automaton, a recursive function, or a natural number, then we use l(x) to
denote the length of its standard binary description. Let h\Delta; \Deltai : N \Theta N ! N be
a standard recursive, invertible, one-one encoding of pairs of natural numbers
in natural numbers. This idea can be iterated to obtain a pairing from triples
of natural numbers with natural numbers hx;
Any of the usual definitions of Kolmogorov complexity in [11, 20, 13] will do
for the sequel. We are interested in the shortest effective description of a finite
object x. To fix thoughts, consider the problem of describing a string x over 0's
and 1's. Let T be the standard enumeration of Turing machines. Since
computes a partial recursive function we obtain the standard
enumeration recursive functions. We denote OE(hx; yi) as
OE(x; y). Any partial recursive function OE from strings over 0's and 1's to such
strings, together with a string p, the program for OE to compute x, such that
is a description of x. It is useful to generalize this idea to the
conditional version: OE(p; x such that p is a program for OE to compute x,
given a binary string y for free. Then the descriptional complexity C OE of x,
relative to OE and y, is defined by
or 1 if no such exists.
For a universal partial recursive function OE 0 , computed by the universal
Turing machine U , we know that, for each partial recursive function OE, there is
a constant c OE such that for all strings x; y, we have OE 0 (i;
We fix a reference universal function OE 0 and define
the conditional Kolmogorov complexity of x given y as
The unconditional Kolmogorov complexity of x is
denotes the empty string
Since there is a Turing machine that just copies its input to its output
we have C(xjy) - O(1), for each x and y. Since there are 2 n binary
strings of length n, but only 2 descriptions d, it follows
that C(x) - l(x) for some binary string x of each length. We call such strings
incompressible or random. It also follows that, for any length n and any
binary string y, there is a binary string x of length n such that C(xjy) - l(x).
Considering C as an integer function, using the obvious one-one correspondence
between finite binary words and nonnegative integers, it can be shown that
C(x) !1 for x !1. Finally, C(x; y) denotes C(hx; yi).
Example 1 (Self-Delimiting Strings) A prefix code is a mapping from finite
binary code words to source words, such that no code word is a proper
prefix of any other code word. We define a particular prefix code.
For each binary source word define the code word - x by
The string x 0 is called the self-delimiting code of x.
which corresponds to binary string '10', and
is the self-delimiting code of '01011'.
1 Similarly, we define the complexity of the xth partial recursive function OE conditional to
the yth partial recursive function / by
The self-delimiting code of a positive integer x requires
bits. It is easy to verify that logarithms are base 2
unless otherwise noted. For convenience, we simply denote the length l(x) of a
natural number x by 'log x'. 3
Example 2 (Substrings of incompressible strings) Is a substring of an
incompressible string also incompressible? A string can be specified
by a short description for v of length C(v), a description of l(u), and the literal
description of uw. Moreover, we need information to tell these three items apart.
Such information can be provided by prefixing each item with a self-delimiting
description of its length. Together this takes C(v) bits.
Hence,
Thus, if we choose x incompressible, C(x) - l(x), then we obtain
It can be shown that this is optimal - a substring of an incompressible string
of length n can be compressible by an O(log n) additional term. This conforms
to a fact we know from probability theory: every random string of length n is
expected to contain a run of about log n consecutive zeros (or ones). Such a
substring has complexity O(log log n). 3
3 Regular Sets and Finite Automata
\Sigma be a finite nonempty alphabet, and let Q be a (possibly
infinite) nonempty set of states. A transition function is a function
Q. We extend ffi to ffi 0 on \Sigma   by ffi 0 (ffl;
Clearly, if ffi 0 is not then the automaton 'forgets' because some x and y
from \Sigma   drive ffi 0 into the same memory state. An automaton A is a quintuple
everything is as above and q 0 ; q f 2 Q are distinguished
initial state and final state, respectively. We call A a finite automaton (fa) if Q
is finite.
We denote 'indistinguishability' of a pair of histories x; y 2 \Sigma   by x - y,
defined as of strings is reflexive, sym-
metric, transitive, and right-invariant (ffi 0 (xz; q 0
'indistinguishability' is a right-invariant equivalence relation on \Sigma   . It is a simple
matter to ascertain this formally.
2 The language accepted by automaton A as above is the set
g. A regular language is a language accepted by a finite
automaton.
It is a straightforward exercise to verify from the definitions the following
fact (which will be used later).
Theorem 1 (Myhill, Nerode) The following statements about L ' \Sigma   are
equivalent.
(i) L ' \Sigma   is accepted by some finite automaton.
(ii) L is the union of equivalence classes of a right-invariant equivalence
relation of finite index on \Sigma   .
(iii) For all x; y 2 \Sigma   define right-invariant equivalence x - y by: for all
z 2 \Sigma   we have xz 2 L iff yz 2 L. Then the number of -equivalence classes is
finite.
Subsequently, closure of finite automaton languages under complement, union,
and intersection follow by simple construction of the appropriate ffi functions
from given ones. Details can be found in any textbook on the subject like [7].
The clumsy pumping lemma approach can now be replaced by the Kolmogorov
formulation below.
3.1 Kolmogorov Complexity Replacement for the Pumping
Lemma
An important part of formal language theory is deriving a hierarchy of language
families. The main division is the Chomsky hierarchy, with regular languages,
context-free languages, context-sensitive languages and recursively enumerable
languages. The common way to prove that certain languages are not regular
is by using 'pumping' lemmas, for instance, the uvw-lemma. However, these
lemmas are quite difficult to state and cumbersome to prove or use. In contrast,
below we show how to replace such arguments by simple, intuitive and yet
rigorous, Kolmogorov complexity arguments.
Regular languages coincide with the languages accepted by finite automata.
This invites a straightforward application of Kolmogorov complexity. Let us give
an example. We prove that f0 k 1g is not regular. If it were, then the
state q of a particular accepting fa after processing 0 k , together with the fa, is,
up to a constant, a description of k. Namely, by running A, initialized in state q,
on input consisting of only 1's, the first time A enters an accepting state is after
precisely k consecutive 1's. The size of the description of A and q is bounded
by a constant, say c, which is independent of k. Altogether, it follows that
choosing k with C(k) - log k we obtain a contradiction
for all large enough k. Hence, since the fa has a fixed finite number of states,
there is a fixed finite number that bounds the Kolmogorov complexity of each
natural number: contradiction. We generalize this observation as follows.
Definition 3 Let \Sigma be a finite nonempty alphabet, and let OE  be a
total recursive function. Then OE enumerates (possibly a proper subset of) \Sigma
in order OE(1); We call such an order effective, and OE an enumerator.
The lexicographical order is the effective order such that all words in \Sigma   are
ordered first according to length, and then lexicographically within the group
of each length. Another example is OE such that the standard binary
representation of the ith prime, is an effective order in f0; 1g   . In this case OE
does not enumerate all of \Sigma   . Let L ' \Sigma   . Define L Lg.
be regular, and let OE an enumerator
in \Sigma   . Then there exists a constant c depending only on L and OE, such that for
each x, if y is the nth string enumerated in (or in the complement of) L x , then
Proof. Let L be a regular language. The nth string y such that xy 2 L for
some x can be described by
ffl this discussion, and a description of the fa that accepts L;
ffl a description of OE; and
ffl the state of the fa after processing x, and the number n.
The statement "(or in the complement of)" follows, since regular languages are
closed under complementation. 2
As an application of the KC-Regularity Lemma we prove that f1
primeg is not regular. Consider the string
, with p 0 the kth prime. Then
, and y is the lexicographical
first element in L x . Hence, by Lemma But the difference
between two consecutive primes grows unbounded. Since there are only O(1)
descriptions of length O(1), we have a contradiction. We give some more examples
from the well-known textbook of Hopcroft and Ullman that are marked *
as difficult there:
Example 3 (Exercise 3.1(h)* in [7]) Show
ffflgg is not regular. Set log m. Then, the lexicographically
first word in L x is y with
contradicting the KC-Regularity Lemma. 3
Example 4 Prove that jg is not regular. Set
log m. Then, the lexicographically first word not in L x
But, C(y)
m), contradicting the KC-Regularity Lemma. 3
Example 5 (Exercise 3.6* in [7]) Prove that
is not regular. Set
log log n. Then the lexicographically first word in L x is 1
contradicting the KC-regularity lemma. 3
Example 6 (Section 2.2, Exercises 11-15, [5]) Prove that fp : p is the
standard binary representation of a prime g is not regular. Suppose the con-
trary, and p i denotes the ith prime, i - 1. Consider the least binary
not in f0g   f1g. Such a prime pm exists
since each interval [n; n of the natural numbers contains a prime, [6].
Considering pm now as an integer,
and v is not divided by any prime less than p k (because pm is prime), the binary
length goes to infinity with k, the value C(v) - C(l(v))
also goes to infinity with k. But since v is the lexicographical first suffix, with
integer v ? 1, such that uv 2 L, we have by the KC-Regularity
Lemma, which is a contradiction. 3
3.2 Kolmogorov Complexity Characterization of Regular
Languages
While the pumping lemmas are not precise enough (except for the difficult construction
in [4]) to characterize the regular languages, with Kolmogorov complexity
this is easy. In fact, the KC-Regularity Lemma is a direct corollary of
the characterization below. The theorem is not only a device to show that some
nonregular languages are nonregular, as are the common pumping lemmas, but
it is a characterization of the regular sets. Consequently, it determines whether
or not a given language is regular, just like the Myhill-Nerode Theorem. The
usual characterizations of regular languages seem to be practically useful to
show regularity. The need for pumping lemmas stems from the fact that characterizations
tend to be very hard to use to show nonregularity. In contrast,
the KC-characterization is practicable for both purposes, as evidenced by the
examples.
Definition 4 Let \Sigma be a nonempty finite alphabet, and let y i be the ith element
of \Sigma   in lexicographic order, i - 1. For L ' \Sigma   and x 2 \Sigma   , let
be the characteristic sequence of L defined by
Theorem 2 (Regular KC-Characterization) Let L ' \Sigma   , and assume
the notation above. The following statements are equivalent.
(i) L is regular.
(ii) There is a constant c L depending only on L, such that for all x 2 \Sigma   ,
for all n, C(- 1:n jn) - c L .
(iii) There is a constant c L depending only on L, such that for all x 2 \Sigma   ,
for all n,
(iv) There is a constant c L depending only on L, such that for all x 2 \Sigma   ,
for all n,
Proof. (i) ! (ii): by similar proof as the KC-Regularity Lemma.
For each constant c there are only finitely many one-way infinite binary
strings ! such that, for all n,
Proof. The claim is a weaker version of Theorem 6 in [2]. It turns out that
the weaker version admits a simpler proof. To make the treatment self-contained
we present this new proof in the Appendix. 2
By (iv) and the claim, there are only finitely many distinct -'s associated
with the x's in \Sigma   . Define the right-invariant equivalence relation - by x - x 0 if
This relation induces a partition of \Sigma   in equivalence classes
xg. Since there is a one-one correspondence between the [x]'s and the -'s,
and there are only finitely many distinct -'s, there are also only finitely many
[x]'s, which implies that L is regular by the Myhill-Nerode theorem. 2
Remark 1 The KC-regularity Lemma may be viewed as a corollary of the
Theorem. If L is regular, then clearly L x is regular, and it follows immediately
that there are only finitely many associated -'s, and each can be specified in
at most c bits, where c is a constant depending only on L (and enumerator
OE). If y is, say, the nth string in L x , then we can specify y as the string
corresponding to the nth '1' in -, using only C(n) bits to specify y.
Hence loss of generality, we need to assume
that the nth string enumerated in L x in the KC-regularity Lemma is the string
corresponding to the nth '1' in - by the enumeration in the Theorem, or that
there is a recursive mapping between the two.
Remark 2 If L is nonregular, then there are infinitely many x 2 \Sigma   with
distinct equivalence classes [x], each of which has its own distinct associated
characteristic sequence -. It is easy to see, for each automaton (finite or infinite),
for each - associated with an equivalence class [x] we have
1. The difference between finite and infinite automata is precisely
expressed in the fact that only in the first case does there exist an a priori
constant which bounds the lefthand term for all -.
We show how to prove positive results with the KC-Characterization Theo-
rem. (Examples of negative results were given in the preceding section.)
Example 7 Prove that There exists a constant c, such
that for each x the associated characteristic sequence is
C(- 1:n jn) - c. Therefore, L is regular by the KC-Characterization Theorem.
Example 8 Prove that the number of '1's in x is oddg is regular.
Obviously, there exists a constant c such that for each x we have C(- 1:n
Therefore, L is regular by the KC-Characterization Theorem. 3
4 Deterministic Context-free Languages
We present a Kolmogorov complexity based criterion to show that certain languages
are not dcfl. In particular, it can be used to demonstrate the existence of
witness languages in the difference of the family of context-free languages (cfls)
and deterministic context-free languages (dcfls). Languages in this difference
are the most difficult to identify; other non-dcfl are also non-cfl and in those
cases we can often use the pumping lemma for context-free languages. The new
method compares favorably with other known related techniques (mentioned in
the Introduction) by being simpler, easier to apply, and apparently more powerful
(because it works on a superset of examples). Yet, our primary goal is to
demonstrate the usefulness of Kolmogorov complexity in this matter.
A language is a dcfl iff it is accepted by a deterministic pushdown automaton
(dpda).
Intuitively, the lemma below tries to capture the following. Suppose a dpda
accepts 1g. Then the dpda needs to first store a representation
of the all-0 part, and then retrieve it to check against the all-1 part. But
after that check, it seems inevitable that it has discarded the relevant information
about n, and cannot use this information again to check against the all-2
part. That is, the complexity of the all-2 part should be
yields a contradiction for large n.
Definition 5 A one-way infinite string recursive if there
is a total recursive function f
be recognized by a deterministic pushdown
machine M and let c be a constant. Let be a recursive sequence
over \Sigma which can be described in c bits. Let x; y 2 \Sigma   with C(x; y) ! c and let
recursive sequence over \Sigma of the
be such that Items (i) to (iii) below are satisfied.
(i) For each i (1 - i - n), given M 's state and pushdown store contents
after processing input description of !, and an additional
description of at most c bits, we can reconstruct n by running M and observing
only acceptance or rejection.
Given M 's state and pushdown store contents after processing input
, we can reconstruct w from an additional description of at
most c bits.
log log m.
Then there is a constant c 0 depending only on L and c such that C(w) - c 0 .
Proof. Let L be accepted by M with input head h r . Assume m; n; w satisfy
the conditions in the statement of the lemma. For convenience we write
For each input z 2 \Sigma   , we denote with c(z) the pushdown store contents at
the time h r has read all of z, and moves to the right adjacent input symbol.
Consider the computation of M on input uv from the time when h r reaches the
end of u. There are two cases:
Case 1. There is a constant c 1 such that for infinitely many pairs m;n
satisfying the statement of the lemma if h r continues and reaches the end of v,
then all of the original c(u) has been popped except at most the bottom c 1 bits.
That is, machine M decreases its pushdown store from size l(c(u)) to size
during the processing of v. The first time this occurs, let v 0 be the processed
initial segment of v, and v 00 the unprocessed suffix (so that
be in state q. We can describe w by the following items. 2
ffl A self-delimiting description of M (including \Sigma) and this discussion in
bits.
ffl A self-delimiting description of ! in (1
ffl A description of c(uv 0 ) and q in c 1 log j\Sigmaj +O(1) bits.
ffl The 'additional description' mentioned in Item (i) of the statement of the
lemma in self-delimiting format, using at most (1 bits. Denote it by
p.
ffl The 'additional' description mentioned in Item (ii) of the statement of the
lemma in self-delimiting format, using at most (1 bits. Denote it by
r.
By Item (i) in the statement of the lemma we can reconstruct v 00 from M in
state q and with pushdown store contents c(uv 0 ), and !, using description p.
Subsequently, starting M in state q with pushdown store contents c(uv 0 ), we
process v 00 . At the end of the computation we have obtained M 's state and
pushdown store contents after processing uv. According to Item (ii) in the
statement of the lemma, together with description r we can now reconstruct w.
Since C(w) is at most the length of this description,
Setting c 0 := 4c satisfies the lemma.
Since we need to glue different binary items in the encoding together, in a way so that we
can effectively separate them again, like hx; y, we count C(x)
a self-delimited encoding x of x . We only need to give self-delimiting forms
for all but one constituent description item.
Case 2. By way of contradiction, assume that Case 1 does not hold. That
is, for each constant c 1 all but finitely many pairs m;n satisfying the conditions
in the lemma cause M not to decrease its stack height below c 1 during the
processing of the v part of input uv.
Fix some constant c 1 . Set m;n so that they satisfy the statement of the
lemma, and to be as long as required to validate the argument below. Choose
as a suffix of
log log m: (2)
That is, much larger than l(u) (= m) and much more regular. A mo-
ment's reflection learns that we can always choose such a u 0 .
2 For large enough m there exists a u 0 as above, such that M starts
in the same state and accesses the same top elements of its stack
during the processing of the v parts of both inputs uv and u 0 v.
Proof. By assumption, M does not read below the bottom c 1 symbols of
c(u) while processing the v part of input uv.
We argue that one can choose u 0 such that the top segment of c(u 0 ) is precisely
the same as the top segment of c(u) above the bottom c 1 symbols, for
large enough l(u), l(u 0 ).
To see this we examine the initial computation of M on u. Since M is
deterministic, it must either cycle through a sequence of pushdown store con-
tents, or increase its pushdown store with repetitions on long enough u (and
Namely, let a triple (q; that M is in state q, has top pushdown
store symbol s, and h r is at ith bit of some y. Consider only the triples (q;
at the steps where M will never go below the current top pushdown store level
again while reading u. (That is, s will not be popped before going into v.)
There are precisely l(c(u)) such triples. Because the input is repetitious and
M is deterministic, some triple must start to repeat within a constant number
of steps and with a constant interval (in height of M 's pushdown store) after
starts reading y's. It is easy to show that within a repeating interval only a
constant number of y's are read.
The pushdown store does not cycle through an a priori bounded set of push-down
store contents, since this would mean that there is a constant c 1 such that
the processing by M of any suffix of does not increase the stack height
above c 1 . This situation reduces to Case 1 with
Therefore, the pushdown store contents grows repetitiously and unbound-
edly. Since the repeating cycle starts in the pushdown store after a constant
number of symbols, and its size is constant in number of y's, we can adjust u 0
so that M starts in the same state and reads the same top segments of c(u) and
in the v parts of its computations on uv and u 0 v. This proves the claim.The following items form a description from which we can reconstruct v.
ffl This discussion and a description of M in O(1) bits.
ffl A self-delimiting description of the recursive sequence ! of which v is an
initial segment in (1
ffl A self-delimiting description of the pair hx; yi in (1
ffl A self-delimiting description of
ffl A program p to reconstruct v given ! and M 's state and pushdown store
contents after processing u. By Item (i) of the statement of the lemma,
Therefore, a self-delimiting description of p takes at most (1+ ffl)c
bits.
The following procedure reconstructs v from this information. Using the description
of M and u 0 we construct the state q u 0
and pushdown store contents
after processing u 0 . By Claim 2, the state q u of M after processing
and the top elements of c(u) and c(u 0 ) are the
same. Run M on input ! starting in state q u 0
and with stack contents c(u 0 ). By
assumption, no more than popped before we
have processed . By just looking at the consecutive states of M in this
computation, and using program p, we can find n according to Item (i) in the
statement of the lemma. To reconstruct v requires by definition at least C(v)
bits. Therefore,
where the last inequality follows by Equation 2. But this contradicts Item (iii)
in the statement of the lemma for large enough m. 2
Items (i) through (iii) in the KC-DCFL Lemma can be considerably weak-
ened, but the presented version gives the essential idea and power: it suffices
for many examples. A more restricted, but easier, version is the following.
Corollary 1 Let L ' \Sigma   be a dcfl and let c be a constant. Let x and y be
fixed finite words over \Sigma and let ! be a recursive sequence over \Sigma. Let u be a
suffix of be a prefix of !, and let w 2 \Sigma   such that:
(i) v can be described in c bits given L u in lexicographical
(ii) w can be described in c bits given L uv in lexicographical order; and
log log l(u).
Then there is a constant c 0 depending only on L; c; such that C(w) - c 0 .
All the following context-free languages were proved to be not dcfl only with
great effort before, [7, 5, 25]. Our new proofs are more direct and intuitive.
Basically, if v is the first word in L u , then processing the v part of input uv
must have already used up the information of u. But if there is not much
information left on the pushdown store, then the first word w in L uv cannot
have high Kolmogorov complexity.
Example 9 (Exercise 10.5 (a)* in [7]) Prove
is not dcfl. Suppose the contrary. Set
Item (iii) of the lemma. Since v is lexicographically the first word in L u ,
Item (i) of the lemma is satisfied. The lexicographically first nonempty word
in L uv is so we can set of the lemma.
But now we have C(w)
n), contradicting the KC-DCFL Lemma and its
Corollary.
Approximately the same proof shows that the context-free language fxx R :
and the context-sensitive language fxx : x 2 \Sigma   g are not deterministic
context-free languages. 3
(b)* in [7], Example 1 in [25]) Prove f0
2ng is not dcfl. Suppose the contrary. Let
log n. Then v is the lexicographically first word in L u . The lexicographically
first nonempty word in L uv is 1 n . Set
contradicting the KC-DCFL Lemma and its Corollary. 3
Example 11 (Example 2 in [25]) Prove contains a
is not dcfl. Suppose the contrary. Set
is even. Then lexicographically the first even length word not in
L u . With C(n) - log n, this satisfies Items (i) and (iii) of the lemma. Choosing
the lexicographically first even length word not in L uv starting with
a '1 0 , satisfies Item (ii). But C(w)
=\Omega\Gamma292 n), which contradicts the KC-DCFL
Lemma and its Corollary. 3
Example 12 Prove kg is not dcfl.
Suppose the contrary. Let
item (iii) of the lemma. Then, v is lexicographically the first word in L u ,
satisfying Item (i). The lexicographic first word in L uv " f1gf2g   is 12 n+1 .
Therefore, we can set
contradicting the KC-DCFL Lemma and its Corollary. 3
Example 13 (Pattern-Matching) The KC-DCFL Lemma and its Corollary
can be used trickily. We prove fx#yx R z : x; is not dcfl. Suppose
the contrary. Let
(iii) of the lemma. Since v is the lexicographically first word in L u , the
choice of v satisfies Item (i) of the lemma. (We can reconstruct v from v 0 by
flipping the last bit of v 0 from 1 to 0.) Then is lexicographically the
first word in L uv , to satisfy Item (ii). Since C(w)
=\Omega\Gamma365 n), this contradicts
the KC-DCFL Lemma and its Corollary. 3
5 Recursive, Recursively Enumerable, and Be-
yond
It is immediately obvious how to characterize recursive languages in terms of
Kolmogorov complexity. If L ' \Sigma   , and \Sigma  effectively ordered,
then we define the characteristic sequence
In terms of the earlier developed terminology, if A
is the automaton accepting L, then - is the characteristic sequence associated
with the equivalence class [ffl]. Recall Definition 5 of a recursive sequence. A set
recursive iff its characteristic sequence - is a recursive sequence. It
then follows trivially from the definitions:
Theorem 3 (Recursive KC Characterization) A set L 2 \Sigma   is recur-
sive, iff there exists a constant c L (depending only on L) such that, for all n,
L is r.e. if the set fn : In terms of Kolmogorov complexity, the
following theorem gives not only a qualitative but even a quantitative difference
between recursive and r.e. languages. The following theorem is due to Barzdin',
[1, 14].
Theorem 4 (KC-r.e.) (i) If L is r.e., then there is a constant c L (depending
only on L), such that for all n,
(ii) There exists an r.e. set L such that C(- 1:n ) - log n, for all n.
Note that, with L as in Item (ii), the set \Sigma   \Gamma L (which is possibly non-
r.e.) also satisfies Item (i). Therefore, Item (i) is not a Kolmogorov complexity
characterization of the r.e. sets.
Example 14 Consider the standard enumeration of Turing machines. Define
the ith Turing machine started on its ith program
halts A be the language such that k
is its characteristic sequence. Clearly, A is an r.e. set. In [1] it is shown that
Example 15 Let k be as in the previous example. Define a one-way infinite
binary sequence h by
Then, C(h 1:n log n). Therefore, if h is the characteristic
sequence of a set B, then B is not recursive, but more 'sparsely' nonrecursive
than is A. 3
Example 16 The probability that the optimal universal Turing machine U
halts on self-delimiting binary input p, randomly supplied by tosses of a fair
coin, is \Omega\Gamma 0
1. Let the binary representation
of\Omega be
0:\Omega
be a finite nonempty alphabet, and an effective enumeration without
repetitions of \Sigma   . Define L ' \Sigma   such that v i 2 L
1. It can be shown,
see for example [13], that the
for all but finitely many n.
Hence neither L nor \Sigma   \Gamma L is r.e. It is not difficult to see that L 2
in the arithmetic hierarchy (that is, L is not recursively enumerable),
[23, 24]. 3
6 Questions for Future Research
(1) It is not difficult to give a direct KC-analogue of the uvwxy Pumping Lemma
(as Tao Jiang pointed out to us). Just like the Pumping Lemma, this will show
that is primeg, and so on, are not cfl.
Clearly, this hasn't yet captured the Kolmogorov complexity heart of cfl. More
in general, can we find a CFL-KC-Characterization?
(2) What about ambiguous context-free languages?
(3) What about context-sensitive languages and deterministic context-sensitive
languages?


Appendix

Proof of Claim 1
A recursive real is a real number whose binary expansion is recursive in the sense
of Definition 5. The following result is demonstrated in [15] and attributed to
A.R. Meyer. For each constant c there are only finitely many
C(! 1:n jn) - c for all n. Moreover, each such ! is a recursive real.
In [2] this is strengthened to a version with C(! 1:n ) - C(n)+c, and strengthened
again to a version with C(! 1:n than the
latter version by not requiring the !'s to be recursive reals. For completeness
sake, we present a new direct proof of Claim 1 avoiding the notion of recursive
reals.
Recall our convention of identifying integer x with the xth binary sequence
in lexicographical order of f0; 1g   as in Equation 1.
Proof.[of c be a positive constant, and let
If the cardinality d(An ) of An dips below a fixed constant c 0 , for infinitely
many n, then c 0 is an upper bound on d(A). This is because it is an upper
bound on the cardinality of the set of prefixes of length n of the elements in A,
for all n.
Fix any l 2 N . Choose a binary string y of length 2l
Choose i maximum such that for division of y in
(This holds at least for similarly a division
1. By maximality of i, we have s ? From the easily proven
We prove l(r) - l. Since by Equations 5 and 3 we have
it follows that l(m) -
which implies that l(n) ? l. Consequently,
We prove dovetailing the computations of the reference
universal Turing machine U for all programs p with l(p) - log c, we can
enumerate all elements of An . We can reconstruct y from the mth element, say
y 0 , of this enumeration. Namely, from y 0 we reconstruct n since l(y 0
we obtain m by enumerating An until y 0 is generated. By concatenation we
From Equation 4 we have
Combining Equations 7 and 8, it follows that log m - c + O(1). Therefore, by
Equation 6,
Here, c is a fixed constant independent of n and m. Since l(r) - l and we can
choose l arbitrarily, for a fixed constant c 0 and infinitely many r,
which implies d(A) - c 0 , and hence the claim. 2
We avoided establishing, as in the cited references, that the elements of A
defined in Equation 3 are recursive reals. The resulting proof is simpler, and
sufficient for our purpose, since we only need to establish the finiteness of A.
Remark 3 The difficult part of the Regular KC-Characterization Theorem
above consists in proving that the KC-Regularity Lemma is exhaustive, i.e.,
can be used to prove the nonregularity of all nonregular languages. Let us look
a little more closely at the set of sequences defined in Item (iii) of the KC-
Characterization Theorem. The set of sequences A of Equation 3 is a superset
of the set of characteristic sequences associated with L. According to the proof
in the cited references, this set A contains finitely many recursive sequences
(computable by Turing machines). The subset of A consisting of the characteristic
sequences associated with L, satisfies much more stringent computational
requirements, since it can be computed using only the finite automaton recognizing
L. If we replace the plain Kolmogorov complexity in the statement of
the theorem by the so-called 'prefix complexity' variant K, then the equivalent
set of A in Equation 3 is
which contains nonrecursive sequences by a result of R.M. Solovay, [21].

Acknowledgements

.
We thank Peter van Emde Boas, Theo Jansen, Tao Jiang for reading the
manuscript and commenting on it, and the anonymous referees for extensive
comments and suggestions for improvements. John Tromp improved the proof
of Claim 1.



--R

Complexity of programs to determine whether natural numbers not greater than n belong to a recursively enumerable set.

Algorithmic Information Theory.
Pumping lemmas for regular sets.
Introduction to Formal Language Theory.
The difference between consecutive primes.
Introduction to Automata Theory
A necessary and sufficient pumping lemma for regular languages.

Two heads are better than two tapes.
Three approaches to the quantitative definition of in- formation
Tape versus queue and stacks: The lower bounds.
An Introduction to Kolmogorov complexity and Its Applications.
On minimal-program complexity measures
A variant of the Kolmogorov concept of complexity.
Quadratic lower bounds for deterministic and nondeterministic one-tape Turing machines


Kolmogorov's complexity and lower bounds.
An information theoretic approach to time bounds for on-line computation
Lecture notes.
A pumping theorem for regular languages.
Random Sequences.
Algorithmic Information Theory.
A pumping lemma for deterministic context-free languages
--TR
kolmogorov complexity;pumping lemmas;deterministic context-free languages;formal language theory;regular languages;finite automata