Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!cmcl2!rutgers!mcnc!ece-csc!ncrcae!ncr-sd!hp-sdd!ucsdhub!sdcsvax!nosc!humu!uhccux!lee
From: lee@uhccux.UUCP (Greg Lee)
Newsgroups: sci.lang,comp.ai
Subject: Re: Infinte alphabets (and CFness of NLs)
Message-ID: <970@uhccux.UUCP>
Date: Sun, 18-Oct-87 14:13:25 EDT
Article-I.D.: uhccux.970
Posted: Sun Oct 18 14:13:25 1987
Date-Received: Mon, 19-Oct-87 02:02:58 EDT
References: <154@Aragorn.UUCP> <114400001@exunido.UUCP>
Organization: U. of Hawaii, Manoa (Honolulu)
Lines: 70
Xref: mnetor sci.lang:1588 comp.ai:924

In article <448@russell.STANFORD.EDU> goldberg@russell.STANFORD.EDU
 (Jeffrey Goldberg) writes:
*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
*>...
*
*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).

He does not deal with all unbounded dependencies, because they cannot
in general be expressed in a CFPSG.  If there is a problem with the
argument I gave it would hinge on whether unbounded phonological
dependencies are of the sort which can be expressed in a CFPSG.  I don't
know whether they are.  For the special case of a transparently
applying phonological rule, i.e. one whose conditions are met in the
pronunciation, it seems to me that unbounded phonological dependencies
could indeed be expressed, by the device of "foot initial features"
which propagate up the tree from left-most daughters, "foot final
features" which propagate up from right-most daughters, and appropriate
agreement rules. So, upon more careful consideration, I would say my
argument was incomplete, at best.

*
*>Suppose now that we apply the same reasoning in the case of phonology.
*>...
*
*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.
*
Yes, that is what I'm saying.  And of course regular languages are
context free, so that possibility is included.  So far as I'm aware,
all the evidence that has been cited in favor of language being context
free also supports the hypothesis that language is regular. (Remember
Ingve's "A Model and an Hypothesis for Language Behavior"?)

*>Because of the qualification in my original posting, I concede in
*>...
*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.
*
alphabet = segments of adequate transcription system

*>(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.
*
Look at his footnote 4.  Is he right that the optionality of
objects makes no difference to his argument?  One can't simply
take an intersection with a language `... some number of verbs ...
same number of nouns' because this is not regular.

*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