Как преобразовать дерево решений в автомат?

Question

от того, что я знаю,

.
• проблема может быть преобразована в ответ Да / Нет, что может быть описывается деревом принятия решений.
• решение проблемы также можно представить набором строк (языка), что означает, что проблема может рассматриваться как проблема членства.
• Этот набор строк может также быть представленным автоматом, хотя, как это сделано, все еще смутно в моей голове.

Мои вопросы:

1. Что такое отношения между деревом решений и автоматом?

2. Как конвертировать дерево решений в автомат?

Я пытался прочитать некоторые статьи, связанные с этим, и как-то «знают» эти концепции связаны друг с другом, но все же чувствуют, что я не совсем понимаю связь и как преобразовать их друг к другу.

.

Answer 1

Дерево решений - это модель вычислений, которая имеет смысл, например, Constance Constance . Напротив, язык обычно является коллекцией экземпляров неограниченного размера. Автомат (в этом контексте) является моделью вычислений, которая описывает язык.

Выделение всего этого является то, что в большинстве случаев на самом деле не имеет смысла преобразовывать дерево решений на автомат.

Вот несколько примеров:

.
• Определение того, является ли человек избыточный вес, учитывая их возраст, пол, высоту и вес. Это может быть решено варом решений, или на таблице.
• Решая, описывает ли изображение 64x64, описывает собаку или кошку. Это также может быть решено варом решений, хотя это не рекомендуется.
• Решая, является ли данное целое число главное. Эта проблема решений определяет язык, язык простых чисел. Agrawal, Kayal и Saxena дали эффективную порядок решения этой проблемы в 2002 году, что, однако, не может быть реализована такими автоматами, обычно рассматриваемыми в теории вычислений классов (DFA, NFA, PDA).
• Решая, является ли данная строка палиндром. Эта проблема принятия решений определяет язык и может быть решена автоматическим автоматом, но не DFA / NFA.