Come convertire un albero decisionale su un Automaton?

Question

Da quello che conosco,

.
• un problema può essere trasformato in una risposta sì / no, che può essere descritto da un albero decisionale.
• Soluzione a un problema può anche essere rappresentata da un set di stringhe (una lingua), il che significa che il problema può essere considerato un problema di iscrizione.
• Questo set di stringhe può anche essere rappresentato da un Automaton, anche se come è stato fatto è ancora vago nella mia mente.

Le mie domande sono:

.

1. Qual è la relazione tra un albero decisionale e un Automaton?

2. Come convertire un albero decisionale su un Automaton?

Ho cercato di leggere alcuni articoli relativi a questo, e in qualche modo "sapere" questi concetti sono legati l'uno con l'altro, ma ritengono ancora che non capisco la relazione e come convertirli tra loro.

.

Answer 1

Un albero decisionale è un modello di calcolo che ha senso per esempio di costante . Al contrario, una lingua è solitamente una raccolta di casi di dimensioni non trattate. Un Automaton (in questo contesto) è un modello di calcolo che descrive una lingua.

Il risultato di tutto questo è che nella maggior parte delle circostanze, non ha senso convertire un albero decisionale su un automa.

Ecco alcuni esempi:

.
• Determinare se una persona è sovrappeso data la loro età, sesso, altezza e peso. Questo può essere risolto da un albero decisionale o da un tavolo.
• Decidere se un'immagine 64x64 descrive un cane o un gatto. Questo può anche essere risolto da un albero decisionale, anche se non è raccomandato.
• Decidere se un determinato intero è un primo. Questo problema decisionale definisce una lingua, la lingua dei primi. Agrawal, Kayal e Saxena hanno dato una procedura efficiente per risolvere questo problema nel 2002, il che tuttavia non può essere implementato dal tipo di automi di solito considerato in teoria delle classi di calcolo (DFA, NFA, PDA).
• Decidere se una determinata stringa è un palindromo. Questo problema decisionale definisce una lingua e può essere risolta da un Automaton Pushdown, ma non da un DFA / NFA.