基本概念
哈尔滨工业大学 陈鄞
第二章 语言及其文法
➢字母表∑是一个有穷符号集合
➢符号：字母、数字、标点符号、…
字母表 (Alphabet)
例：
➢二进制字母表：{ 0,1 }
➢ASCII字符集
➢Unicode字符集
➢∑
1
∑
2
={ab|a ∈ ∑
1
, b ∈ ∑
2
}
字母表上的运算
例： {0, 1} {a, b} ={0a, 0b, 1a, 1b}
➢字母表∑
1
和∑
2
的乘积( product)
∑
0
={ ε }
∑
n
=∑
n-1
∑ , n ≥ 1
例： {0, 1}
3
={0, 1} {0, 1} {0, 1}
={000, 001, 010, 011, 100, 101, 110, 111}
字母表的n次幂：长度为n的符号串构成的集合
字母表上的运算
➢字母表∑
1
和∑
2
的乘积( product)
➢字母表∑的n次幂( power)
➢字母表∑的正闭包( positive closure)
➢∑
+
= ∑ ∪ ∑
2
∪ ∑
3
∪ …
例：{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
的乘积( product)
➢字母表∑的n次幂( power)
字母表的正闭包：长度正数的符号串构成的集合
