ON THE SUCCINCTNESS OF DIFFERENT
REPRESENTATIONS OF LANGUAGES
by
Jt flartmanis
TR78--H346
REVISED
Department of Computer Science
Cornell University
Ithaca, N?			14853
This research has been supported in part by National Science Foundation
Grant DCR75-09433.
ON THE SUCCINCTNESS OF DIFFERENT
REPRESENTATIONS OF LANGUAGES
J. Hartnanis
Department of Computer Science
Cornell University
Ithaca, NY			14953
Abstract
The purpose of this paper is to give simple new proofs of
some interesting recent results about the relative succinctnesa
of different representations of regular, deterministic and un?
biguous context--Hfree languages and to derive some new results
about how the relative succinctness of representations change
when the representations contain a formal proof that the languages
generated are in the desired suhclass of languages.
This research has been supported in part by National Science Foundation
Grant DCR7S-O9433 and MCS 79-00418.
Introduction
It has been shown recently that there exist dramatic com-
pression of the length of representations of languages in sub-
classes of context-free languages a? we go from restricted to
unrestricted representations of these languages (2,4,Sj. For
example, when we consider the representation of detenninistic
context-free languages by deterministic versus nondetenninistic
pushdown automata, then there is no recursive function which can
bound the size of the minimal deterministic pushdown autonaton as
a function of the size of the equivalent minimal nondetertinistic
pushdown automaton (51. It is well known that we cannot re-
cursively decide whether a given pushdown automaton has a equi-
valent deterministic pushdown automaton, but the above result
makes a considerably stronger statement: even if we would know
(or be given? which pushdown automata describe deterministic lan-
guages, we still could not effectively write down the correspon-
ding deterministic pushdown automata becsuse of their enorrr.ous size
which grows nonrecursively in the size of the nondeter?t?inistic push-
down automata. Therefore we see that though nondet?rm?nism is not
needed in the description of nondeterministic context-free lan-
guages its use in the description permits nonrecursively bounded
shortening of infinitely many representations.
Similar results hold for the relative succinctness of the
description of unambiguous cfl?s by unambiguous and ambiguous cfg's
(41, and the description of finite or regular sets by finite auto-
--H2--H
mata and pushdown automata [21.
Some of the original proofs of these results are quite hard
and they require special results about context-free languages. In
the first part of this paper we give a very simple, elementary proof
that the relative succinctness of representing deterninistic context-
free languages by deterministic or nondeterministic pushdown automate
is not recursively bounded, and using a result about inherently
ambiguous cfl's and Turing machine computations [31, derive an
equally simple proof for the representation of unambiguous cfl's
by unambiguous or ambiguous context-free grammars. The results
about the representation of finite and regular sets can be easily
proven by the same methods
In the representation of deterministic cfl's by deterministic
pda's we can easily check whether a given pda is deterministic, on
the other hand, for a nondeterministic pda we have no obvious way
of verifying that it accepts a deterministic cfl. Therefore the
question arises whether the relative succinctness of the two repre-
sentations is caused by the fact that in one representation we can
prove what we are accepting but that no such proofs are possible
in the other representation.
Indeed a close inspection of the original proof [21 reveals
that it does not hold when we represent dcfl's by dpda's or pda's
with attached proofs that they accept deterministic cfl's.
In the second part of this paper we show that our proof tech-
niques furthermore prove that, for example, the relative succinct-
ness results hold for the representation of dcfl's by deterministic
pda and nondeterministic pda with attached proofs that they accept
deterministic cfl`s.
--H3--H
Finally, to gain further insight how the inclusion of formal
proofs of correctness in representations of languages affects their
succinctness, we consider the representation of finite sets. We
show that there is no recursive hound in the relative succinctness
of the representation of finite sets by finite automata or Turing
machines (even if we attach proofs that the Tn accepts a finite
set). On the other hand, we show that the relative succinctness
is recursively bounded for the representation of finite sets by
finite automata or Turing machines with proof5 which explicitly give
ths cardinality of the finite set accepted.
It follows from the results that the relative succinctness is
not recursively bounded for the representation of finite sets by
finite automata (or tables) or muring machines which accept them,
but that there is a recursive bound for the representation of finite
sets by finite automata (or tables) and Turing machines which list
them and halt.
Su			Results about cFL'
We first establish notation and summarize some well known facts
about context-free languages (cfl?s)
We denote pushdown automata (pda) by A. and deterministic
pushdown automata (dpda) by Dj Let 1AiI denote the length of the
description of the automaton A. over some finite alphabet and L(Ai)
the language accepted by Ai. We consider only one-tape Turing
machines, denoted by Mi and for technical reasons we assume (withou
any loss of generality) that M. can halt only after an even number
of moves, N. accepts by halting and that it makes at least two moves
before halting, finally assume that Mi cannot print a blank. An
--H4--H
instantaneous description of Mi depict. the syvibols written om the
tape1 indicate. the tape square scanned by Mi and its state: they
are strings of the following form:
--Ht'(a1q)?'--H1--H(--H.q)?*--H or --Ht'(--H.q)--H.
where -? denotes a blank tape square, ? is the finite alphabet of
5YmbOl5.Mj can print, a E Z and q is a state of Mi. For Th N
? 1D0(x)
denotes the instantaneous description of the starting configuration
on input x and 1D1(x)1ID2(x).... denote the successive instantaneous
T
descriptions of M on input x. If x --H a1a2. an then x --H
a2a1. Lot VALC(MiJ denote the set of valid computations of Mi in
which every second instantaneous description is reversed1 i.e.
VAW(Mi) (?Io0(x)?1IDl(x)jT?In2(x)..??(ID2kl(x)JTflID2k(x)?1 X c
and ID2k(x) is a halting configuration).
Let
o+INVALC[Mji --H			- vALC(Mii
It is well kno:'n that INVALC(Mi1 can be accepted by a nondetermin-
istic pda and tnerefore it is a cfl 111. On the other hand1 VALC(Mi)
is a efi iff L(Nj?&5??a finite set1 since otherwise for arbitrarily
large inputs x the th?'e'e first instantaneous descriptions must be
related and the cfl pumping lemma does not hold. This yields the
well known auxiliary result.
Lemma1: INVALC(MiJ is a deterministic cfl iff L(Mi) is finite.
Proof: If L(Mi) is finite then INVMCiMii is a regular set and
therefore a dcfl. If L(Mi) is infinite then VALC(Mii is not a
i anti th?r?r.,?o ?NVAIA iMi) ?annet lN? a left.
-5-
Len-a2: The set `t - (At I L(Aj) is not a dcfl) is not recursively
enunerable.
Proof: Since INVAWIMil is a deterainistic cfl iff L(Mj) is finite,
a racursive enuneration of R would yield a recurs?ve enuneration of
the set ?Mi I L(Mj) is infinite), which is seen not to be possible
by Rice's theorem.			I
For two representations. such as the representation of deter--H
ministic cfl's by deterininiatic and nondeterministic pda's, we
will say that their relative succinctness is not recursively bounde
if there does not exist a recursive function F such that for any
pda, A, which accepts a deterninistic cfl, there exists an equiva-
lent deterninistic pda, n, for which ID % F(IAI)
Theorem3: The relative succinctness of representing deter:ainistic
cfl's by deterministic and nondeterministic pda's is not recursivel:
bounded.
Proof: If such a recursive F exists then for any pda A we can coin-
pute F(IAI) and effectively list the dpda0s whose length of descrip
tion does not exceed F(iAI), say Di1 Di2Di5 Then L(A) is a
nondeterninistic cf1 iff none of the Di , l'i%s, is equivalent to
A, but if this is so then we can detect it by coinparing the Di and
A on successive inputs from S?. Therefore the existence of r i:?pli
that the set
(A			L(A) is not a dcfl)
is recursively enumerable, which we know is not the case by Le? 2
Therefore, F does not extst as was to be ihown.
--H6--H
Next we consider the relative succinctness between the repre-
sentation of unambiguous cfl?s by unambiguous and ambiguous cfg's.
We exploit a recent result (which is given in a somewhat dif-
ferent formulation in) 131. For any Tm, Mi let
A5(Mi) = 4ID0(x)t([ID?1T4 IDj+1 o+)* I
follows from IDj by one operation of M., x ?
IDj+1			1
?(Mi)=(#(IDj o+[IDj+11T.)s ID2k# ID?+1 follows from IDj in
pne operation of Mi and ID2k is a halting configuration.)
and define
A(Ni)			A5(14) u AE(Mi)
It is easily seen that A(Mi) is a context-free language and it links
the ambiguity question for A(Mi) to finiteness of sets accepted by
the Turing machine Mj.
Theoren4: A(Mi) is an inherently ambiguous cfl iff L(M?) is infinite.
Proof: See [31.			I
Theoren5: The relative succinctness of representing unambiguous
cfl's ?y unambiguous and ambiguous cfg's is not recursively bounded.
Proof: If a recursive bound F exists, then the set
AMB = G cfg and L(G) is inherently ambiguous)
is recursively enumerable. To see this note that we can list for
any cfg G all cfg's whose representations are shorter than F(IGI)
and then crossoff those grazmnars which are found to be ambiguous or
--H7--H
not equivalent to G as we test them on successive strings from ??
L(G) is inherently ambiguous iff eventually all gra::mars from the
list are crossed off. Thus the set AMB is recursively enumerable
and therefore, (by Theorem 4) so is the set
(Mi I L(Mi) is infinite),
which leads to a contradiction. Therefore the recursive bound P
does not exist.
By the same method we can give an easy proof for the next result
[1]
Theorem6: The relative succinctness of the representation of co-
finite sets by finite automata and pushdown automata is not recur-
sively bounded. Therefore the relative succinctness of the repre-
sentation of regular sets by finite automata and pushdown automata
is also not recursively bounded.
Proof: Similar to the proof of Theorem 3, by using the set
R (AiIL(Ai) is not cofinite).
The same reasoning shows that there is no recursive bound
between the size of context-free grammars (which generate cfl?s
whose complements are also cfl?s) and the size of the cfg?s gener-
ating the complements.
Theorem7: There is no recursive function F such that for any cfg
G such that ?* - L(G) is a cfl, there exists a cfg, G', with
--H --H L(G) and IG' : F(iGi).
Proof: Similar to the proof of Theorem 3.
?uccinctnessResu?tsaboutVerifiedRepresentations
In the representation of deterministic cfl's by determinietic
and nondeterministic pda's we can easily verify that a given auto-
`naton is indeed deterministic, but for the equivalent nondetermini-
stic pda's we have no fixed way of verifying that it will accept a
deterministic cf1. This lack of symmetry in our representations
suggests that we should consider only representations by nondeter-
ministic pda's with attached proofs that they accept a determini-
stic language and add the length of the proof to the length of the
representation of the pda.
A close inspection of the original proofs [2,4,51 reveals that
they do not extend to the representation with added proofs. On the
other hand our proof techniques show that the previous succinctnese
results can be extended to representations with attached verifica-
tions that they accept the desired type of language.
More precisely, let ?S be an axiomatizable, sound formal mathe-
matical system which is powerful enough to express and prove elemen-
tary facts about Turing machines, context-free languages and push-
do%? autonata. Since FS is axiomatirable we know that we can
recuraively enumerate the set of provable theorems and soundness
assures as that the provable theorems are true. Instead of speci-
fying FS in detail we will describe what must be easily provable in
PS.
a)
Lot Ma(r) be a simply and uniformly constructod Th which
for o.?ch ini'ut x computes ?i'a :`avt,e tiLe len?th of x,
lxi --H a, then enunerates all one-tape m's up to length r1
--H9--H
i.e. IMjI ? r,,and simulates in a dove-tail manner the corn
putations of this finite set of machines on blank tape.
M0(r) halts (and therefore accepts) iff some MiU IMji ?
halts after performing m or more steps. From this constru
tion we see that for all r, r ? 1, M?(r) accepts a finite
set. We assume that FS is sufficiently powerful that we
can prove in FS that L(M0(r)? is finite and that the lengt
of these proofs is recursively bounded in r.
b) We furthermore assume that there is a simple and uniform
construction p which yields for each TI Mi a pda
such that
L(AP(i)) --H INVALC(Mi)
and that it can be proven in FS (by a proof whose length ?
recureively bounded in i) thats
if L(Mi) is finite then L(AO(i)) --H lNVAW?Mi1
is a deterministic cf1.
From these assumptions it follows that we cam prove (easily)
im PS thati
AP(O(r)) accepts a deterministic cfl.
It should be observed that in any logic designed to reason
about computations we should be able to formulate and prove easily
the above result. Furthermore, to any given sound formal syst? WE
can add the above assertions as an axiom scheme to obtain the de-
sirod FS.
--H10-
A nondeterministic pda with an attached proof in FS that it
accepts a deterministic cf1 is called a verified pda or vpda.
Theorem8: The relative succinctness of representing dcfl's by
dpda's and vpda's is not recursively bounded.
proof: For r, r ? 1, let M,(r) be a Th which accepts all inputs
up to length N where N is the maximal running time before halting
r r
achieved by a Th of size r on blank tape. Let Ap (i) be a non-deter-
ministic pda which accepts INVALC[Mi] It is assumed that s(r) and
p(r) are simple enough to compute and that FS is sufficiently rich
that there exist short proofs (whose length is recursively
bounded in r) that L[Na(r) is finite and therefore L[AP(c(r))? is a
deterministic cfl.
If there exists a recursive bound F between JAp(a(r))1 and the
shortest eguivalent dpda, then we can list all the dpda's
D11 12 Di5 such that Dij I ? F[JAP(a(r)) J], lsj?s.
From this list of dpda's we can effectively construct a list of
dpda's which accept the complements of these languages. From this
new list we can effectively select the dpda's which accept finite
sets and compute the longest string accepted by these dpda's
Clearly the length of this string is bigger than N and therefore
r
N is recursively bounded in r, which is a contradiction. I
r
By exploiting the fact that we can recursively enumerate the
voda's we can prove the next result.
Corollary9: There is no recursive succinctness bound between the
representation of dcfl's by verified pda's and pda's.
By assuming that we can easily prove in ?S relations between
A(Mi) and ambiguous cfl's we obtain the next result.
Corollary10: There is no recursive succinctness bound between the
representation of unambiguous cfl?s by unambiguous cfg's and
ambiguous cfg?s with proofs that they accept unambiguous cfl's, nor
is there a recursive bound between the representation of unambiguous
cfl's by ambiguous cfg's with proofs that they accept unambiguous
cfl's and cfg's.
xe resentation ot ?1n1te ?ets
The situation changes drastically if we consider representation
of finite sets and finite sets of known size.
Theorem11: a) There is no recursive succinctness bound for the
representation of finite sets by finite automata and by Tn's with
proofs that they accept finite sets.
b) There is a recursive succinctness bound for the representa-
tion of finite sets by finite automata (or tables) and Tn's with
proofs which explicitly give the size of the finite set accepted.
c) There is a recursive bound for the relative succinctness
of representing finite subsets by finite autonata (or lists) and
Tn's with proofs that they print a list and halt.
Proof: a) Let Ms(r) be the Tn constructed for the proof of Theorem
8 and recall that we have assumed that our formal system FS is suf-
ficiently rich to prove, by proofs whose length is recursively
bounded in r, that L(na(r)) is finite. Therefore the length of M0(r)
plus the length of the proof in FS that L(Ms(r)) is finite is re-
--H12--H
cursively bounded in r. On the other hand, since L(M0(r)? is finite
the number of state. of any finite autonaton accepting L(Mc(r)) must
be n6 less than the length of the longest string in L(Mc(r))0 which
by construction of Mo (r) is not recursively bounded in r. Therefore0
the relative succinctness of these two representation. cannot be
recursively bounded
b) The relative succinctness bound F can be constructed as follows.
For n construct all proofs of "Mi accepts a set of size k", i0k --H
1,2,..., such that IMi plus the length of the proof is less or equal
to n. For the Mi with such proofs let km be the cardinality of the
largest set accepted and an the length of the longest atring accepted.
Clearly km and an are effectively computable and
F(n) - 5n			km + 2
is such a recursive bound.
c) For any m we can effectively list the finite set of Ta's
Mi I MiMi 0 such that
I 2 k
Mi I + proof that Mij prints a list and halts ?
Therefore we can run all the Th1a on this list, which are guaranteed
to halt because FS is sound, and determine the length of the longest
string printed, mm. Clearly mm is recursively computable from n0
by the above procedure, and, furthermore, the size of the largest
minisal finite automaton accepting the sets L(Mi )o L(Mi ),...o
I			2
L(M ) is recursively bounded in mm. Therefore the size of the
1k
finite automata representation of these sets is recursively bounded
to n and therefore to the size of the Th representation with proof5. 1
Iteferences
1.
-13-
Hartmanie, J. "Context-Free Languages and Turing Machine Compu-
tations", Proceedings of Symposia in Applied Mathematics Vol. is
Mathematical Aspects of Computer Science1 pp. 42-51, Amer. Matn.
Soc. 1967.
2. Meyer, A.R. and N.J. Fischer. "Economy of Description by Autonat
Grammars and Formal Systems", Conference secord, I?E 12th Ann'ja
Symposium on Switching and Automata Theory (1971), 198-190.
3. ?eedy, H. and W.J. Savitch. "The Turing Degree of the Inherent
Ambiguity Problem for Context-Free Languages"1 Theoretical
Computer Science, Vol. 1 (1975), 77-91.
4. Schmidt, E.11. and T.G. SzymanskL. "Succinctness of Descriptions
of Unamoiguous Context-Free Languages"1 SlAM J. Computing1 Vol.
(1977), 547--H553.
5. Valiant, L.G. "A Note on the Succinctnees of Descriptions of
Deterministic Languages", Xnfor?nation and Control, Vol. 32 (197E
139--H145.