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

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

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

例：

    二进制字母表：{1，0}

    ASCII字符集

    Unicode字符集

字母表上的运算

字母表∑₁和∑₂的乘积(product)

∑₁∑₂={ab|a ∈ ∑₁, b∈ ∑₂}

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

字母表∑的n次幂(power)

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

∑ⁿ=∑^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º=ε

sⁿ=s^n-1s，n≥1

例：s¹=sºs=εs=s，s²=ss，s³=sss，...

示例：如果s=ba，那么s¹=ba，s²=baba，s³=bababa，...

记录

点点滴滴的笔记

欢迎关注，共同学习

小浩笔记