形式陈述

字母表 $\Sigma$$\mathrm{\Sigma }$ 是有限非空符号集，$\Sigma^*$${\mathrm{\Sigma }}^{\ast }$ 是由其符号构成的所有有限字符串集合，包括空串 $\varepsilon$$\epsilon$。一个形式语言是任意子集 $L\subseteq\Sigma^*$$L\subseteq {\mathrm{\Sigma }}^{\ast }$。

直觉

语言把“哪些输入被接受”与输入的具体意义分开。识别器、文法和逻辑公式都可以用它们定义的字符串集合比较能力。

例子与边界

$\{0^n1^n:n\ge0\}$$\{0^n{1}^n:n\ge 0\}$ 是二进制字母表上的语言。形式语言不必是自然语言，也不必存在有限描述；不可数多个语言中只有可数多个能由程序识别。

推论与应用

正则语言、上下文无关语言、可判定语言和复杂度类都把语言作为决策问题的标准表示。

参考资料

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., §0.2.
• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Chapter 1.