形式语言

数学、逻辑和计算机科学中，形式语言（英语：Formal language）是用精确的数学或机器可处理的公式定义的语言。如语言学中语言一样，形式语言一般有两个方面: 语法和语义。

专门研究语言的语法的数学和计算机科学分支叫做形式语言理论，它只研究语言的语法而不致力于它的语义。在形式语言理论中，形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。按一定规律构成的句子或符号串的有限或无限的集合。

在逻辑学、数学、计算机科学和语言学中，形式语言由单词组成，这些单词的字母来自于一个字母表，并且根据一套特定的规则被很好地构成。

形式语言的字母表由符号、字母或代币组成，这些符号可以串联成语言的字符串。每个由这个字母表的符号串联起来的字符串被称为一个词，而属于某个特定形式语言的词有时被称为形式良好的词或形式良好的公式。

形式语言通常是通过形式语法来定义的，如正则语法或无语境语法，它由其形成规则组成。在计算机科学中，形式语言被用来作为定义编程语言的语法和自然语言子集的形式化版本的基础，其中语言的词代表与特定含义或语义相关的概念。

在计算复杂性理论中，决策问题通常被定义为形式化语言，而复杂性类别被定义为可以被计算能力有限的机器解析的形式化语言的集合。

在逻辑学和数学基础中，形式语言被用来表示公理系统的语法，而数学形式主义是一种哲学，认为所有的数学都可以通过这种方式简化为形式语言的语法操作。

形式语言理论领域主要研究这种语言的纯句法方面--即其内部结构模式。形式语言理论产生于语言学，是理解自然语言的句法规律的一种方式。历史在17世纪，戈特弗里德-莱布尼茨想象并描述了characteristicauniversalis，一种利用象形文字的普遍和形式语言。在这一时期，卡尔-弗里德里希-高斯也研究了高斯码的问题。

戈特洛布-弗雷格试图通过一个符号系统来实现莱布尼茨的想法，该系统首先在《初学者》（Begriffsschrift，1879年）中概述，并在其两卷本的《算术基础》（GrundgesetzederArithmetik，1893/1903）中得到更充分的发展。

这描述了一种纯语言的形式语言。在20世纪上半叶，有几个与形式语言相关的发展。阿克塞尔-图伊在1906年至1914年间发表了四篇与词和语言有关的论文。

其中最后一篇介绍了EmilPost后来称之为"Thue系统"，并给出了一个早期的不可解决的问题的例子。波斯特后来用这篇论文作为1947年证明"半群的词问题是递归无解的"的基础，后来还设计了创建形式语言的典型系统。

诺姆-乔姆斯基设计了一个形式语言和自然语言的抽象表示法，被称为乔姆斯基层次结构。1959年，JohnBackus开发了Backus-Naur形式来描述高级编程语言的语法，这是他在创建FORTRAN时的工作。PeterNaur在1960年发明了一个类似的方案。

字母表，在形式语言的背景下，可以是任何集合，尽管使用通常意义上的字母表通常是有意义的，或者更普遍的是任何有限的字符编码，如ASCII或Unicode。一个字母表的元素被称为字母。

一个字母表可以包含无限多的元素；然而，形式语言理论中的大多数定义指定了具有有限数量元素的字母表，并且大多数结果只适用于它们。字母表上的一个词可以是任何字母的有限序列（即字符串）。

一个字母表Σ上的所有词的集合通常用Σ*来表示（使用Kleene星）。一个词的长度是指它由多少个字母组成。对于任何字母表，只有一个长度为0的词，即空词，通常用e、ε、λ甚至Λ来表示。

通过连接，人们可以将两个词合并成一个新的词，其长度为原词的长度之和。将一个词与空词连接的结果就是原来的词。

在某些应用中，特别是在逻辑学中，字母表也被称为词汇表，而词则被称为公式或句子；这就打破了字母/词的隐喻，取而代之的是词/句子隐喻。

一个字母表Σ上的形式语言L是Σ*的一个子集，也就是该字母表上的一个词集。有时，词集被分组为表达式，而规则和约束可能被制定为"形式良好的表达式"的创建。在通常不涉及自然语言的计算机科学和数学中，形容词正式通常被省略，因为它是多余的。