خلال قرائتي لكود مصدري لأحد المفسرات لـ Python بالتحديد PyPy وجدت في أحد مراحله اعنماده على ما يسمى الـ DFA أو Deterministic finite automaton
و الـ NFA أو Non-Deterministic finite automaton
و أن DFA نظرية للأتمتة تصف عدد من الحالات و العمليات للانتقال بين هذه الحالات و كأنها المقابل النظري للـ State Machine مالم افهمه الـ NFA ماهي؟ و مالفرق بينهما ؟
أهلاً علي.. سعيد بالمقترح الطيب هذا :)
الفرق الرئيسي بين NFA و DFA هو في الphase transition او بالاصح the next state
في الDFA, عندما تكون في حالة state معينة ولديك input معين ، تعرف بالضبط ماهي الnext state
بمعنى اخر the next state is determined in advance
مثلاً تخيل ان المدخلات عندك هي صفر وواحد
تصور انك في state s4 بحيث اذا المدخل صفر تنتقل للحالة s3 اما اذا المدخل واحد تنتقل للحالة s5 .. هذا تصور بسيط/
s5<^1----s4----^0>s3
في الNFA ممكن يكون الانتقال لأكثر من حالة بمعنى اخر ان الnext state عباره عن مجموعة من الحالات وليست حالة واحدة فقط كما في DFA ..
ماشاء الله.. موقع جميل تمت اضافته للمفضلة..
هذي الصورة بالضبط للي كنت اقصدة
مرحبا اخي ,,
اعنقد تعريفك جدا خطا.
NFA ,, عند وجودك في حالة معنية فرضا q0 وقرات مدخل مثل 1 يمكنك الانتقال الى q1 او q2. الي انك لا تسطبع التقرير اي مسار تسلكه q1 او q2.
في حالة DFA هذا غير ممكن. فيجب عند قراءة مدخل مثل ١ الانتقال الى حالة واحدة واشدد عليها حالة واحدة فقط مثل q1.
مثال على NFA,,
انت في q0 وتقرا 1 يمكنك البقاء بنفس الحالة او الذهاب الى q1
هذه الميزة غير موجودة في DFA
مدخل صحيح ل مثال هو ,, 01011
معلومة ,, كل NFA يمكن تحويلها الى DFA لاكن NFA اسهل :)
اهلا اخوي احمد.
ماادري اين الخطأ الذي وقعت به انا.
في حديثي لم اتطرق للNFA الا في اخر سطر. كل ماقبلها كان كلام عن الDFA
:) ,,
في هذا السطر ,, في الNFA ممكن يكون الانتقال لأكثر من حالة بمعنى اخر ان الnext state عباره عن مجموعة من الحالات وليست حالة واحدة فقط كما في DFA ,,
فهمت منه ان NFA ليس linear اما DFA linear .
فهمت مثالك بطريقة خاطئة :).
اعتذر جدا :)
التعليقات