والدليل العام على التكافؤ من اثنين من FSMS في الوقت المحدد؟

Question

هل يوجد دليل عام على تكافؤ ماكينتي الولاية المحددة (الحتمية) التي تأخذ دائما وقتا محددا؟ وهذا هو، بالنظر إلى اثنين من FSMS، هل يمكنك إثبات أنه نظرا لأن المدخلات نفسها، فإنها ستنتج دائما نفس المخرجات دون الحاجة فعليا لتنفيذ FSMS (والتي قد تكون غير مهمة؟). إذا كان هذا الدليل موجود، فما هو تعقيد الوقت؟

Answer 1

هناك دليل، على الرغم من أنني لا أعرف ذلك. ابحث عن كتاب Sipser الخاص بالموضوع حول هذا الموضوع، حيث أعرفه من ذلك.

أزال ذاكرتي: في الأساس، هناك ضئيلة فريدة من نوعها DFA لإدارة DFA المعينة، وهناك خوارزمية التقليل تنتهي دائما. تقليل كل من A و B، ومعرفة ما إذا كان لديهم نفس الحد الأدنى من DFA. لا أعرف تعقيد التقليل، رغم أنه ليس سيئا للغاية (أعتقد متعدد الحدود). Graph Isomorphism من الصعب جدا للحساب، ولكن نظرا لأن هناك عقدة بداية خاصة، فقد نأمل أن تكون أسهل إلى حد ما. قد لا تتطلب حتى Isomorphism الرسم البياني، ليكون صادقا.

ولكن لا، أنت لا تحتاج أبدا إلى تشغيل DFAS فعليا، فقط تحليل هيكلهم.

Answer 2

لنفترض أن لديك اثنين من FSMS مع O (ن) تنص على. ثم يمكنك جعل FSM من الحجم O (ن²) يعترف بالفرق المتماثل فقط بلغاتهم. (جعل FSM له ينص على أن تتوافق مع زوج من الدول، واحدة من كل FSM. ثم في كل خطوة، قم بتحديث كل جزء من الزوج في وقت واحد. الدولة في FSM الجديدة هي قبول الدولة IFF بالضبط واحد من الزوج حالة قبول.) الآن تقليل هذه FSM ومعرفة ما إذا كانت هي نفس FSM الواحدة الواحدة التي ترفض كل شيء. تقليل FSM مع م يستغرق الدول وقتام سجل م)، لذلك بشكل عام يمكنك أن تفعل كل شيء في الوقت المناسب يا (ن² سجل ن).

تنص agor بشكل صحيح على أن Sipser هو مرجع جيد لهذه الأنواع من الأشياء. النقطة الأساسية لإجابتي هي أنه يمكنك القيام بذلك في وقت متعدد الحدود، حتى مع الأسهم الصغيرة.