¿Cómo convertir un árbol de decisión en un autómata?

Question

Por lo que sé,

• Un problema puede transformarse en una respuesta sí/no, que puede describirse por un árbol de decisión.
• La solución a un problema también puede representarse mediante un conjunto de cadenas (un lenguaje), lo que significa que el problema puede considerarse como un problema de membresía.
• Este conjunto de cuerdas también puede ser representado por un autómata, aunque la forma en que se hace todavía es vaga en mi mente.

Mis preguntas son:

1. ¿Cuál es la relación entre un árbol de decisión y un autómata?

2. ¿Cómo convertir un árbol de decisión en un autómata?

Intenté leer algunos artículos relacionados con esto y de alguna manera "sé" que estos conceptos están relacionados entre sí, pero todavía siento que no entiendo bien la relación y cómo convertirlos entre sí.

Answer 1

Un árbol de decisión es un modelo de cálculo que tiene sentido, por ejemplo, constante tamaño.Por el contrario, un lenguaje suele ser una colección de instancias de tamaño ilimitado.Un autómata (en este contexto) es un modelo de computación que describe un lenguaje.

El resultado de todo esto es que, en la mayoría de las circunstancias, no tiene sentido convertir un árbol de decisión en un autómata.

Aquí hay unos ejemplos:

• Determinar si una persona tiene sobrepeso teniendo en cuenta su edad, sexo, altura y peso.Esto se puede resolver mediante un árbol de decisión o mediante una tabla.
• Decidir si una imagen de 64x64 describe un perro o un gato.Esto también se puede resolver mediante un árbol de decisiones, aunque no se recomienda.
• Decidir si un número entero dado es primo.Este problema de decisión define un lenguaje, el lenguaje de los números primos.Agrawal, Kayal y Saxena dieron un procedimiento eficiente para resolver este problema en 2002, que sin embargo no puede ser implementado por el tipo de autómatas usualmente considerados en las clases de teoría de computación (DFA, NFA, PDA).
• Decidir si una cuerda dada es un palíndromo.Este problema de decisión define un lenguaje y puede resolverse mediante un autómata pushdown, pero no mediante un DFA/NFA.