Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!seismo!sundc!sun!decwrl!labrea!russell!goldberg
From: goldberg@russell.STANFORD.EDU (Jeffrey Goldberg)
Newsgroups: sci.lang,comp.ai
Subject: Re: Infinte alphabets (and CFness of NLs)
Message-ID: <448@russell.STANFORD.EDU>
Date: Sat, 17-Oct-87 22:51:14 EDT
Article-I.D.: russell.448
Posted: Sat Oct 17 22:51:14 1987
Date-Received: Sun, 18-Oct-87 22:47:28 EDT
References: <154@Aragorn.UUCP> <114400001@exunido.UUCP>
Reply-To: goldberg@russell.UUCP (Jeffrey Goldberg)
Organization: Center for the Study of Language and Information, Stanford U.
Lines: 68
Xref: mnetor sci.lang:1583 comp.ai:922

In article <969@uhccux.UUCP> lee@uhccux.UUCP (Greg Lee) writes:
>In article <434@russell.STANFORD.EDU> goldberg@russell.STANFORD.EDU
> (Jeffrey Goldberg) writes:
>>In article <959@uhccux.UUCP> lee@uhccux.UUCP (Greg Lee) writes:
>>[stuff ...]

> [ ... ]

>Now, to begin again.  Gerald Gazdar made the point that a local
>context sensitivity, such as a transitive verb occurring always
>with a sister noun phrase, does not prevent a language from being
>context free.  And since there is evidence that such subcategorization
>context sensitivity is in fact local in natural languages, this provides
>us some evidence (not probative) that language is context free.

Gazdar also deals with so-called "Unbounded" Dependencies.  See
"Unbounded Dependcies and Coordinate Structures" in _Linguistic
Inquiry_ 12, 1981.  Also, "Generalized Phrase Structure Grammar"
(Gazdar et al, 1985).

>Suppose now that we apply the same reasoning in the case of phonology.
>If language is phonologically context free, we would predict that
>context sensitivities are local.  It is a commonplace that phonological
>rules tend not to apply across major constituent breaks.  The prediction
>appears to be correct, and so we have some evidence (not probative)
>that language is phonologically context free.

I'm not sure that I follow this argument.  Are you saying: "All
these things involve local dependencies and therefore ought to be
dealt with by a CF grammar."?  That same argument could be applied
equally well (or badly) to conclude that NLs are finite state.

>Because of the qualification in my original posting, I concede in
>advance that this does not provide a very compelling argument for
>finiteness of alphabets.  But the logic, at least, seems clear
>enough:
>	language is context free (hypothesis supported by empirical
>				  argument)
>	if language is context free, the alphabet is finite (obvious)
>	therefore, the alphabet is finite (well known rule of logic)

I'm afraid the logic isn't clear to me.  If a language is is CF (or
CS for that matter) its terminal vocabulary is finite.  Agreed.
But it is not obvious to me how you get from there to concluding
that the WRITING system of a language must employ a finite
alphabet.

>(We could talk about the logic in the Schieber article sometime,
>if you like.)

I think that that would be a refreshing change of topic.

Anyway, I too believe that there are no writing systems based on
infinite alphabets.  But I have nothing more to add to what I have
already said on that topic.

>Greg Lee, lee@uhccux.uhcc.hawaii.edu

-jeff goldberg

-- 
Jeff Goldberg 
Internet:   goldberg@russell.stanford.edu
UUCP   ...!ucbvax!russell.stanford.edu!goldberg
-- 
Jeff Goldberg 
ARPA   goldberg@russell.stanford.edu
UUCP   ...!ucbvax!russell.stanford.edu!goldberg