決定木をオートマトンに変換する方法

Question

私が知っているものから、

• 問題は、はい/いいえ回答に変換することができます。 決定木によって記述されています。
• 問題への解決策も一連の文字列（言語）で表すことができます。つまり、問題はメンバーシップの問題と見なすことができます。
• この文字列のセット それがどのようにして行われているのかは、オートマトンによっても表されます。 私の心の中で漠然とした。

私の質問は次のとおりです。

1. 決定木とオートマトンの関係は何ですか？

2. 決定木をオートマトンに変換する方法？

これに関連するいくつかの記事を読みようとしました、そしてどういうわけかこれらの概念は互いに関連していますが、それでも関係をまったく理解していないと感じています。

Answer 1

決定木は、定数サイズの意味を考慮した計算のモデルです。対照的に、言語は通常、無制限のサイズのインスタンスの集まりです。オートマトン（この文脈で）は、言語を説明する計算モデルです。

これがすべての店舗では、ほとんどの状況では、決定木をオートマトンに変換することは本当に理にかなっていません。

ここにいくつかの例があります：

• 人が年齢、性別、身長、そして体重を与えられた人が太りすぎであるかどうかを判断します。これは、決定木、またはテーブルによって解決できます。
• 64 x 64の画像が犬や猫かを説明するかを決定する。これはまた決定木によって解決されることができますが、それはお勧めできません。
• 与えられた整数がプライムかどうかを決定します。この決定問題は言語、PRIMESの言語を定義します。 AGRAWAL、Kayal、Saxenaは2002年にこの問題を解決するための効率的な手順を示しましたが、通常は計算クラスの理論では考慮されるオートマトンの種類（DFA、NFA、PDA）。
• 与えられた文字列がPalindromeであるかどうかを決定します。この決定問題は言語を定義し、PushDown Automatonによって解決できますが、DFA / NFAでは解決できません。