字母表, 字符串, 语言
字母表的定义(Alphabet)
任意非空有限集合\Sigma称为字母表, 其中的元素称为符号
字母表上的字符串的定义(String)
已知字母表\Sigma, 字符串为w=(c_1,c_2,\cdots,c_n), c_i\in\Sigma
字符串的符号数称为字符串的长度, 记为|w|,
将长度为0的字符串称为空串, 记为\epsilon=()
将字母表上长度为n的字符串的集合记为\Sigma^n,n\in\mathbb{N}
将字母表上所有字符串的集合记为全字符串集\Sigma^*=\bigcup_{n=0}^{\infty}\Sigma^n
字符串连接的定义(Concatenation)
字符串连接记为 x\cdot y=(x_1,\cdots,x_n,y_1,\cdots,y_m)
字符串的连接满足结合律, 且空串\epsilon为单位元, 故[\Sigma^*,\cdot]是幺半群
子串的定义(SubString)
若存在字符串x,y, 使得w=xvy, 则称v为w的子串
如果\exists s\in\Sigma^*, w=vs, 则称v为w的前缀(Prefix)
如果\exists s\in\Sigma^*, w=sv, 则称v为w的后缀(Suffix)
字符串反转的定义(Reverse)
字符串反转记为 w^R=(c_n,c_{n-1},\cdots,c_1)
多字符串连接的反转(xy)^R=y^Rx^R
语言的定义(Language)
语言是全字符串集\Sigma^*的子集L\subseteq\Sigma^*
例如\emptyset,\{\epsilon\},\Sigma^n,\Sigma^*都是\Sigma上的语言
需要注意\emptyset和\{\epsilon\}是两个不同的语言
- 交集为L_1\cap L_2
- 并集为L_1\cup L_2
- 差集为L_1-L_2
- 补集为\bar{L}=\Sigma^*-L
语言连接的定义(Concatenation)
语言连接为L_1\cdot L_2=\{xy|x\in L_1,y\in L_2\}
语言的连接满足结合律, 且L=\{\epsilon\}为单位元, 故[\forall L,\cdot]是幺半群
<语言关于连接运算的生成幺半群>
语言的克林闭包的定义(Kleene Closure)
语言的Kleene闭包为L^*=\bigcup_{n=0}^{\infty}L^n=\{\epsilon\}\cup L\cup L^2\cup\cdots, 特别地 \emptyset^*=\{\epsilon\}
- 运算封闭: \forall w_1,w_2\in L^*,w_1\in L^x, w_2\in L^y, w_1w_2\in L^{x+y}\implies w_1w_2\in L^*
- 结合律: L^*\subseteq\Sigma^*\implies L^*的字符串满足结合律
- 单位元: \epsilon\in L^0\subseteq L^*
语言的正闭包的定义(Positive Closure)
语言的正闭包为L^+=\bigcup_{n=1}^{\infty}L^n=L\cup L^2\cup\cdots
计算性问题(Computation Problem)
从字符串到字符串的映射, 即f:\Sigma^*\to\Sigma^*, 称为计算性问题
判定性问题(Decision Problem)
从字符串到布尔值的映射, 即f:\Sigma^*\to\{0,1\}, 称为判定性问题
或者也可以将该映射记为语言L, 其中上述布尔值映射作为特征函数