计算理论-形式语言

计算机的各种程序设计语言、数理逻辑中的谓词演算语言等都属于形式语言。

计算机形式语言的历史

形式语言是由一组有限的符号和一组规则（通常称为文法）组成的严格数学系统，这些规则定义了如何将这些符号组合成有效的语句。形式语言的研究始于20世纪初，而将形式语言用于模拟自然语言是在20世纪50年代中期。形式语言理论在计算机科学中扮演着重要的角色，尤其是在编译器设计、编程语言的设计、自然语言处理以及数据库查询语言等领域

文法

形式语言的定义通常包括以下几个部分：

字母表（Σ）：这是形成语言的一组基本符号。字（Word）：由字母表中的符号组成的字符串，包括空字符串。语言（Language）：字母表的所有可能字符串的集合中的一部分，这部分由语言的文法规则定义。形式语言理论中的文法被严格地定义为四元组G=(V, T, P, S)，其中：

V和T分别是变元（非终结符）和终结符（终结符）的有穷集合，且V和T没有公共元素。
S是一个特殊的变元，称为开始符号或起始符号。
P是生成式的有穷集合，生成式的基本形式是：A→β，其中A和β都是由变元和终结符组成的符号串，但A至少含有一个非终结符。形式语言可以根据生成规则和特性进行分类，常见的分类包括：

正则语言（Regular Language）：由正则文法生成的语言，可以被有限状态自动机识别。上下文无关语言（Context-Free Language）：由上下文无关文法生成的语言，可以被下推自动机识别。上下文有关语言（Context-Sensitive Language）：由上下文有关文法生成的语言，可以被线性有界自动机识别。无限制文法（Unrestricted Grammar）：没有对生成规则做限制的文法，可以生成所有可被图灵机识别的语言。

G=(V, T, P, S)，其中V是变元（非终结符）的集合，T是终结符（终结符）的集合，P是产生式（规则）的集合，S是起始符号

形式语言的基本概念

G=(V, T, P, S)

字母表

形式语言必须规定所用基本符号集合，即字母表
通常用V或Σ表示,例如V={x, y, z}
显而易见，构造句子不可能用集合之外的元素来构造(当然你可以写空串)

符号串

定义

符号串由字母表中的符号组成的序列
例如abc就是上述字母表V上的一个符号串，它的长度为3，例如ɑ=abc，那么用|ɑ|=3表示该符号串的长度。空符号串，口语表述经常为空串：不含任何符号的字符串通常用ɛ表示，显然|ɛ|=0。

“连接"运算"∘”

当然，这只是一种连接表达，你用别的符号表达也行，这里先这么写。表达式简单易懂，例如x=bca,y=cab,那么z=x∘y=bca∘cab=bcacab，是不是很简单？

性质

幺元

ɛ∘x=x∘ɛ=x

这个是离散数学学的，不过神奇的是，这学期离散数学，计算理论，数据结构一起上，倒是把原来承前启后的学习路径变成交错纵横了

可结合性

(x∘y)∘z=x(y∘z)

幂形式

符号串连接可以写成幂形式例如
x∘x∘x=x³

乘法运算

满足一般的运算律
AB={x∘y|x∈A^y∈B}
A={a,b},b={0,1}
AB={a0,a1,b0,b1}
也可以写成乘幂的形式
A^mAⁿ=A^m+n

闭包v⁺与v^*

v⁰-由空符号串的集合。v⁰={ɛ}。
v-由v中长度为1的符号串的集合。
v²-由v中长度为2的符号串的集合。
v⁺=v∪v²∪v³∪…
v^*=ɛ∪v∪v²∪v³∪…

语言

定义

设V是个字母表，L属于V^*
v={0,1}
L1 = ∅
L2 = {0,00,000,……}
L3 = {1,11,111,1111,……}
上述L1,L2,L3都是V上的语言

句子

定义

语言中的元素就是句子
v={0,1}
L2={0,00,000,……}
例如，00就是L2中的一个句子

文法

定义

G=(V_n, V_t, P, S)

• V_n是非终极符（变元）的集合，一般用大写字母表示

• V_t是终极符的集合(V_N ∩ V_T = ∅, V_T ∪ V_N = V)

• P是产生式的集合.

  • P中的产生式的形式为A→α，其中A是非终极符，α是终极符或非终极符的串。

• S是开始变元(s ∈ V_N)

约定

• 用大写英文字母表示变元

  • S通常表示开始变元

• 用小写a,b,c,…表示终极符

• 用x,y,z,…表示终极符串

• 用希腊字母表示既含有终极符又含有非终极符的符号串

句型

• 句型是由终极符串和非终极符串组成的符号串

推导

• 推导是从开始符号开始，按照产生式进行推导，直到产生终极符串为止。

• 推导的结果是句子。

文法产生的语言

• 文法G产生的语言是由G中所有句型推导出的语言。令集合L(G)={w|w是G中所有句型的推导出的句子}
  其中每个w∈L(G)都是一个句子。

文法分类

0，1，2，3型文法

• 0型文法：G中所有产生式的右部都是终极符串。

• 1型文法：G中所有产生式的右部都是非终极符串。

• 2型文法：G中所有产生式的右部都是终极符串或非终极符串。

• 3型文法：G中所有产生式的右部都是终极符串或非终极符串，且右部的非终极符串均不相同。也可以这么说

• 短语结构文法

• 上下文有关文法(CSG)

• 上下文唔该文法(CFG)

• 正规文法|右线行文法，左线性文法

识别这些语言的自动机分别是
0型语言-图灵机
1型语言-线性界限自动机
2型语言-下推自动机
3型语言-有限自动机

参考

《计算理论ppt》