[Prev][Next][Index]

# Grammars and Uncountable Sets


In SetBasics.lsl, I see:

% Essential finite-set operators

and

C generated by {}, insert

Why are the set traits limited to denumerable sets? Granted, it's nice
if you're interested in doing induction proofs. But I'm interested in
talking about grammars and languages. Languages are not, in general,
countable. But it's still useful to use the \in, {E}, \U, \I, -
operators on them.

Hmmm... Perhaps the answer is in RelationOps.lsl:

e \in r == e \langle r \rangle e;

So I suppose relations can be used for uncountable sets. Is this
the "recommended" strategy?

By the way... has anybody else done traits for grammars and such
(finite state machines, regular and context free grammars, parse
trees, derivations, ...)?

I'm working on clearing up some issues in the HTML spec (as I have
been for years...). The HTML spec has to say how an SGML document
is represented in a MIME body part, and so I need a pretty rigorous
definition of an SGML document, including a definiton of characters,
coded character sets, etc. Fun, huh? (NOT)

Along the way, I thought I'd work out a reasonably formal definition
of an SGML document, ala:

An SGML document is a pair (D, G, I) where D is a function
that "tokenizes" the sequence of characters I into a sequence
of terminals in the context-free grammar G. The resulting
string of tokens is in the language generated by G.

Well... this isn't a definition so much as a necessary condition. The
SGML standard includes a bunch more conditions for some unknown reason.

Daniel W. Connolly        "We believe in the interconnectedness of all things"
Research Technical Staff, MIT/W3C
<connolly@w3.org>             http://www.w3.org/hypertext/WWW/People/Connolly



Follow-Up(s):