如何将决策树转换为自动机？

Question

从我所知道的，

• 一个问题可以转换为是/否答案，可以是 由决策树描述。
• 解决问题的解决方案也可以由一组字符串（一种语言）表示，这意味着问题可以被视为隶属问题。
• 这套字符串可以 也由自动机代表，虽然它是如何完成的 在我的脑海里含糊不清。

我的问题是：

1. 决策树和自动机之间的关系是什么？

2. 如何将决策树转换为自动机？

我试图阅读与此相关的一些文章，以某种方式“知道”这些概念彼此相关，但仍然觉得我不太了解关系以及如何将它们转换为彼此。

Answer 1

决策树是一个计算模型，这对于常数大小有意义。相比之下，一种语言通常是一个无界大小的情况的集合。自动机（在此上下文中）是描述语言的计算模型。

所有这一切都在大多数情况下，将决策树转换为自动机并没有真正有意义。

以下是一些例子：

• 确定一个人是否超重给出了他们的年龄，性别，身高和体重。这可以通过决策树或表格来解决。
• 决定64x64图像是否描述了狗或猫。这也可以通过决策树来解决，但不推荐。
• 决定给定的整数是素数。该决策问题定义了一种语言，素质语言。 Agrawal，Kayal和Saxena在2002年给出了一个有效的程序，以便在2002年解决这个问题，然而不能通过计算类理论（DFA，NFA，PDA）的自动机等自动机。
• 决定给定字符串是否是parindrome。该决策问题定义了一种语言，可以通过推动自动机来解决，但不是DFA / NFA。