计算理论-形式语言

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

计算机形式语言的历史

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