基本概念
# 基本概念
课件
# 字母表
- 字母表
是一个有穷符号集合 - 符号:字母、数字、标点符号
表示空字母表 - 例: 二进制字母表:{ 0,1 }, ASCII字符集, Unicode字符集
# 字母表上的运算
# 字母表乘积运算
例:
# 字母表的幂运算
例:
字母表的
# 字母表的正闭包(positive closure)
- 长度为正数的符号串构成的集合
# 字母表的克林闭包(Kleene closure)
- 任意符号串(长度可以为零)构成的集合
# 串(符号串)
- 设
是一个字母表, , 称为是 上的一个串 - 串是字母表符号中的一个有穷序列
- 串
的长度,记作 , 是指 中符号的个数 - 例
- 例
- 空串是长度为 0 的字符串, 用
表示 - 符号串即是串
# 串上的运算
# 串的连接
如果
和 是串,那么 和 的连接(concatenation)是把 附加到 后面而形成的串,记作 - 例:
- 例:
空串是连接运算的单位元 ( identity) ,即,对于任何串
都有, 设
是三个字符串,如果 ,则称 是 的前缀, 是 的后缀
# 串的幂运算
定义
串
的 次幂:将 个 连接起来
编辑 (opens new window)