Before machines, a shared vocabulary. Everything in the theory is built from sets, sequences, functions, and graphs.
Definition · The essentials
- A set is an unordered collection; a sequence (or tuple) is ordered.
- An alphabet Σ is a finite set of symbols; a string is a finite sequence over Σ.
- A language is a set of strings — a subset of Σ*, the set of all strings.
- A function f : A → B maps each input to one output; a relation relates elements more freely.
The empty string ε has length 0. The set Σ* is infinite, but every individual string in it is finite — a small distinction that quietly powers many later arguments.
Why languages?
Recasting every computational problem as “is this string in this language?” lets one theory cover parsing, arithmetic, graph problems, and logic all at once.