Comment convertir un arbre de décision à un automate?

Question

de ce que je sais,

• Un problème peut être transformé en une réponse oui / non, qui peut être décrit par un arbre de décision.
• La solution à un problème peut également être représentée par un ensemble de chaînes (langue), ce qui signifie que le problème peut être considéré comme un problème d'adhésion.
• Cet ensemble de chaînes peut également être représenté par un automate, bien que cela soit fait est toujours vague dans mon esprit.

Mes questions sont:

1. Quelle est la relation entre un arbre de décision et un automate?

2. Comment convertir un arbre de décision à un automate?

J'ai essayé de lire des articles en relation avec cela, et d'une manière ou d'une autre, ces concepts sont liés les uns avec les autres, mais sentent toujours que je ne comprends pas bien la relation et comment les convertir les uns aux autres.

Answer 1

Un arbre de décision est un modèle de calcul qui a du sens, par exemple de la taille constante . En revanche, une langue est généralement une collection d'instances de taille sans bornes. Un automate (dans ce contexte) est un modèle de calcul décrivant une langue.

Le résultat de tout cela est que dans la plupart des cas, il n'a pas vraiment de sens de convertir un arbre de décision à un automate.

Voici quelques exemples:

• Déterminer si une personne est en surpoids compte tenu de leur âge, de leur sexe, de la hauteur et du poids. Cela peut être résolu par un arbre de décision ou par une table.
• Décider si une image 64x64 décrit un chien ou un chat. Cela peut également être résolu par un arbre de décision, bien que ce n'est pas recommandé.
• Décider si un entier donné est une prime. Ce problème de décision définit une langue, la langue des nombres premiers. Agrawal, Kayal et Saxena ont donné une procédure efficace de résolution de ce problème en 2002, ce qui ne peut toutefois pas être mis en œuvre par le type d'automates généralement considérés en théorie des classes de calcul (DFA, NFA, PDA).
• Décider si une chaîne donnée est un palindrome. Ce problème de décision définit une langue et peut être résolu par un automate de poussée, mais pas par une DFA / NFA.