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