符号和符号串

• 字母表（\Sigma）：符号的非空有穷集合

• 符号串：由\Sigma上的符号组成的有穷序列（包括空符号串\epsilon）

  符号串相关概念

  • 头（前缀）

  • 尾（后缀）

  • 子串

  • 固有头（真前缀）

  • 固有尾（真后缀）

  符号串去掉固有头（或固有尾）后不能为空符号串，即除符号串s本身外，其余头（或尾）均为s的固有头（或固有尾）

  以符号串s=abc为例：

  头：\epsilon，a，ab，abc	尾：\epsilon，c，bc，abc
  固有头：\epsilon，a，ab	固有尾：\epsilon，c，bc