学习编译原理Time04 ~ 字母表和串及运算
共 1447字,需浏览 3分钟
·
2021-04-17 23:07
字母表∑是一个有穷符号集合,比如符号有字母、数字、标点符号......
例:
二进制字母表:{1,0}
ASCII字符集
Unicode字符集
字母表上的运算
字母表∑1和∑2的乘积(product)
∑1∑2={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,...
小浩笔记