Wie konvertiere ich einen Entscheidungsbaum in einen Automaton?

Question

von dem, was ich kenne,

• Ein Problem kann in eine Ja / Nein-Antwort umgewandelt werden, die sein kann von einem Entscheidungsbaum beschrieben.
• Lösung für ein Problem kann auch durch einen Satz von Saiten (einer Sprache) dargestellt werden, dh das Problem kann als Mitgliedsspielproblem angesehen werden.
• Dieser Satz von Saiten kann auch von einem Automaton dargestellt werden, obwohl immer noch der Fall ist vage in meinem Kopf.

Meine Fragen sind:

.

1. Wie ist die Beziehung zwischen einem Entscheidungsbaum und einem Automaton?

2. Wie kann man einen Entscheidungsbaum in einen Automaton umwandeln?

Ich habe versucht, einige Artikel zu lesen, die damit verbunden sind, und irgendwie "wissen" diese Konzepte sind miteinander verbunden, aber immer noch das Gefühl, dass ich die Beziehung nicht ganz verstehe und wie sie sie in einander umwandeln kann.

Answer 1

Ein Entscheidungsbaum ist ein Berechnungsmodell, das zum Beispiel von konstanter -Größe sinnvoll ist. Im Gegensatz dazu ist eine Sprache in der Regel eine Sammlung von Instanzen der ungebundenen Größe. Ein Automat (in diesem Zusammenhang) ist ein Berechnungsmodell, das eine Sprache beschreibt.

Das UpSHOT von all dem ist, dass es in den meisten Umständen nicht wirklich sinnvoll ist, einen Entscheidungsbaum in einen Automaton umzuwandeln.

Hier sind einige Beispiele:

.
• Bestimmen, ob eine Person überzeugt ist, dass Alter, Geschlecht, Höhe und Gewicht übergewichtig ist. Dies kann durch einen Entscheidungsbaum oder durch einen Tisch gelöst werden.
• Entscheidend, ob ein 64x64-Bild einen Hund oder eine Katze beschreibt. Dies kann auch von einem Entscheidungsbaum gelöst werden, obwohl dies nicht empfohlen wird.
• Entscheidend, ob eine gegebene Ganzzahl eine Primzahl ist. Dieses Entscheidungsproblem definiert eine Sprache, die Sprache der Primaten. AGRAWAL, KAYAL und SAXENA gaben ein effizientes Verfahren zur Lösung dieses Problems im Jahr 2002, das jedoch nicht von der Art von Automaten umgesetzt werden kann, die in der Regel in der Theorie von Rechenklassen (DFA, NFA, PDA) berücksichtigt werden.
• Entscheidend, ob eine gegebene Zeichenfolge ein Palindrom ist. Dieses Entscheidungsproblem definiert eine Sprache und kann von einem Pushdown-Automaton gelöst werden, jedoch nicht von einem DFA / NFA.