ON THE PRESERVATION OF CONTEXT-FREE LANGUAGES IN 
A LEVEL-BASED SYSTEM 
Jacob Mey 
The University of Texas at Austin 
Austint Texas 78712 
U.S.A° 
Abstract 
In this paper, a recently proposed level-oriented 
model for machine analysis and synthesis of natural 
languages is investigated° Claims concerning the 
preservation of context-free (CF) languages in such 
a system are examined and shown to be unjustified. 
Furthermorep it is ~hown that even a revised version 
of the mode1 (incorporating some recent discoveries) 
will not be CF-preservlngo Finallyp some theoretical 
implications of these findings are explored: in par- 
tlcular~ claims of greater naturalness and the ques- 
tion of recurslvltyo 
® Over the yearsp and especlally during the pr~wara- 
tlon of this paper t I have had the pleasure of many 
enlightening discussions with Stani%y Peters, for 
which I am glad to thank hlm. 
Mey la 
Dans ce travail, on envisage un module r~cent de 
synth~se et d'analyse automatiques de l angues naturelles, 
oriente vers la notion de "nlveau" linguistlque. On 
examine un postulat selon lequel !es langages context- 
free seraient stables dans un tel syst~me~ Cette notion 
s'avere Incorrecte~ De plus~ on montre comment m~me une 
~erslon modifi~e du module, incorporan~ certalnes d~- 
couvertes r~centes~ ne conserve pas le caract~re con- 
text-free de ces langages. Enfin, on explore l'impor- 
tance theorique de ces resultats~ en particulier, on 
examine l'avantage suppose d'un modele dit plus "natu- 
rel", et la question de la recurslvite des langues na- 
turelles. 
• Pendant les ann~es, et surtout pendant la r~daction 
de ce travail, J'ai pu profiter de nombreuses conver- 
sations illuminantes avec Stanley Peters, puur les- 
quelles Je tiens a lul exprimer ma reconnaissance. 
Mey 2 
1. Level-Oriented Systems in Computational Linguistics 
A new model for computational linguistic perfor- 
m~,~ has recently been proposed by the Czechoslovak 
group of workers at Charles Unlverslty~ Prague~ under 
the direction of Po Sgall (lp 2). This model has Slg- 
nificant theoretlcal impllcations, since it offers 
an alternative to transformationally based solutions 
of the problems encountered in automatic syntactic 
analysis t and consequently~ to the transformatlona~ 
model itselfo In particular, the new model claims to 
compete favorably with the transformational one ~> 
generative power and structural characterlzatio~; .J 
sentences. 
Central to this model is the notion of a "multi-level" 
or "stratified" grammar. The generation of a sentence 
at the highest ("deepest") level of the grammar pro- 
ceeds by a set of context-free (CF) rules| the output 
of these rules is then transduced to lower levels by 
a series of pushdown store automata. The output of the 
final transduction is some "surface" representation 
of the sentence to be generated. 
Me¥ 3 
2. CF-Preservatlon under Transduction 
The whole system des£ribed in the preceding section is 
said to be "weakly equivalent to a CF phrase structure 
grammar" (1:148, 221). This assertion is claimed to 
derive from theorems formulated by N. Chomsky and Ro 
J. Evey (3; 4), which maintain that the output of a 
pushdown store transducer (pdt) is equivalent to the 
set of CF languages (i:109; 2:2.2.5). 
However, the original theorems about this equivalence 
concerned pushdown store acceptors (pda), not trans- 
ducers (pdt as defined by Ginsburg (5:102)); for pdt 
(as used by Sgall and his group) t CF-preservation is 
known not to obtain in general (5:104). 
The condition under which pdt will preserve CF langua- 
ges is stated by Ginsburg in Th. 3.5.1. (5:104)'. 
given a pda M t a pdt S, L - T(M), 
S(L) is CF Iff M and S are associated, i.e. S is ob- 
tained by adding outputs to M, the pda that accepts L. 
For the case of the Czechoslovak "battery" of trans- 
ducers, this condition could actually be fulfilled, 
although the authors never say so, explicitly° I am 
Mey 4 
referring to their extra condition on the system, 
as formulated in "the existence of inverse automata 
for the single levels of the pushdown part \[of the 
grammar, JM\] " (1:146). Hence the impreciseness of 
the Czechoslovak proposal may amount to no more than 
a matter of incomplete formulation. 
In a recent article, however,- Ginsburg and Rose (6) 
have shown that the earlier theorem on which they 
based CF-preservatlon conditions for pdt is false° 
(And~ by the same tokenp so are the original theorem 
of Evey's (4:2°6°6) and an earller theorem by Ginsburg 
and Rose (7:3.2)). According to the 1968 revised ver- 
sion of the latter ~heorem by Ginsburg and Rose (6:3® 
2~)~ CF~p~eserva~ion is made dependent upon an addl- 
tlona~ condition on the pdt~ n~m~y~ that o~ ~est~Ict- 
ing its ou~pu~ %o '~hese strings that are produced by 
the device when it ends up in an accepting (oz final) 
state, In all other cases~ the language generated by 
the pdt will not be equivalent to the set of CF lan- 
guages, but simply constitute a ~ecurslvely enumer- 
able se%~ 
Mey 5 
3. Practical Consequences for the Prague System 
For the case under consideration, the new insight re- 
ferred to in the preceding section has two slgnlfl- 
cant consequences: 
first, the worries of the Czechoslovak group to ensure 
CF preservation may well have been in vainf unless 
the new condition can be incorporated into their sys- 
temo Otherwiset a device that is practically equlva- 
lent to a Turlng machine is not very exciting to work 
with in computatlonal linguistic theory or its imple- 
mentation. 
Second~ one of the advantages inherent in the use of 
CF-preservlng transducers is the guaranteed existence 
of a whole bevy of working recognition routines (e.g., 
the Cocke-Roblnson algorithm, the parser developed 
by Kay I or the predictive analyzer by Kuno, etc.) 
This advantage becomes illusory if the pdt battery 
produces a recursively enumerable languaget ioe. one 
that cannot be guaranteed to be recognized by a CF- 
recognition routine. 
If we think of the Czechoslovak system as part of a 
Mey 6 
machine translation proposal, where the route from 
source to "Interllngua" consists of essentially the 
same flow (but in the opposite direction) as that 
from "interllngua" to target language, it appears 
that the consequences of an incorporation of the 
Ginsburg-Rose adjustment are far-reaching. Such an 
incorporation could take place in two ways: either 
one could check the output of a particular (~-th) 
device, transducing from a higher (~-th) to a lower 
(~ - lth) level, or from a lower (~-th) to a higher 
(~ ÷ lth) level~ to see whether or not this output 
corresponds to an accepting state (where "higher" 
and'~oweE" are understood to refer to deeper and 
more superficial structures respectively); oft al- 
ternatively, a built-ln checking device could prevent 
output from being generated unless the transducer 
reached an accepting state after reading the input 
string. So far t Sgall and his group have not sugges- 
ted ways to handle this problem. 
Quite another matter is that the Prague group's p£o- 
posal to let the output of the ~-th de,ice be • pro- 
per s~bset of the input of the ~ + Ith~ ~ - Ith 
Mey 7 
transducer respectively, does not seem to be fruitful, 
or even feasibleo Naturallyp the first question that 
arises is: what about the remaining input, where does 
it all come from? It is certainly true, as the authors 
remark (2:2o2o5)~ that "the output language of the 
whole description is not necessarily context-free"o 
AS shown above, it simply never is under the given 
conditions. Hence the reason given in the rest of the 
quote is trivial: "since °.. it is only a proper sub- 
aet of the context-free languages of the last pushdown 
transducer" (ibld.)o While it is always possible to 
tame a prope~ subset of a CF language and obtain a 
language tha% i~ not C2~ or maybe not even reguiar~ 
that cleaxly i~ not the point here. The authors in~nd 
their output language to be CF~ for reasons llk~ the 
ones mentioned above° As long as it can be shown (as 
I have done here) that the system in no case is (even 
weakly) equivalent to a CF grammar~ the question of 
the restrictions on the input to the subsequent trans- 
ducers is t of course, irrelevant to the CF character 
of the system as a whole. 
Mey 8 
4. Some theoretical implications 
The proponents of the Prague model have repeatedly 
asserted that their system has certain advantages 
over other models of linguistic performance and, in 
particular t that their grammar is superior (or at 
least equivalent) to transformational grammar. 
The claim that the level-based model is superior to 
others because of easy CF-recognitlon has been. dispro- 
ved in the preceding sections. Another claim, that of 
greater naturalness inherent in the level-orlented 
model, is also often made (sometimes implicitly by 
reference to the model's stance in tlme-honored lin- 
guistic tradition). It should be observed t however~ 
that such a claim does not concern the formal charac- 
ter of any system. As Chomsky has pointed out (in his 
discussion of Fillmore's case theory (8:14-16)) I it 
is vacuous to discuss different formal systems in 
terms of which is the more "direct" representation 
of natural language; unless a formal system is inter- 
preted 0 it slmply cannot be compared to another one 
for "~Lrectneee" of expression. 
But how about transformational grammar itself with 
Mey 9 
respect to sentence recognition? It has been kno~ 
for a long time that there is no way of establlshing 
a universal automatic recognition procedure for a 
tr~sformatlonal grammar that is not in some ways 
restricted° This was precisely the Prague group's 
motivation for proposing their system as a (superior) 
alternatlve to TGo Now that their clalms have been 
de-substantlated on theoretlcal grounds, it may seem 
like a meagre consolation to the Prague ~oup that TG 
itself is in the same boat, theoretically speaking. 
In an important recent study~ Peters and Ritchle have 
demonstrated that a context-sensltlve (CS) based 
transformational grammar~ unless restricted in some 
respecta~ generates a recurslvely enumerable language~ 
and conversely, for any recurslvely enumerable language 
there is a CS based TG that will generate it (9:4.1). 
As the authors point out (ibido:33), it is imperative 
to set out and find conditions under which a TG will 
generate only recurslve languages. One such condition 
would be to restrict the base of a TG to be CF; however t 
t-nls will still not guarantee recurslvlty (9:4.2)° 
This is preclsely the problem that the Czechoslovak I 
workers will have to solve in order to make thelr system 
vlable and to valldate their claims. 
Mey 10 

References 

(I) Po Sgall, Generativn~ Po_o~Jazvka a ~esk~ Dek~inace, 
Prague 1967. 

(2) "Po Sgall & alo, A Functional Approach to S~tax, New 
York 1969 (in press)° 

(3) No Chomsky t ~Fo~mal Properties of Grammars", in: 
~. Luc~ Ro Bush & Eo Galan%e~ (edd~)~ 
Handbook of Mathematical PsycholoqY, II, 
New York 1963, ppo 523-4180 

(4) ~o Evey~ The Theo._~ an_~d Appl&catlon o~ Pushdown 
Sto~e Machines, Cambridge, Mass°, 1963. 
(doct° disso) 

(5) S. Ginsburg, Th.se Mathematical TheorM of Context- 
Fre___.~eGrammars, New York 1966° 

(6) S® Ginsburg & G. Rose, "A Note on Preservation of 
Languages by Transducers", info Contr. 
12(1968):549-552° (See also (I0), below) 

(7) S. Ginsburg & G. Rose, "Preservation of Languages 
by Transducers", In~fo Contr. 9(1966): 
153-176. (See also (I0), below) 
Mey 11 

(8) N° Chomsky, Deep Structure, Surface Structure, 
and Semantic Interpretation (mlmeo- 
graphed)p M°I.To 1968 

(9) 5. Peters & R. Ritchie, On the Generative Power 
off Transformational Grammars(mimeo- 
graphed)~ TeCho Report CSClo 69-2-3-e 
The University of Washington, Seattle 
1969. 

(I0) J. Mey~ Review of Glnsburg & Rose (6) 9 Combo Re..~v. 
lO(May 1969), in press. (This review 
contains a succinct statement of the 
contents of (6) and (7), as well as 
a historical footnote on the author- 
ship of the maln theorem of Section 
2 of (7) and Its revised form as pre- 
sented In (6)). 
