formal language

Symbols can represent types of events, words in a sentence, or anything else. Formal language theory studies just the form of language, not its interpretation.

The classes of languages studied most intensively are those of the Chomsky hierarchy.

Some examples of formal languages:

• The set of binary strings that are the binary representation of a number divisible by 3. This language is regular.
• The set of well-formed arithmetic formulas (i.e. with matching parentheses etc). This language is context-free.
• The set of tautological (i.e. true) formulas in boolean algebra. This language is recursive.
• The set of provable arithmetic formulas (which can contain variables and logical quantifiers.) This language is recursively enumerable.
• The set of true arithmetic formulas. This language is undecidable. (hi Gödel!)