Como converter uma árvore de decisão para um autômato?

Question

do que eu sei,

• Um problema pode ser transformado em uma resposta sim / não, que pode ser descrito por uma árvore de decisão.
• solução para um problema também pode ser representado por um conjunto de strings (um idioma), o que significa que o problema pode ser considerado como um problema de associação.
• este conjunto de strings pode também ser representado por um autômato, embora como é feito ainda Vaga em minha mente.

minhas perguntas são:

.

1. Qual é a relação entre uma árvore de decisão e um autômato?

2. Como converter uma árvore de decisão para um autômato?

Eu tentei ler alguns artigos relacionados a isso, e de alguma forma 'sabe' esses conceitos estão relacionados entre si, mas ainda sinto que eu não entendo muito bem a relação e como convertê-los uns aos outros.

.

Answer 1

Uma árvore de decisão é um modelo de computação que faz sentido, por exemplo, de um tamanho de constante . Em contraste, uma linguagem é geralmente uma coleção de casos de tamanho ilimitado. Um autômato (neste contexto) é um modelo de computação que descreve uma linguagem.

O resultado de tudo isso é que na maioria das circunstâncias, não faz sentido converter uma árvore de decisão para um autômato.

Aqui estão alguns exemplos:

• Determinando se uma pessoa está acima do peso dada a idade, sexo, altura e peso. Isso pode ser resolvido por uma árvore de decisão, ou por uma tabela.
• Decidindo se uma imagem de 64x64 descreve um cão ou um gato. Isso também pode ser resolvido por uma árvore de decisão, embora isso não seja recomendado.
• decidindo se um determinado inteiro é um primo. Este problema de decisão define uma linguagem, a linguagem dos primos. Agrawal, Kayal e Saxena deu um procedimento eficiente para resolver este problema em 2002, que, no entanto, não pode ser implementado pelo tipo de autômato geralmente considerado em teoria das classes de computação (DFA, NFA, PDA).
• decidindo se uma determinada string é um palíndromo. Este problema de decisão define uma linguagem, e pode ser resolvido por um autômato de pushdown, mas não por um DFA / NFA.