Re: Uses for CSS?

NOTE: I have redirected this to the theory-list, since we are moving into
mathematical formalities (which, for some reason, the bulk of the
subscribers of the HWG lists (to be referred to further as "the hoipolloi")
feels to be babbling (if I remember correctly from the thread on the
definition of "valid"). To keep from upsetting the hoipolloi I suggest we
continue this thread on that list.
A copy of this has been sent to the -standards list by way of notification.

-----Original Message-----
From: John M. Allen <jallen(at)thunder.ocis.temple.edu>
To: Ben Z. Tels <optimusb(at)stack.nl>
Cc: hwg-standards(at)hwg.org <hwg-standards(at)hwg.org>
Date: donderdag 28 mei 1998 12:32
Subject: Re: Uses for CSS?


>>> Actually, it is not. Both HTML and English can be represented using
>>> formal languages.
>>
>> English? A formal language?
>
>No, what I said was that English can be REPRESENTED using a formal
language.


In that case, you will be limited to a subset, or you will not be able to
capture all the finer point of the language.

>> That's a good trick. Care to show me how it's done?
>
>As I said, there have been a number of attempts. I haven't kept up with it
>recently, but they include GPSG (Generalized Phrase Structure Grammar), GB
>(Government and Binding), and HPSG (Head-Oriented Phrase Structure
Grammar). Any
>university with a linguistics department should have books available on
these
>subjects in their library.


And I'm sure there is one in my department at the university as well, for
use in the study of speech recognition by computers (and other subjects in
the field of Formal Languages). However, the nature of natural languages
(including synonymity, homonymity, several other such phreases for which I
do not know the English term) and alteration of meaning by context and/or
inflection is too difficult to capture. There is not enough logic in it, not
enough formality.

Although it might be possible to translate the strict grammar of a natural
language into a set of production rules, it will never lead to a formal
language which adequately describes the entire language.

>Actually, both of these have been formally described. Homonyms simply have
an
>entry in the lexicon for each meaning.

And what, in a formal language, is a lexicon?
Unless of course you are proposing to formulate a grammar with a bag of
terminals instead of a set? Otherwise a lexicon will not help you.

>There is simply no reason to encode as
>part of the language that one word sounds like another. In fact, there are
>reasons to believe that having separate entities reflects what actually
happens
>in a speaker's mind.[1] The case with synonyms is much more complicated,
because
>you actually have to look at the meanings of the words. It involves
specifying
>that the set of objects defined by each of the words is the same in all
possible
>worlds.


World = universe???

This specification might or might not lead to correct results.

>There is nothing about formal languages, per se, that requires them to be
>unambiguous. Now certainly, ambiguity is undesirable in a programming
language,
>but that is a restraint that has been put on by the designers. It is not
>inherent in formal languages. In fact, in order to model English, you have
to
>have ambiguity, because natural languages are ambiguous.


Yes, you are right.

>> Oh, neither. At the very least it would have to be Turing-calculable
only.
>
>No, the human brain is simply too limited to have any human language be
>Turing-calculable,

You can prove this? I think not.

>In fact,
>the reason that Context Free is preferred over Context Sensitive is that
even
>Context Sensitive may be too much of a mental burden to explain the
facility
>with which humans learn languages as kids.


Unfortunately, you cannot have a natural language without context. See your
own example of "can".

I think we are treading dangerously here, trying to relate "mental burden"
(whatever that may be) to the structure of a language.

>> BTW, context-sensitive is not a class of formal language. Context is an
>> addition to a formal language (although you can probably simulate context
in a
>> Turing-machine).
>> Known classes of languages:
>> Regular languages
>> Context Free languages (with determinsitic PDA's and then NPDA's)
>> Turing-calculable
>
>It has been several years, but if I remember correctly PDA's and NPDA's are
not
>equivalent.

This is why I made the distinction. Note that I did not mention DFA's and
NFA's for regular languages, because they are equivalent.

>Context Free languages can be parsed/produced by PDA's and Context
>Sensitive languages can be parsed/produced by NPDA's.

Yes, but they are both automata associated with CFL's [0]. Context is an
extension to the CFG[0], which is why the number of languages produced by
NPDA's is larger than the one produced by DPDA's.

>I do remember enough to
>know that Context Sensitive most certainly IS a class of formal language.


It is not. Context is an extension to CFL's.

Do you remember the defintion of "class"? It is a subbset formed by a
partitioning.
Partitioning is based on equivalence relationships. This implies that
classes of a set are disjoint.
However, the set of deterministic context-free languages is a subset of the
set of context-free languages (all of which are described by by CFG's and
producable by NPDA's [0]). Therefore, the set of "context-sensitive
languages" and the set of CFL's are not disjoint. Therefore they are in the
same class.

[0] Actually, it is the other way around; "context-free" (and I will refer
to this as deterministic context-free (the official term) from now on) is a
limitation of non-deterministic context free.

An NPDA is a septuple M=(Q,Sigma,Gamma,delta,q0,z,F) [1]

with

Q a finite set of internal states of the "control unit"
Sigma the input alphabet
Gamma the finite set of symbols called the Stack Alphabet
delta the transition function
         delta: Q x (Sigma U {lambda}) x Gamma --> V={x | x finite, x subset
QxGamma*}
         lambda = unity character or the "empty"character
         |V| >= 0 (|V| = cardinality of V = number of elements of V)
q0 element of Q the initial state of the control unit
z elemnt of Gamma the stack start symbol
F subset of Q the set of final states

A DPDA is the same septuple, with delta:Qx(Sigma U {lambda})xGamma --> V={x
| x finite, x subset QxGamma*}
but now with |V| = 1 OR |V| = 0 for every disjoint triple (q elemnt Q, a
element Sigma x {lambda}, b element Gamma},
so that there is no choice in the transition from one state to the next.[1]

That makes determinism a limitation of non-determinism for context-free
languages.

[1] "An Introduction to Formal Languages and Automata" by Peter Linz

Ben Z. Tels
optimusb(at)stack.nl
http://www.stack.nl/~optimusb/

"The Earth is the cradle of the mind, but one cannot stay in the cradle
forever."
                                                    --Tsiolkovsky

HWG hwg-theory mailing list archives, maintained by Webmasters @ IWA