automata-theory - 在自动机理论中，回文长度是什么意思？甚至回文？奇怪的回文？

Question

回文是自动机中的一种语言。但我无法理解以下段落。我计算了很多东西，并尽力估计，但我做不到。

回文长度：我们知道字符串的长度为 n，字母表中的符号数为 2，这表明长度为 2n 的回文数与长度为 n 的字符串一样多，即所需的回文数为 2 ^n。

Answer 1

回文是从左侧读取与从右侧读取相同的单词。所以前半部分完全决定了后半部分的字母。这就是为什么长度为 $2n$ 的回文数等于长度为 $n$ 的单词的数量——后者是长度为 $2n$ 的单词的所有可能的前半部分。

在一个由两个字母组成的字母表中，每个 $n$ 个位置都有两个选择，因此有 $2^n$ 个长度为 $n$ 的不同单词。