Date: Sun, 9 Feb 2003 20:56:51 +0100 From: Erik Trulsson <ertr1013@student.uu.se> To: Rahul Siddharthan <rsidd@online.fr> Cc: Mark Murray <mark@grondar.org>, Dag-Erling Smorgrav <des@ofug.org>, chat@freebsd.org Subject: Re: languages Message-ID: <20030209195650.GA38369@falcon.midgard.homeip.net> In-Reply-To: <20030209192309.GA21962@papagena.rockefeller.edu> References: <20030209181722.GA19704@papagena.rockefeller.edu> <200302091826.h19IQBaX035066@grimreaper.grondar.org> <20030209184658.GA19887@papagena.rockefeller.edu> <20030209191203.GA37952@falcon.midgard.homeip.net> <20030209192309.GA21962@papagena.rockefeller.edu>
next in thread | previous in thread | raw e-mail | index | archive | help
On Sun, Feb 09, 2003 at 02:23:09PM -0500, Rahul Siddharthan wrote:
> Erik Trulsson wrote:
> > The definition of "language" in mathematics (which is also used in
> > computer science) is as follows:
> >
> > An alphabet L is a finite non-empty set of symbols.
> > Let L* be the set of all strings of elements in L (including the empty string.)
> > A _language_ over L is a subset of L*.
> >
> > Note that this is a very broad definition and does not concern itself
> > with any meaning of a language.
>
> Well, it arguably defines a vocabulary.
> What about syntax, grammar? Aren't those part of a language?
That is included in the above defintion.
Note that "symbols" can include things like space and newline.
This means that for example the following
int main(void)
{
return 0;
}
is a string over the set of ASCII symbols. It happens to be a valid C
program while the following
aad sdfsd &734 11
s
s
dfsdf
43534
which is also a string over the set of ASCII symbols is not a valid C
program. Both are obviously elements of ASCII* but only the first is an
element of the subset of ASCII* which is the set of all valid C
programs.
To define a particular language over some alphabet you need to give
some kind of description on which strings are part of the language and
which are not. I.e. you need to define which subset of L* you are
talking about, since each subset defines a separate language.
A grammar is a very useful way of doing that for a large class of
languages. (Actually I believe that all languages in the above sense
can be described by a grammar, but for some languages (e.g. English) it
can be quite complicated (and in many cases completely infeasible) to
write a correct grammar that fully describes the language.)
--
<Insert your favourite quote here.>
Erik Trulsson
ertr1013@student.uu.se
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-chat" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20030209195650.GA38369>