形式语言
| 形式语言 | |
|---|---|
| 术语名称 | 形式语言 |
| 英语名称 | formal language |
形式语言(formal language)指通过定义语法规则的方式来定义的语言。
通常包括一个字母表，和一组规则，按这个规则可以将字母表中的字母结合成良定义的单词。 在一些领域中，将这里的字母表称为词汇表，称按规则将词汇表中的单词结合成良定义的句子。
形式化在这里的意思是语言具有某种形式，服从某种规则。与规则本身是否被形式化地描述无关。 换句话说，即使以并不形式化的方式描述语言的规则，也应该称为形式语言。
定义
对任意集合 [math]\displaystyle{ A }[/math] ，由集合上的所有串构成集合 [math]\displaystyle{ A^{*} }[/math] ，其（遵循某种规则确定的）一个子集 [math]\displaystyle{ L }[/math] 称为 [math]\displaystyle{ A }[/math] 上的一个形式语言(formal language)。其中，
- 集合 [math]\displaystyle{ A }[/math] 称为形式语言的字母表(alphabet)，元素称为字母(letter)，构成的串称为单词(word)，规则称为文法(grammar)；
- 有时，集合 [math]\displaystyle{ A }[/math] 称为形式语言的词汇表(vocabulary)，元素称为单词(word)，构成的串称为句子(sentence)或公式(formula)，规则也称为文法(grammar)。
特别地，如果一种形式语言有两级结构，通常较低一级使用“字母-单词”，较高一级使用“单词-句子”，且分别称两个级别的规则为词法规则/词法(lexical rule)和句法规则/句法(syntactic rule/syntax)，并合称语法(grammar)。
注：
- 形式语言是相对于非形式化语言来说的，在不需要区分的领域中，也常简称为语言(language)。
- 这里的规则本身仅要求能用于界定一个串是否属于这个语言，不要求其具有某种规则的形式。
- 特别地，空集 [math]\displaystyle{ \varnothing }[/math] 也是 [math]\displaystyle{ A^* }[/math] 的子集，称为空语言。
描述
描述形式语言通常包括两方面：
- 形式语言的字母表；
- 形式语言的构成规则。
规则有以下几种常见的表达方式：
- 集合描述：按集合列举的方式描述集合内的元素。
- 规则描述：通过形式文法、正则表达式等描述规则。
- 自动机描述：通过某种自动机描述一个串是否在语言中。
琐事
短语 formal language 也在非研究领域被用于“正式用语”。 这里 formal 一词指符合某种既定形式（form）的，因此可以指“正式的”（符合传统或礼节的）和“形式的”（与“内容的”相对，关于形式本身的并抽象掉具体内容的）。
当我们描述一种语言时，需要使用一种语言来描述，也就是“用语言 A 描述语言 B”。一般称语言 B 为“被描述语言”，也就是实际研究对象；而称语言 A 为“元语言”。 形式化定义、形式化描述中的形式化指的是元语言的形式化，或者说，“用形式化定义描述”本身是指“用形式化的语言描述一门语言”，不要求被描述语言有形式化特征。而形式语言是指被描述语言是形式化的，“描述一门形式语言”指“用语言描述一门形式化的语言”。因此描述形式语言时，不要求元语言是形式化的。只是为了严谨起见，多数情况下使用形式化的描述方法，而不是简单形容规则。