title: "Language"

Language

Definition. A language over an alphabet $\Sigma$ is a set of strings, that is, a subset of $\Sigma^*$ (the set of all finite strings over $\Sigma$).

A language and a decision problem are the same object seen twice: the problem "does the input have property X?" is the language of strings with property X. From Lecture 3 on, machines are judged by the language they recognize. Defined in Lecture 2.