NFA لسؤال DFA

Question

أولا، هذا ليس سؤالا يسأل عن خوارزمية تحويل NFA إلى DFA.

من المعروف (وأثبت) أن DFA المكافئ من NFA لديه على الأكثر 2^ن الدول، على الرغم من أن معظم الأوقات ستحصل على نفس عدد الدول مثل NFA.

كيف يمكنني التنبؤ بتقدير لعدد الدول التي ستحصل عليها DFA المكافئ NFA؟ أي نوع معين من NFA سيتطلب من DFA مكافئ أن يكون لديك 2^ن تنص على؟

السبب الخاص بي لسؤال هذا هو أن تكون قادرا على "اختراع" بعض NFAS التي ستنتج بالتأكيد، دون النظر في التقليل، 2^ن - 1 الدول بالإضافة إلى "الدولة الميتة".

Answer 1

عدد الدول تنفجر بسبب غير الحتمية, ، وهو مفتاح سؤالك.

إذا كنت تأخذ NFA، حيث يتم تحديد كل انتقال بشكل فريد، أي NFA حتمية، فمن لا شيء سوى DFA عادي. ومع ذلك، بمجرد أن يكون لديك دولة محتملة حيث تختلف فترة الانتقال عن DFA.

فكر في خوارزمية التحويل وإلقاء نظرة على ما يحدث إذا كان لديك اثنين أو أكثر من التحولات مع نفس التسمية لحالة. هذا هو المكان الذي تحتاج فيه الدول الجديدة التي تتوافق مع مجموعات الدول.

وبالتالي فإن السؤال ينزل عن معرفة عدد هذه الدول SuperSet يمكن الوصول إليها بالفعل. بالطبع، يمكنك اختراع خوارزمية خيالية لذلك، ولكن للحصول على الرقم الصحيح، قم ببساطة بتشغيل خوارزمية التحويل العادية وإزالة حالات غير قابلة للوصول إليها.

بالنسبة إلى NFA مع الدول N التي تعادلها DFA لديها 2 ^ n تنص على استغلال عدم الحتمية. الفكرة الأولى ستكون تسمية جميع التحولات نفسها، ومع ذلك، فإن ذلك لا يعمل بشكل جيد للغاية. وبدلا من ذلك تذكر أنك بحاجة إلى أن تكون قادرا على الوصول إلى جميع مجموعات فرعية من الدول مع بعض الملصقات.

إذا لم تحسب حالة البداية، فيمكنك القيام بالبناء التالي: قم بإنشاء العقد N ولكل منها من بين 2 ^ n إنشاء ملصق فريد وفي NFA أضف انتقالا مع هذه الملصق إلى كل عقدة من تلك المجموعة. هذا يمنحك NFA مع دول N + 1 (1 كونها حالة البداية)، حيث يتطلب DFA 2 ^ n +1. بالطبع، يصبح مهتز، بمجرد أن تحصل على 2 ^ n DFA الولايات بعد التقليل.

Answer 2

حسنا، ابدأ بافتراض أن n -> n. الآن، لكل عملية انتقال غير محددة حيث من دولة واحدة، يمكنك الانتهاء من الولايات المتحدة في X، تضاعف تقديرك بواسطة X. قد لا يكون هذا دقيقا، كما قد تعتمد مزدوجا. ولكن يجب أن يمنحك الحد الأعلى.

ومع ذلك، فإن الطريقة المؤكدة الوحيدة لبناء DFA المقابلة ثم عد الدول (أعتقد).

أخيرا، ربما يمكنك تبسيط بعض DFAS (و NFAS لهذه المسألة)، ولكن هذه قصة جديدة كاملة ...

Answer 3

اتخاذ كدالة من N، مع Start State S و Stired State N، NFA A(N):

S a-> S
S b-> S
S a-> 0 // NOTE: only "a" allows you to leave state S
0 a-> 1
0 b-> 1
1 a-> 2
1 b-> 2
...
N-1 a-> N
N-2 b-> N
N

يجب أن يكون واضحا أن هذا يقبل جميع الأوتار في [ab]* الذي الرسالة nth-from الأخيرة هو a.

تحديد A(N) يجب أن نتذكر رسائل N-1 السابقة، بفعالية (تحتاج إلى معرفة كل المواقف في تلك النافذة التي كانت a, ، بحيث تنتهي السلسلة بشكل غير متوقع، يمكنك القول ما إذا كان هناك a n أحرف قبل).

لست متأكدا مما إذا كان هذا يضرب بالضبط عدد الدول التي تريدها، ولكنها على الأقل في غضون عامول من 2 - جميع مجموعات فرعية من {0,...,N} ممكن، لكنك أيضا في S. وبعد هذا ينبغي أن يكون 2^(N+1) الدول، ولكن A(N) ملك N+2 تنص على.

Answer 4

للتوسع في الجواب الممتاز من جوناثان غرآل.

أضف إلى كل ولاية 0, 1, ..., N من A(N) selfloop المسمى c, ، أي، يمكنك إضافة التحويلات التالية:
0 c-> 0
1 c-> 1
...
N c-> N

ثم افترض c لا يطلق النار أبدا، DFA يحتوي على نفسه 2^(N+1) دول جوناثان DFA. ومع ذلك، كلما c لوحظ من الدولة {S,j,k,...,z} <> {S} نصل إلى الدولة {j,k,...,z}. وبعد وبالتالي كل مجموعات فرعية من {S,0,...,N} ممكن باستثناء المجموعة الفارغة و DFA 2^(N+2)-1 الدول في حين A(N) لديها N+2 تنص على.