graph - 每个字母的转换图？

Question

您如何确定特定字母表上有多少不同的转换图？例如，字母表 {x, y} 上有多少个 TG。我正在上一堂课，上面有 Daniel IA Cohen 的书“计算机理论导论”中的类似问题。有很多关于如何创建 TG 的示例，但无法确定每种语言可以创建多少个。我假设我正在寻找有限数量的 TG？非常感谢！

Answer 1

有无数个这样的转移图。考虑这一点的一种方法是，您可以轻松地构建一个由无限多个转换图组成的族，如下所示。假设我想为某个固定的 n（即字母 a 的 n 个副本）接受语言 a ^{n 。}然后我可以构造一个接受该语言的转换图，如下所示。从一个开始状态开始，然后将 n 个新状态链接到该状态的末尾，每个状态都有一个从“a”到下一个状态的转换。使最后一个状态接受。

要看到这些自动机只有可数无限多，我们可以考虑如何描述这些自动机。我们可以通过写出一元的状态数，然后将这些状态之间的转换作为元组列表（开始、结束、字符）（全部以二进制编码），然后将接受状态作为一元的状态。连接在一起，这是一个二进制字符串，并且只有可数个有限的二进制字符串。