Formal language

Summary

A formal language over an alphabet $\Sigma$ is any set of strings over $\Sigma$. Formal languages describe the syntax of programming languages and of logic, and they model decision problems. They are classified by the machines or grammars that describe them, from regular languages up to recursively enumerable languages. Operations such as union, concatenation and Kleene star build new languages from old ones.