Formal language

Also known as: Language

A formal language $L$ over an alphabet $\Sigma$ is any set of strings from $\Sigma^*$. Not “English.” A collection of inputs you count as yes.

Examples: all valid emails, all digit strings matching ^[0-9]+$, all event sequences that leave a door safe. One particular string is a member of $L$; $L$ itself is the set.

Grammars generate members; automata accept or reject them. Regular languages are the ones finite automata / regex can describe. Larger classes need pushdowns, Turing machines, and so on.

← Back to CS Glossary