= Formal language
{wiki}
A <formal language> over a fixed finite <alphabet> $\Sigma$ is a <set> $L\subseteq\Sigma^*$ of finite <words>. Here $\Sigma^*$ contains every finite <word> over $\Sigma$, including the <empty word> $\varepsilon$. A <formal language> may contain finitely or infinitely many such <words>.<The P versus NP Problem by Stephen A. Cook>[§1, finite alphabets and languages]{ref}
For example, $L=\{a^nb^n:n\geq0\}$ over $\Sigma=\{a,b\}$ contains $\varepsilon$, `ab` and `aaabbb`, but not `abab`. The notation specifies a <set> of permitted <words>; it does not itself give a <running time> for deciding membership. The <empty language> $\varnothing$ contains no <words>, whereas $\{\varepsilon\}$ contains one.
<Concatenation of formal languages> combines permitted <words> from two <formal languages>. <Automata theory> and <computability theory> ask which machine models can recognize such <sets>, while <computational complexity theory> asks what resources membership decisions require.
Back to article page
