查看“︁形式语言”︁的源代码

[[分类:形式语言]]
{{InfoBox
|name=形式语言
|eng_name=formal language
}}
'''形式语言'''('''formal language''')指通过定义语法规则的方式来定义的语言。

通常包括一个'''字母表'''，和一组'''规则'''，按这个规则可以将字母表中的'''字母'''结合成良定义的'''单词'''。
在一些领域中，将这里的字母表称为'''词汇表'''，称按规则将词汇表中的'''单词'''结合成良定义的'''句子'''。

形式化在这里的意思是语言具有某种形式，服从某种规则。与规则本身是否被形式化地描述无关。
换句话说，即使以并不形式化的方式描述语言的规则，也应该称为形式语言。

== 定义 ==

对任意[[集合]] <math>A</math> ，由集合上的所有[[串]]构成集合 <math>A^{*}</math> ，其（遵循某种规则确定的）一个[[子集]] <math>L</math> 称为 <math>A</math> 上的一个'''形式语言'''('''formal language''')。其中，
* 集合 <math>A</math> 称为形式语言的'''字母表'''('''alphabet''')，元素称为'''字母'''('''letter''')，构成的串称为'''单词'''('''word''')，规则称为'''文法'''('''grammar''')；
* 有时，集合 <math>A</math> 称为形式语言的'''词汇表'''('''vocabulary''')，元素称为'''单词'''('''word''')，构成的串称为'''句子'''('''sentence''')或'''公式'''('''formula''')，规则也称为'''文法'''('''grammar''')。
特别地，如果一种形式语言有两级结构，通常较低一级使用“字母-单词”，较高一级使用“单词-句子”，且分别称两个级别的规则为'''词法规则'''/'''词法'''('''lexical rule''')和'''句法规则'''/'''句法'''('''syntactic rule'''/'''syntax''')，并合称'''语法'''('''grammar''')。

注：
# 所有串的集合就是[[字符串]]集的定义，也可以表达成字符串集的某个子集。
# 形式语言是相对于非形式化语言来说的，在不需要区分的领域中，也常简称为'''语言'''('''language''')。
# 这里的规则本身仅要求能用于界定一个串是否属于这个语言，不要求其具有某种规则的形式。
# 特别地，空集 <math>\varnothing</math> 也是 <math>A^*</math> 的子集，称为'''空语言'''。

== 描述 ==

描述形式语言通常包括两方面：
* 形式语言的字母表；
* 形式语言的构成规则。

规则有以下几种常见的表达方式：
* 集合描述：按集合列举的方式描述集合内的元素。
* 规则描述：通过形式文法、正则表达式等描述规则。
* 自动机描述：通过某种自动机描述一个串是否在语言中。

== 琐事 ==

短语 formal language 也在非研究领域被用于“正式用语”。
这里 formal 一词指符合某种既定形式（form）的，因此可以指“正式的”（符合传统或礼节的）和“形式的”（与“内容的”相对，关于形式本身的并抽象掉具体内容的）。

当我们描述一种语言时，需要使用一种语言来描述，也就是“用语言 A 描述语言 B”。一般称语言 B 为“被描述语言”，也就是实际研究对象；而称语言 A 为“[[元语言]]”。
形式化定义、形式化描述中的形式化指的是元语言的形式化，或者说，“用形式化定义描述”本身是指“用形式化的语言描述一门语言”，不要求被描述语言有形式化特征。而形式语言是指被描述语言是形式化的，“描述一门形式语言”指“用语言描述一门形式化的语言”。因此描述形式语言时，不要求元语言是形式化的。只是为了严谨起见，多数情况下使用形式化的描述方法，而不是简单形容规则。