形式语言

在逻辑学与计算机科学中, 形式语言由符合一些规则的、按顺序写下的符号组成, 这样的符号串又叫字符串, 而形式语言则是所有符合规则的字符串的全体. 例如, 多数编程语言是形式语言; 逻辑学中的一阶语言也是形式语言, 是主流数学的基础的一部分.

在一门形式语言中, 所有可能出现的符号的集合称为字母表.

描述形式语言的规则一般叫做文法, 例如形式文法.

1定义

定义 1.1 (形式语言). 令 $V$ 为有限集. 则以 $V$ 为字母表的形式语言是指 $V$ 上的自由幺半群 $V^{*}$ 的子集.

可以看出, 语言里的元素就是按顺序写出 $V$ 里的元素, 这也是它被叫做字母表的原因.

•

术语翻译

形式语言 • 英文 formal language

字符串 • 英文 string

字母表 • 英文 vocabulary