形式语言

数学、逻辑和计算机科学中，形式语言（英语：Formal language）是用精确的数学或机器可处理的公式定义的语言。

详细内容

形式语言的字母是从该语言的字符串可以形成的一组符号，字母，或标记，;通常它的要求是有限的。

字符串由这个称为字的字母形成，这些词属于一个特定的形式语言有时被称为形式公式。一个正式的语言，往往是通过一个正式的语法，如正则文法或上下文无关文法定义，称作形成规律。

形式语言理论主要研究的是内部结构模式这类语言的纯粹的语法领域。形式语言理论是从语言学衍生而来，作为一种理解自然语言的句法规律。在计算机科学中，形式语言通常作为定义编程语言和语法的基础，是正式版本的自然语言的子集。在计算复杂性理论中，决策问题通常定义为形式语言，复杂类被定义为形式语言的集合，它能被具有有限计算能力的机器所解析。在逻辑和数学基础中，形式语言是用来表示公理系统的语法。

自然语言和形式语言

自然语言（Natural Language）就是人类讲的语言，比如汉语、英语和法语。这类语言不是人为设计（虽然有人试图强加一些规则）而是自然进化的。形式语言（Formal Language）是为了特定应用而人为设计的语言。例如数学家用的数字和运算符号、化学家用的分子式等。编程语言也是一种形式语言，是专门设计用来表达计算过程的形式语言。

形式语言有严格的语法（Syntax）规则，例如，3+3=6是一个语法正确的数学等式，而3=+6$则不是，H2O是一个正确的分子式，而2Zz则不是。语法规则是由关于符号（Token）和结构（Structure）的规则所组成的。Token的概念相当于自然语言中的单词和标点、数学式中的数和运算符、化学分子式中的元素名和数字。关于Token的规则称为词法（Lexical）规则，而关于语句结构的规则称为语法（Grammar）规则。

语言间的运算

语言间的运算就是Σ*幂集上的运算。

字符串集合的交并补等运算。

连接运算：L1L2={xy|x属于L1并且y属于L2}。

幂运算：Ln=L…L（共n个L连接在一起），L0={ε}。

闭包运算：L*=L0∪L1∪…∪Ln∪…。

右商运算：L1/L2={x|存在y属于L2使得xy属于L1}。

设S⊆Σ*是一个语言，S的补语言定义为集合{ω|ω∈Σ*且ω∉S}

语言的表示方法

一个形式语言可以通过多种方法来限定自身，比如：

枚举出各个字串（只适用于有限字串集合）。

通过形式文法来产生（参见乔姆斯基谱系）。

通过正则表达式来产生。

通过某种自动机来识别，比如图灵机、有限状态自动机。

应用

编程语言

主要文章：语法（编程语言和编译器）

编译器通常有两个不同的部分组成。一个词法分析器，由一个像lex的工具形成。那识别编程语言的语法标记。例如：标识符或关键字，在一个简单的语言表达形式中，通常是正则表达式工具。在最基本的概念，一个解析器由一个类似yacc的解析生成器构成。试图判断源程序是否有效。当然，编译器做的不仅仅是解析源代码，他们通常把它翻译成一些可执行格式。因此，一个解析器通常输出多是或否的回答，一个典型的抽象语法树，这是由编译器后续阶段用于最终生成机器代码，包含直接运行在硬件执行，或一些中间代码需要虚拟机执行。

形式语言学

也称代数语言学,它研究一般的抽象符号系统,运用形式模型对语言(包括人工语言和自然语言)进行理论上的分析和描写.

形式文法:是一种格式,用来说明什么句子在该语言中是合法的,并指明把词组合成短语和句子的规则.

描述语言有三种途径:1,穷举2,文法 3,自动机其中文法是指的产生过程,而自动机是指的识别过程.一种语言,如果存在对它的识别过程,就一定存在对它的产生过程,反之亦然.

现行的形式语法系统是Chomsky于1959年为了描述自然语言而提出的一种理论模型

如何严格的定义形式化的语言

形式文法:一个形式文法G由四个部分组成,可记作G={VN, VT, S , P },其中:

VN:称为文法G的非终结符号字母表,VN不出现在G所表示的语言集合的句子中;

VT:称为文法G的终结符号字母表,G所表示的语言的句子由VT中的元素组成,VN ∩VT = ;S :代表句子符号,S∈VN .

P :代表一组式子组成的集合,P 中的式子具有如下形式:α->β

产生式需要满足下面的条件:1)α可以是VN 和VT 上的任意字符串,但其中必须至少包含一个非终结符,并且不能是空字符;2)β可以是VN 和VT 上的任意字符串,也可以是空字符;3)P 中至少有一个产生式中的α得由S 来充当;

形式语言的特点

1,高度的抽象化(采用形式化的手段-专用符号,数学公式-来描述语言的结构关系,这种结构关系是抽象的)2,是一套演绎系统(形式语言本身的目的就是要用有限的规则来推导语言中无限的句子,提出形式语言的哲学基础也是想用演绎的方法来研究自然语言)3,具有算法的特点.(比如说句法分析中采用不同的算法来构造句子的句法推导树)

乔姆斯基把文法分成4种类型，即0型，1型，2型，和3型。0型文法也称短语文法，0型文法的能力相当于图灵机（Turing），或者说任何0型语言都是递归可枚举的。1型文法也称上下文有关法，其能力相当于线性界限自动机。2型文法也称上下文无关法，其能力相当于非确定的下推自动机。3型文法也称右线性文法，由于这种文法等价于正规式，所以也称正规文法。从文法描述语言的能力来说，0型文法最强，3型文法最弱。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省