Re: [xmlvoc] Definition: formal language

[Lars Marius Garshol <larsga@garshol.priv.no>]

* Patrick Durusau
| 
| The term for the day is: formal language.

This one is easy if you can write it in maths; it's simply a set of
strings composed of characters from some alphabet (where an alphabet
is just a set of characters). I don't think we can take that approach,
however.
 
| Taylor in Models of Computation and Formal Languages, notes:
| 
| "The term 'formal' is introduced in order to distinguish such
| languages from natural languages, programming languages, and so on. It
| is in fact, possible to regard natural languages such as Spanish and
| programming languages such as PROLOG as formal languages, provided one
| ignores their semantic aspects." (p. 5)

This was pretty good, but is not a definition, unfortunately.
 
| I would suggest something along the following lines:
| 
| formal language: An artificial language that is used to investigate
| the properties of languages in general. As distinguished from
| natural or programming languages that have other primary uses.

I'm afraid this won't work. A formal language is strictly any language
for which a strict definition is given. This can be as a set of all
the strings in the language, as a BNF grammar, as a regular
expression, or in some other way.
 
| Captures the notion that the language is not a "natural" one, i.e.,
| artificial, and notes that it has a primary purpose other than use
| as a programming language.

Actually, purpose does not affect whether something is a formal
language or not. The question is whether it has a formal definition of
its syntax.
 
| Started to say something about how a formal language has a finite
| set of rules that can generate an infinite number of strings from a
| finite alphabet, which obviously excludes even verbose programming
| languages but did not think it would add anything to the definition.

Agreed. That would just be a definition of one way to define a formal
language, rather than a definition of what a formal language *is*.
 
| Lars: Do you want to take a crack at it?

Helped by your initial exploration I think I can:

  formal language: Any language with a defined set of allowed symbols
  and a precise definition of which strings composed from these
  symbols are considered syntactically correct. The syntax definitions
  of formal languages are often given as BNF grammars or regular
  expressions, but a formal language can be defined in any way so long
  as the definition is mathematically precise and it can also serve
  any purpose.

What do you think?

-- 
Lars Marius Garshol, Ontopian         <URL: http://www.ontopia.net >
GSM: +47 98 21 55 50                  <URL: http://www.garshol.priv.no >