字符串的字母表 是在一个特定字符串中出现的所有字母的列表。如果 s 是字符串，则它的字母表 指示为
Alph
(
s
)
{\displaystyle \operatorname {Alph} (s)}
这可以等价地认为是先把字符串中的所有字母按照给定的顺序排好，再去掉其中重复者。
字符串同态 是使得每个字母被替代为一个单一字符串的字符串代换。就是说，
f
(
a
)
=
s
{\displaystyle f(a)=s}
s 是字符串，对于每个字母 a 。字符串同态是保持字符串连接 二元运算 的同态 。给定一个语言 L ，
f
(
L
)
{\displaystyle f(L)}
L 的同态像 。字符串 s 的逆同态像 被定义为
f
−
1
(
s
)
=
{
w
|
f
(
w
)
=
s
}
{\displaystyle f^{-1}(s)=\{w\vert f(w)=s\}}
而语言 L 的逆同态像被定义为
f
−
1
(
L
)
=
{
s
|
f
(
s
)
∈
L
}
{\displaystyle f^{-1}(L)=\{s\vert f(s)\in L\}}
注意一般的说
f
(
f
−
1
(
L
)
)
≠
L
{\displaystyle f(f^{-1}(L))\neq L}
f
(
f
−
1
(
L
)
)
⊆
L
{\displaystyle f(f^{-1}(L))\subseteq L}
和
L
⊆
f
−
1
(
f
(
L
)
)
{\displaystyle L\subseteq f^{-1}(f(L))}
对于任何语言 L 。简单单一字母置换密码 是字符串代换的例子。
字符串 s 与字母 a 的右商 是在字符串 s 中切断右手端字母 a 得到的字符串。它被指示为
s
/
a
{\displaystyle s/a}
a ，则结果是空串。就是:
(
s
a
)
/
b
=
{
s
if
a
=
b
ε
if
a
≠
b
{\displaystyle (sa)/b={\begin{cases}s&{\mbox{if }}a=b\\\varepsilon &{\mbox{if }}a\neq b\end{cases}}}
空串的右商可以是:
ε
/
a
=
ε
{\displaystyle \varepsilon /a=\varepsilon }
类似的，给出幺半群
M
{\displaystyle M}
S
⊂
M
{\displaystyle S\subset M}
S
/
a
=
{
s
∈
M
|
s
a
∈
S
}
{\displaystyle S/a=\{s\in M\vert sa\in S\}}
左商可以类似的定义，运算发生在字符串的左端。
幺半群
M
{\displaystyle M}
S
⊂
M
{\displaystyle S\subset M}
等价关系 ，叫做 S 的右语法关系 。它给出为
∼
S
=
{
(
s
,
t
)
∈
M
×
M
|
S
/
s
=
S
/
t
}
{\displaystyle \sim _{S}\;\,=\,\{(s,t)\in M\times M\vert S/s=S/t\}}
关系明显是有有限索引的(有有限数目个等价类)，当且仅当右商族有限的；就是说如果
{
S
/
m
|
m
∈
M
}
{\displaystyle \{S/m\vert m\in M\}}
是有限的。在这种情况下，S 是可识别语言 ，就是说可被有限状态自动机 识别的语言。这个在语法幺半群 中详细讨论。
字符串 s 与字母 a 的右取消 是切除字符串 s 右手端的字母 a 的首次出现得到的字符串。它被指示为
s
÷
a
{\displaystyle s\div a}
(
s
a
)
÷
b
=
{
s
if
a
=
b
(
s
÷
b
)
a
if
a
≠
b
{\displaystyle (sa)\div b={\begin{cases}s&{\mbox{if }}a=b\\(s\div b)a&{\mbox{if }}a\neq b\end{cases}}}
空串总是可取消的:
ε
÷
a
=
ε
{\displaystyle \varepsilon \div a=\varepsilon }
明显的，右取消和投影可交换 :
π
Σ
(
s
)
÷
a
=
π
Σ
(
s
÷
a
)
{\displaystyle \pi _{\Sigma }(s)\div a=\pi _{\Sigma }(s\div a)}
字符串的前缀 是关于给定语言一个字符串的所有前缀 的集合:
Pref
L
(
s
)
=
{
t
|
s
=
t
u
for
u
∈
L
}
{\displaystyle \operatorname {Pref} _{L}(s)=\{t\vert s=tu{\mbox{ for }}u\in L\}}
语言的前缀闭包 是
Pref
(
L
)
=
⋃
s
∈
L
Pref
L
(
s
)
{\displaystyle \operatorname {Pref} (L)=\bigcup _{s\in L}\operatorname {Pref} _{L}(s)}
一个语言叫做前缀闭合 的，如果
Pref
(
L
)
=
L
{\displaystyle \operatorname {Pref} (L)=L}
幂等 的:
Pref
(
Pref
(
L
)
)
=
Pref
(
L
)
{\displaystyle \operatorname {Pref} (\operatorname {Pref} (L))=\operatorname {Pref} (L)}
前缀关系 是二元关系
⊑
{\displaystyle \sqsubseteq }
s
⊑
t
{\displaystyle s\sqsubseteq t}
s
∈
Pref
L
(
t
)
{\displaystyle s\in \operatorname {Pref} _{L}(t)}
前缀文法 生成(关于这个文法)前缀闭合的语言。
John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation , Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X . (See chapter 3.) 
