كيفية تحويل شجرة القرار إلى Automaton؟

Question

من ما أعرفه،

• مشكلة يمكن تحويلها إلى إجابة نعم / لا يمكن أن تكون وصفها شجرة القرار.
• حل مشكلة أيضا يمكن تمثيلها من خلال مجموعة من السلاسل (لغة)، مما يعني أن المشكلة يمكن اعتبارها مشكلة عضوية.
• هذه المجموعة من السلاسل يمكن كما يتم تمثيلها بواسطة Automaton، على الرغم من كيفية القيام بذلك لا يزال غامضة في ذهني.

أسئلتي هي:

1. ما هي العلاقة بين شجرة القرار وآوتاوتون؟

2. كيفية تحويل شجرة القرار إلى Automaton؟

لقد حاولت قراءة بعض المواد المتعلقة بهذا، وترتبط هذه المفاهيم "معرفة" بطريقة أو بأخرى مع بعضها البعض، ولكن لا تزال تشعر أنني لا أفهم تماما العلاقة وكيفية تحويلها إلى بعضها البعض.

Answer 1

شجرة القرار هي نموذج للحساب الذي يجعل من المنطقي على مثيل حجم ثابت . في المقابل، عادة ما تكون لغة مجموعة من حالات حجم غير محدود. تتمثل Automaton (في هذا السياق) نموذجا للحساب الذي يصف اللغة.

uphot من كل هذا هو أنه في معظم الحالات، فإنه لا معنى له حقا تحويل شجرة القرار إلى Automaton.

هنا بعض الأمثلة:

• تحديد ما إذا كان الشخص يعاني من زيادة الوزن بالنظر إلى سنهم والجنس والطول والوزن. يمكن حل هذا بواسطة شجرة القرار أو بواسطة طاولة.
• يقرر ما إذا كانت صورة 64x64 تصف الكلب أو القط. يمكن أيضا حل ذلك بواسطة شجرة قرار، على الرغم من أن هذا غير مستحسن.
• يقرر ما إذا كان عدد صحيح معين هو رئيس الوزراء. تحدد مشكلة هذه القرار لغة، لغة الأعداد الأولية. أعطى Agrawal، Kayal و Saxena إجراء فعال لحل هذه المشكلة في عام 2002، ومع ذلك، لا يمكن تنفيذها بواسطة نوع من Automata عادة ما يتم النظر في نظرية الطبقات الحسابية (DFA، NFA، PDA).
• يقرر ما إذا كانت سلسلة معينة هي palindrome. تحدد مشكلة القرار هذه اللغة، ويمكن حلها بواسطة Automaton Pushnation، ولكن ليس بواسطة DFA / NFA.