每个字母表的转换图？
如何确定特定字母表上有多少个不同的转换图？例如，字母表 {x, y} 上有多少个 TG。我正在上一堂课，课程中提出了丹尼尔·IA·科恩（Daniel IA Cohen）的书《计算机理论导论》中的类似问题。有很多关于如何创建 TG 的示例，但没有任何内容可以确定每种语言可以创建多少个 TG。我假设我正在寻找有限数量的 TG？非常感谢！
How do you determine how many different Transition Graphs are over a particular alphabet? For example How many TG's are over the alphabet {x, y}. I am taking a class with a similar question from Daniel I. A. Cohen's book, "Introduction to computer theory." There are plenty of examples of how to create a TG but nothing to determine how many can be created per language. I'm assuming I'm looking for finite amount of TG's? Thank You very much!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这样的转移图有无数个。思考这个问题的一种方法是，您可以轻松构建一系列无限多个转换图，如下所示。假设我想接受某个固定n（即字母a的n个副本）的语言an。然后我可以构建一个接受该语言的转换图，如下所示。从起始状态开始，然后将 n 个新状态链接到该状态的末尾，每个状态都从“a”转换到下一个状态。使最后一个状态接受。
看到这些自动机只有可数无穷多个，我们可以考虑如何描述这些自动机。我们可以通过以下方式来做到这一点：以一元形式写出状态数，然后将这些状态之间的转换作为元组列表（开始、结束、字符）（全部以二进制编码），然后将接受状态作为状态数列表一元状态。连接在一起，这是一个二进制串，并且只有可数个有限的二进制串。
There are countably infinitely many such transition graphs. One way to think about this is that you can easily construct a family of infinitely many transition graphs as follows. Suppose that I want to accept the language an for some fixed n (that is, n copies of the letter a). Then I could construct a transition graph that accepts that language as follows. Begin with a start state, then chain n new states onto the end of that state, each with a transition on 'a' to the next state. Make the last state accepting.
To see that there are only countably infinitely many of these, we can think of how we would describe these automata. We could do so by writing out the number of states in unary, then the transisions between those states as a list of tuples (start, end, character) (all encoded in binary), then the accepting states as a list of the numbers of the states in unary. Concatenated together, this is a binary string, and there are only countably many finite binary strings.