学习编译原理Time04 ~ 字母表和串及运算

小浩笔记

共 1447字,需浏览 3分钟

 ·

2021-04-17 23:07

学习文法之前,先了解基本概念,即字母表和串



字母表∑是一个有穷符号集合,比如符号有字母、数字、标点符号......

例:

    二进制字母表:{1,0}

    ASCII字符集

    Unicode字符集


字母表上的运算

字母表1和∑2乘积(product)

12={ab|a ∈ 1, b∈ ∑2}

例:{0, 1}{a, b}={0a, 0b, 1a, 1b}


字母表∑的n次幂(power)

∑º={ ε }    ε表示为空字符串

n=n-1∑ , n≥1

字母表的n次幂:长度为n的符号串构成的集合

例: {0,1}³={0,1} {0,1} {0,1}

={000, 001, 010, 011, 100, 101, 110, 111}


字母表∑的正闭包(positive closure)

+ = ∑ U ∑² U ∑³ U ...

什么是正闭包?

字母表的正闭包是长度为正数的字符串构成的集合。


例:{a, b, c, d}+={a, b, c, d,

aa, ab, ac, ad, ba,bb,bc,bd,...,

aaa,aab,aac,aad,aba,abb,abc,...}

意思是说长度为1的字符串集合并上长度为2的字符串集合,再并上长度为3的字符串集合,以此类推。


字母表∑的克林闭包(positive closure)

∑* =∑º U∑+ = ∑º U ∑ U ∑² U ∑³ U ...

什么是克林闭包?

字母表的克林闭包是任意字符串(长度可以为0)构成的集合。


例:{a, b, c, d}*={ε, a, b, c, d,

aa, ab, ac, ad, ba,bb,bc,bd,...,

aaa,aab,aac,aad,aba,abb,abc,...}



串(string)

是一个字母表,∀x∈*,x称为是上的一个串

意思是说,克林闭包里面的每一个元素,都成为字母表里面的一个串,串是字母表中符号的一个有穷序列。

 

串s的长度,通常记作|s|,是指s中符号的个数

例:|aab|=3

空串是长度为0的串,用ε(epsilon)表示

例:|ε|=0


串上的运算——连接

如果x和y是串,那么x和y的连接(concatenation)是把y附加到x后面而形成的串,记作xy。

例:如果x=hello,y=world

那么xy=helloword

空串是连接运算的单位元(identity),即对于任何串都有,εs=sε=s

设x,y,z是三个字符串,如果x=yz,则称y是x的前缀,z是x的后缀


串上的运算——

串s的幂运算

sº=ε

sn=sn-1s,n≥1

例:s¹=sºs=εs=s,s²=ss,s³=sss,...

示例:如果s=ba,那么s¹=ba,s²=baba,s³=bababa,...





记录
点点滴滴的笔记
欢迎关注,共同学习


小浩笔记


浏览 70
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报