在考虑自动机时，它们通常被认为是有限字母表。以下是两种类型的自动机，它们可以处理无限字母表上的单词（为清楚起见，包括定义）。
分别附加在单词开头和结尾的符号 [ 和 ] 是分隔符，不在字母表中。也就是说，自动机处理形式为w = [ v ] 的单词，其中v是字母表的一个元素。
字母表上的k 寄存器自动机A 是一个 5 元组 (Q, q_0, F, t_0, P)，其中：
Q 是一组有限状态；
Q 中的 q_0 是初始（或开始）状态；
F（Q 的子集）是最终（或接受）状态的集合；
t_0 : {0,1,...,k}--> 字母联合 {[,]} 是初始寄存器分配；和，
P 是形式为 (i, q)-->(q', d) 或 q-->(q', i, d) 的有限转换集，其中 i 在 {0,1,...,k }, q, q' 在 Q 和 d 在 {Stay, Left, Right}。
符号有限自动机 (SFA) M 是一个 5 元组 ( A , Q, q_0, F, d)，其中：
- A 是一个有效的布尔代数（字母表）；
- Q 是一组有限状态；
- Q 中的 q_0 是初始（或开始）状态；
- F（Q 的子集）是最终（或接受）状态的集合；和，
- d（Q x Y_A x Q 的子集）是有限的转换集。
研究表明，对于寄存器自动机，等价是不可判定的，但在符号自动机中，等价是可判定的。我的问题是为什么？这两种自动机类型的工作结果相似，那么为什么我们不能将一种归约到另一种呢？
有人告诉我这是一个非常简单的问题，但我似乎无法在任何地方找到答案，所以感谢您的帮助！:)
我目前的想法是，SFA 要求他们的字母表是有效的布尔代数，而 RA 可以处理任何事情，因此他们的字母表不必遵循布尔代数的规则。我不知道如何正确地将这个想法转化为任何有用的东西。