文章目錄

• • 字母表
  • 串

字母表

1.字母表簡介

字母表** Σ（Sigma）**是一個有窮符號集合，譬如：

二進制字母表{0，1}

ASCII字符集	……
Unicode字符集	……

2.字母表的運算

字母表Σ₁和Σ₂的乘積
Σ₁Σ₂={ab|a∈Σ₁，b∈Σ₂}

Eg：{0，1}{a，b}={0a，0b，1a，1b}

字母表Σ的n次冪
①Σ⁰={ε}
②Σⁿ=Σ^n-1Σ

Eg：{0，1}³
={0，1} {0，1} {0，1}

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

所以字母表的n次冪，就是長度為n的符號串構成的集合。

字母表Σ的正閉包——長度為正數的符號串構成的集合
Σ⁺=Σ¹∪Σ²∪Σ³∪Σ⁴∪……

Eg：{a，b，c，d}⁺
={
a，b，c，d，
aa，ab，ac，ad，
ba，bb，bc，bd，
…………
aaa，aab，aac，aad，
aba，abb，abc，abd，
…………
}

字母表Σ的克林閉包——任意符號串（長度可為0）構成的集合
Σ^* = Σ⁰∪Σ⁺ = Σ⁰∪Σ¹∪Σ²∪Σ³∪Σ⁴∪……

Eg：{a，b，c，d}^*
={
ε，a，b，c，d，
aa，ab，ac，ad，
ba，bb，bc，bd，
…………
aaa，aab，aac，aad，
aba，abb，abc，abd，
…………
}

串

串的基本概念：
①設Σ是一個字母表，?x∈Σ^*，x是Σ上的一個串。
②串是字母表中符號的一個有窮序列。
③串的長度，記作|s|，表示s中符號數。（Eg：|aab|=3）
其中空串記作ε，長度|ε|=0。

串的運算

①連接運算：
空串（ε）是連接運算的單位元。
若x，y是串，計算連接就是把y接到x后邊，記作：xy

Eg1： x=dog，y=house =》xy=doghouse Eg2： εs=sε=s（其中，ε為單位元） Eg3： x=yz =》y是x的前綴，z是x的后綴

② 冪運算
s⁰=ε
sⁿ=s^n-1s
s¹=s⁰s=εs=s , s²=ss……

Eg：設s=ab，則s^2^=abab，……

串s的n次冪：將n個s連接起來。

總結

以上是生活随笔為你收集整理的【编译原理】文法的基本概念的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。