Formal Language

In mathematics, a formal language is normally defined by an alphabet and formation rules. The alphabet of a formal language is a set of symbols on which this language is built. Some of the symbols in an alphabet may have a special meaning. The formation rules specify which strings of symbols count as well-formed. The well-formed strings of symbols are also called words, expressions, formulas, or terms. The formation rules are usually recursive. Some rules postulate that such and such expressions belong to the language in question. Some other rules establish how to build well-formed expressions from other expressions belonging to the language. It is assumed that nothing else is a well-formed expression.

For example, the language of propositional calculus could be defined as follows. The alphabet of this language is comprised of English letters with optional indexes and the following special symbols:  (NOT),  (AND),  (OR),  (implies), and  (grouping). The formation rules are then that every English letter and every letter with an index is a formula, and if  and  are formulas, then so are , , , , and .

Formation rules are sufficient for defining simple languages. More syntactically complex languages are defined by means of grammars or regular expressions.

The formation rules of propositional calculus and most other formation rules can be straightforwardly transformed into grammar productions. For example, the formation rule  becomes the production , where  is the start symbol.

REFERENCES

Aho, A. V. and Ullman J. D. Theory of Parsing, Translation and Compiling, Vol. 1. Englewood Cliffs, NJ: Prentice Hall, 1972.

Aho, A. V. and Ullman J. D. Theory of Parsing, Translation and Compiling, Vol. 2. Englewood Cliffs, NJ: Prentice Hall, 1972.

Kleene, S. C. Introduction to Metamathematics. Princeton, NJ: Van Nostrand, p. 39, 1964.

Wolfram, S. "Computation Theory of Cellular Automata." Comm. Math. Phys. 96, 15-57, 1984.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 893, 2002.