formal language (thing)

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!)