计算理论-形式语言

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

计算机形式语言的历史

形式语言是由一组有限的符号和一组规则（通常称为文法）组成的严格数学系统，这些规则定义了如何将这些符号组合成有效的语句。形式语言的研究始于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=x3

乘法运算

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

闭包v+与v*

v0-由空符号串的集合。v0={ɛ}。 v-由v中长度为1的符号串的集合。 v2-由v中长度为2的符号串的集合。 v+=v∪v2∪v3∪… v*=ɛ∪v∪v2∪v3∪…

语言

定义

设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=(Vn, Vt, P, S)

• Vn是非终极符（变元）的集合，一般用大写字母表示
• Vt是终极符的集合(VN ∩ VT = ∅, VT ∪ VN = V)
• P是产生式的集合.
  • P中的产生式的形式为A→α，其中A是非终极符，α是终极符或非终极符的串。
• S是开始变元(s ∈ VN)

约定

• 用大写英文字母表示变元
  • 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》