Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!bloom-beacon!oberon!cit-vax!ucla-cs!zen!ucbcad!ames!aurora!labrea!russell!goldberg
From: goldberg@russell.STANFORD.EDU (Jeffrey Goldberg)
Newsgroups: sci.lang,comp.ai
Subject: Re: Infinte alphabets - (Turing via Berke)
Message-ID: <434@russell.STANFORD.EDU>
Date: Fri, 16-Oct-87 04:23:13 EDT
Article-I.D.: russell.434
Posted: Fri Oct 16 04:23:13 1987
Date-Received: Sat, 17-Oct-87 18:46:47 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: 51
Xref: mnetor sci.lang:1568 comp.ai:902

In article <959@uhccux.UUCP> lee@uhccux.UUCP (Greg Lee) writes:

>The number of phonetic characters must be finite if language is context-free.

That is true, but it is uninformative.  Any recursively enumerable
language will have a finite terminal vocabulary.

>There are apparent context sensitivities in pronunciation, such as for
>some English speakers, pronouncing "band" as "bam" before a word beginning
>with "p", as in "The bam played on".

"Context Sensitive" and "Context Free" are technical terms.  You
can get into trouble by using both the technical and non technical
meanings in the same argument.

>Yet such context sensitivities may
>be represented in a context-free grammar, provided that the sensitive item
>and its context are not separated by an unbounded number of constituent
>boundaries.

Dependencies over arbitary distance can be maintained in a CF
grammar:

S -> a B a
S -> c B c
B -> b B
B -> b

(lowercase letters are terminal symbols.)


>Perhaps, though, language is only almost context free, failing to be
>so through having an infinite number of terminal symbols.

The linguistics literature from 1960 to 1985 is filled with
arguments about why NLs are not CF.  All of those arguments had
holes in them.  In 1985, however, two mathematically well founded
arguments were published in the "Linguistics and Philosophy".  One
by Christopher Culy and the other by Stuart Shieber.

The whole question raised had to do with writing systems, and I
don't quite see what this has to do with the (mathematical) class
languages fall into.

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


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