學(xué)習(xí)編譯原理Time04 ~ 字母表和串及運(yùn)算

學(xué)習(xí)文法之前，先了解基本概念，即字母表和串

字母表∑是一個(gè)有窮符號(hào)集合，比如符號(hào)有字母、數(shù)字、標(biāo)點(diǎn)符號(hào)......

例：

    二進(jìn)制字母表：{1，0}

    ASCII字符集

    Unicode字符集

字母表上的運(yùn)算

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

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

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

字母表∑的n次冪(power)

∑o={ ε }    ε表示為空字符串

∑ⁿ=∑^n-1∑ , n≥1

字母表的n次冪：長(zhǎng)度為n的符號(hào)串構(gòu)成的集合

例： {0,1}3={0,1} {0,1} {0,1}

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

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

∑⁺ = ∑ U ∑2 U ∑3 U ...

什么是正閉包？

字母表的正閉包是長(zhǎng)度為正數(shù)的字符串構(gòu)成的集合。

例：{a, b, c, d}⁺={a, b, c, d,

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

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

意思是說(shuō)長(zhǎng)度為1的字符串集合并上長(zhǎng)度為2的字符串集合，再并上長(zhǎng)度為3的字符串集合，以此類(lèi)推。

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

∑* =∑o U∑⁺ = ∑o U ∑ U ∑2 U ∑3 U ...

什么是克林閉包？

字母表的克林閉包是任意字符串（長(zhǎng)度可以為0）構(gòu)成的集合。

例：{a, b, c, d}^*={ε, a, b, c, d,

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

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

串(string)

設(shè)∑是一個(gè)字母表，?x∈∑*，x稱為是∑上的一個(gè)串

意思是說(shuō)，克林閉包里面的每一個(gè)元素，都成為字母表里面的一個(gè)串，串是字母表中符號(hào)的一個(gè)有窮序列。

 

串s的長(zhǎng)度，通常記作|s|，是指s中符號(hào)的個(gè)數(shù)

例：|aab|=3

空串是長(zhǎng)度為0的串，用ε（epsilon）表示

例：|ε|=0

串上的運(yùn)算——連接

如果x和y是串，那么x和y的連接（concatenation）是把y附加到x后面而形成的串，記作xy。

例：如果x=hello，y=world

那么xy=helloword

空串是連接運(yùn)算的單位元（identity），即對(duì)于任何串都有，εs=sε=s

設(shè)x，y，z是三個(gè)字符串，如果x=yz，則稱y是x的前綴，z是x的后綴

串上的運(yùn)算——冪

串s的冪運(yùn)算

so=ε

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

例：s1=sos=εs=s，s2=ss，s3=sss，...

示例：如果s=ba，那么s1=ba，s2=baba，s3=bababa，...

記錄

點(diǎn)點(diǎn)滴滴的筆記

歡迎關(guān)注，共同學(xué)習(xí)

小浩筆記