《计算理论基础》章节试读

《计算理论基础》的笔记-1.7 ALPHABETS AND LANGUAGES - 1.7 ALPHABETS AND LANGUAGES

内存不是内存，硬盘也不是硬盘；内存是符号序列，硬盘也是符号序列。
人类的处理能力是有限的，我们只能处理有限集合，所以字母表只能是有限集合。
有人说符号是符号，符号序列是符号的序列；神说，傻逼，符号就是符号序列，符号序列也是符号。有人说字母表是符号的集合，语言是符号序列的集合；神说，傻逼，字母表就是语言，语言也是字母表。
人类的处理能力是有限的，我们只能处理有限序列，所以符号序列只能是有限序列。
我们不区分此三者：符号a，序列(a)，外加singleton集合{a}。
这个世界是否存在鬼，我们不知道，但我们很确定存在空序列，我们用e表示空序列；需要提请注意的是：
（1）你虽然看不到，其实每个字母表都隐藏着一个字母e。
（2）空序列不是空集合，这个一定要清醒；包含空序列的集合，当然，也不是空集合。
空序列对于DFA来说是EOF；对于NFA来说是不移动读写头。空集合表示空语言，不接受任何序列。包含空序列的集合表示，该语言只接受空序列。
对于($\sum$)来说，($\sum^*$)包含了所有可能的序列。
序列的长度定义和路径的长度定义是一样的。($\mid e \mid = 0$)。
前面提到内存和硬盘都是序列，实际上是在说，存储是序列；而这里说序列等价于函数，也就是说不存在真正意义上的存储，只有计算。
那么($e$)对应什么函数呢，既然是isomorphism，($e$)是不能漏掉的。有空函数吗？显然有，因为函数就是元组集合。空集合就是空函数，没有任何输入，也没有任何输出：void func(void)。
基于函数的概念我们定义了连接运算，发现这哪里是定义，完全就描述了C语言strcat()函数的实现。我们有下列基本定律：($$we = ew = w$$)($$(wx)y = w(xy)$$)我们也由此定义了子序列：($$w = xvy$$)因为x和y可以是e，所以任何序列都是其自身的子序列。还有后缀：($$w = xv$$)还有前缀：($$w = vy$$)还有，我们认为abab在ababab中出现了两次，而不是一次。
接下来我们定义($w^i$)的概念：($$
w^i =
\begin{cases}
e & {i = 0}\\
w^{i-1}w & {i > 0}
\end{cases}
$$)作者称之为归纳定义法，我更愿意称之为递归定义法，一种用自己定义自己的方法。
练习一下，用递归定义法来定义($w^R$)：($$
w^R =
\begin{cases}
e & {\mid{w}\mid = 0}\\
u^Ra & {w = au}
\end{cases}
$$)