This section reviews some of the basic results of the formal theory of languages and computation (for further information, the reader is referred to books on the subject such as Hopcroft and Ullman (1979), Salomaa (1973) or Lewis and Papadimitriou (1981)), and in particular, the relation between languages, grammars and automata.