在自动机理论中，帕兰德罗马的长度是什么意思? 甚至回文? 奇怪的回文?

Question

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

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

Answer 1

回文是一个从左边读到和从右边读出的词。所以前半部分完全决定了后半部分的字母。这就是为什么长度为 $2n$ 的回文数等于长度为 $n$ 的单词数 - 后者是长度为 $2n$ 的单词的所有可能的前半部分。

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