a formal language

In everyday speech a language is a way of communicating, but in this theory the word is stripped down to something far simpler and sharper: a language is just a set of strings. Pick an alphabet, look at all the strings you could write with it (that is Σ*), and then choose any collection of them you like. That chosen collection is a language. It is a guest list, not a grammar lesson: it says which strings are in and which are out, and nothing more.

Formally, a language L over an alphabet Σ is any subset of Σ*, written L ⊆ Σ* (L is a subset of Sigma-star). Because it is just a set, the strings in L need not share any obvious pattern, though the interesting languages do. Examples over Σ = {0, 1} include the language of all strings ending in 0, the language of all strings with an even number of 1's, and the language { 0^n 1^n : n is at least 0 } of equal blocks of 0's then 1's. A language can be finite (like { ab, ba }) or infinite (like all strings of even length), and a single language can contain ε or not.

This definition is the great leap of the whole subject. Once a language is just a set of strings, recognizing a pattern, deciding a yes/no problem, and accepting an input all become the same activity: testing whether a given string belongs to a given language. That is why languages are the common ground on which automata, grammars, and complexity classes are all compared. Honesty check: do not confuse the language (the set of strings) with the device that describes it. A finite automaton, a regular expression, and a grammar are different ways to specify a language, but the language itself is just the set.