什么是语言？

数理逻辑和编程语言

关于归纳定义、推理规则，可参见从不动点定理到编程语言
在数理逻辑中，我们有字母表（Alphabet）；在编程语言中，我们有字符集（Character Set）
- 在数理逻辑中，字母表的元素称为字母（Letter）；在编程语言中，字符集的元素称为字符（Character）
群论
- 设为集合。那么，生成
  - 自由半群（Free Semigroup） $S(A) = \cup_{n \geq 1} A^n$
  - 自由幺半群（Free Monoid） $M(A) = \cup_{n \geq 0} A^n$ ，它具有单位元素 $\emptyset$
  - 自由群（Free Group） $F(A)$ ，它具有逆元素 $a^{-1}$ ， $a \in A$
- 设为群
  - 由群论的结果可知，对任意映射 $f: A \to G$ ，存在唯一的自由扩张 $\widetilde{f}: F(A) \to G$ 。在Shannon熵中，唯一译码的编码需要使用半群上的自由扩张
  - 设 $A$ 为 $G$ 的一个生成元集。那么，含入映射 $i: A \to G$ 有自由扩张 $\widetilde{i}: F(A) \to G$ 。因为 $\widetilde{i}$ 为满同态，所以我们有同构
    $F(A) / ker\widetilde{i} \cong G.$
  - 设 $R$ 为 $ker\widetilde{i}$ 的一个生成元集。那么，我们称字母表 $A$ 、关系 $R$ 为群 $G$ 的一个表现，记为 $G = \{ A | R \}$ 。如果 $A$ 、 $R$ 为有限的，那么 $G$ 称为有限表现群；如果 $A$ 为有限的，那么 $G$ 称为有限生成群
在数理逻辑中，字母表生成字（Word）；在编程语言中，字符生成字符串（String）
- 在编码理论中，比如一般线性编码，我们考虑 $A = \mathbb{F}_2$ 或者 $\mathbb{F}_q$ 。 $A$ 生成二进制串（Bitstring）或者 $q$ 阶串（ $q$ -ary String），它们是机器语言
词法（Lexicon）
- （数理逻辑）表达式（Expression）由字、推理规则归纳定义
  - 项（Term），比如Lambda演算的Lambda项
  - 公式（Formula），比如命题逻辑（Propositional Logic）的公式
- （编程语言）单词（Token）由字符串、推理规则归纳定义
  - 保留字（Reserved Word），比如由公理定义
  - 正则表达式（Regular Expression），比如由推理规则定义
句法（Syntax）
- （数理逻辑）句子（Sentence）由表达式、推理规则归纳定义
  - 比如谓词逻辑（Predicate Logic）中的句子
- （编程语言）程序（Program）由单词、推理规则归纳定义
  - 比如可计算函数的编程语言PCF中的程序
- 我们通常用上下文无关语法（Context-Free Grammar，CFG）来定义句法，它是和归纳定义、推理规则等价的定义方法。比如，对于从不动点定理到编程语言中的语言，其上下文无关语法为（竖线表示“或者”）
  - t = b | atc
语义（Semantics）
- （数理逻辑）句子的计算称为演算（Calculus）
  - 比如Lambda演算中的Beta规约
- （编程语言）程序的计算称为求值（Evaluation）
  - 比如求值器（Evaluator）对项求值，解释器（Interpreter）对项、环境求值
  - 编译器（Compiler）将程序翻译为机器语言，然后由机器求值。机器求值是由物理定律决定的