字

字是把字母表中的原子按有限顺序排成的一条序列。把它形式化为位置到符号的函数，可以精确谈长度、切片和连接，而不依赖某种具体字符串存储。顺序与重数都重要：01、10 和 001 是三个不同的字。空字虽然没有符号，却是连接运算的单位元，因此不能把它当作“什么都没有而无需纳入集合”。

在 $\mathrm{\Sigma }=\{a,b\}$ 上，$w=abba$ 的长度为 $4$，ab 是前缀，ba 是后缀，第二至第三位置形成子串 bb。空字满足 $|\epsilon |=0$，并属于每个 ${\mathrm{\Sigma }}^{\ast }$。

边界是空字与空语言的区别：$\epsilon$ 是一个字，而 $\varnothing$ 是不含任何字的语言；$\{\epsilon \}$ 则是恰含一个长度零字的语言。无限符号序列不属于 ${\mathrm{\Sigma }}^{\ast }$，需要 ω-word 等不同模型。

$\epsilon$ 通常不属于字母表 $\mathrm{\Sigma }$，除非有人刻意把一个同名印刷符号作为普通元素加入；作为空序列的 $\epsilon$ 长度仍为零。字也不能定义成字母表的有限子集，因为集合表示会丢失顺序与重复次数。

字是形式语言公理库形式语言Formal language · Language over an alphabet固定字母表上有限字的任意集合，是识别器、文法与判定问题共同描述的对象。的元素，也是有限状态自动机公理库有限状态自动机Finite-state automaton · Finite automaton · Finite-state machine用有限个控制状态概括已读前缀，并沿带输入标号的转移识别有限字的模型家族。与图灵机读取的有限输入。字符串连接公理库字符串连接String concatenation把第二个字的符号接在第一个字之后形成的新字及相应结合运算。把字组成自由幺半群，长度给出与连接相容的自然数分级。

前缀、后缀和子串结构支撑字符串匹配、词法分析、编码理论与 Myhill–Nerode 区分后缀的定义。形式语言里的 word 是字母序列；Word-RAM 的 machine word 则是固定 $w$-bit 运算单元，两者不能因英文同名而混用。

压缩索引进一步把字符串视作 bit 串与可导航序列：rank/select公理库Rank 与 Select 查询Rank and select在位串上计算前缀频数或定位第 j 次出现，并固定端点和索引约定。在位位置上计数与定位，简洁位向量公理库简洁位向量succinct bit vector · rank-select bit vector以 n+o(n) 位表示静态位串，并在 Word-RAM 上常数时间支持 rank 与 select。按 bit 报空间，FM-index公理库FM-indexFM-index · Full-text minute-space index · 压缩全文索引在压缩 BWT 上提供 rank 支持，以反向搜索完成模式计数，并通过采样后缀数组和逆后缀数组实现定位与文本提取。从 BWT 表示支持模式搜索。这些页面都保留字符边界、字母表编码和机器字打包三个层次。

同一个字在亚线性模型中还会被分配不同的可见性。Indexing公理库Indexing 通信问题Indexing communication problem · INDEX problemAlice 持有 n-bit 串、Bob 持有索引并要恢复对应 bit 的单向通信问题，是流式与摘要空间下界的标准母问题。让 Alice 看见整个 bit 字而 Bob 只持索引，输出虽只有一位，通信仍可能线性；位查询模型公理库查询复杂度模型Query complexity model · Bit-query model将输入隐藏在坐标 oracle 后，只统计算法为确定函数值而读取的输入位置数量。则让单个算法按位置读取隐藏字，并把读取次数作为成本。性质距离公理库到性质的距离Distance to property · Distance from a property取对象到性质中最近合法对象的归一化距离，并据此精确定义 close、far 与测试 promise。常把两个等长字的 Hamming 差异除以长度，但测试器还需声明可查询坐标和 far 阈值。字的集合论定义没有改变，改变的是谁看见哪些符号以及访问一次如何计费。