##### 形式语言 - 形式语言 - **形式语言**是通过一组符号和规则来定义的[[语言]], 与自然语言相比它的语法是精确且形式化的, 没有歧义, 通常用于逻辑学, 数学和计算机科学的[[形式系统]]中. 具体来说, 形式语言是由[[字符串]]组成的[[集合]], 这些字符串的字符取自[[字符集]], 并且根据一组称为[[形式语法]]的特定规则形成良好的形式. 形式语言本质上完全是研究语法的不考虑语义, 但可以赋予形式语义 - 形式语言, 是由字符串组成的集合, 记为 $L \subseteq \Sigma^*$, 其中 $\Sigma^*$ 是字符集上所有可能字符串的集合, 包括空串, 例如形式语言可以是 $L = \{a, ab, bba\}$ - 字符集, 是由符号构成的有限集合, 记为 $\Sigma$, 符号可以是任何离散的实体, 比如字符, 数字, 或者更抽象的记号, 例如字符集 $\Sigma = \{a, b, c\}$ 有三个符号 - 字符串, 是由字符集中的符号按顺序排列而成的有限序列, 空串 $\varepsilon$ 是一种特殊的字符串, 长度为 $0$, 例如对于 $\Sigma = \{a, b,c\}$ 字符串可以是 $bba$ - 形式语法, 定义了形式语言的产生规则, 通常以形式化的方式描述哪些符号组合是有效的, 哪些组合是无效的 - 形式语义, 赋予形式语言元素意义, 在数理逻辑中通常以模型论的形式进行, 每个公式赋予真值意义, 公式中出现的项被解释为数学结构中的对象