形式语言

1. 概述

在 逻辑学 中, 形式语言 是由一些满足特定规则的 符号 (或称 字符) 所生成的, 这样的符号串又称为 字符串. 而 字母表 则是这些可能出现的符号的全体.

2. 定义

定义 1 (形式语言)

设 为 有限 或 可数 的 字母表, 称 自由幺半群 中的 子集 为以 为字母表的 形式语言.

记号 2 (形式语言)

通常将 形式语言 记为 , 即英语中 “Formal Language” 中语言的首字母.

注记 3 (形式语言)

在不同的场景与学科下, 形式语言 的定义稍微有些许差别, 例如：

场景	字母表 是否允许 无限多个元素	原因
逻辑学 / ZFC 集合论	通常允许 可数多个元素	具有更强的表达力
计算机科学	通常不允许	保证可计算性
类理论 / 大基数理论	可能涉及 不可数多个元素	处理一些超出 集合论 范畴的问题

3. 例子

例子 4 (初步例子)

• 设 字母表 为 , 则 这些由二进制字符串 所构成的集合是 的 形式语言.
• 设字母表为 , 则 亦是 的形式语言.
• 特别地若 , 则 为 的形式语言.

4. 相关概念

• 字母表
• 一阶语言
• Zermelo-Fraenkel 集合论
• ZFC 集合论

5. 术语翻译

中文	英文
符号	symbol(s)
字符串	string
字母表	alphabet
形式语言	formal language

逻辑学