A formal language is a set of strings of symbols that may be constrained by rules that are specific to it.

$\Sigma^*$ is the set of strings formed by symbols in the set $\Sigma$.

Relations to compilers, parsers, etc. Grammars, etc.

A nice new language for this: Ohm

See Automata theory, Grammar.

Chomsky hierarchy. (see also Theory of computation).

Mathematics - Formal Languages and Automata Theory

Probabilistic languages and grammars

See paper on algorithmic probability by Solomonoff.