في نظرية احركه(فرع علوم الكمبيوتر) إن تقليل حتميه محدده الحركة إلى الحد الأدنى هو مهمة تحويل حتميه محدده الحركة(DFA) إلى حتميه محدده الحركة مكافئ يحتوي على عدد أدنى من الحالات. هنا، يُطلق على اثنين من DFAs اسمًا مكافئًا في حالة تعرفهما على اللغة العادية نفسها. العديد من الخوارزميات المختلفة التي تحقق هذه المهمة معروفة وموصوفة في كتب قياسية حول نظرية الروتين.
تصغير DFA
لكل لغة عادية، يوجد أيضًا عدد قليل من الحركات يقبل ذلك، أي، DFA مع عدد أدنى من الحالات وهذا DFA فريد (باستثناء أنه يمكن إعطاء أسماء مختلفة). يضمن الحد الأدنى DFA الحد الأدنى من التكلفة الحسابية للمهام مثل مطابقة الأنماط.
هناك فئتان من الحالات التي يمكن إزالتها أو دمجها من DFA الأصلي دون التأثير على اللغة التي تقبلها لتصغيرها.
*الحالات التي لا يمكن الوصول إليها هي الحالات التي لا يمكن الوصول إليها من الحالة الأولية لـ DFA ، لأي سلسلة إدخال.
*الحالات غير المميزة هي تلك التي لا يمكن تمييزها عن بعضها البعض لأي سلسلة إدخال.
عادةً ما يتم تقليل DFA إلى ثلاث خطوات، بما يتوافق مع إزالة أو دمج الدول المعنية. وبما أن التخلص من الحالات غير القابلة للتمييز هو الأكثر غلاءً للحساب، فإنه يتم عادة كخطوة أخيرة.
الحالات التي لا يمكن الوصول إليها:
حالة p من DFA -, M=(Q, Σ, δ, q0, F) لا يمكن الوصول إليه في حالة عدم وجود مثل هذه السلسلة w في Σ* موجود لأي منها p=δ*(q0, w) . يمكن الحصول على الحالات التي يمكن الوصول إليها باستخدام الخوارزمية التالية :
let reachable_states := {q0};
let new_states := {q0};
do {
temp := the empty set;
for each q in new_states do
for each c in Σ do
temp := temp ∪ {p such that p = δ(q,c)};
end;
end;
new_states := temp \ reachable_states;
reachable_states := reachable_states ∪ new_states;
} while (new_states ≠ the empty set);
unreachable_states := Q \ reachable_states;
يمكن إزالة الحالات التي لا يمكن الوصول إليها من DFA دون التأثير على اللغة التي تقبلها.
*الحالات غير المميزة
خوارزمية هوبكروفت :
تعتمد إحدى الخوارزميات لدمج الحالات غير المميزة لـ DFA ، بسبب هوبكروفت (1971),على تحسين القسم وتقسيم حالات DFA إلى مجموعات حسب سلوكها. تمثل هذه المجموعات فئات مكافئة لعلاقة تكافؤ Myhill – Nerode ، حيث تكون كل حالتين من نفس القسم متساويتين إذا كان لديهم نفس السلوك لكل تسلسلات الإدخال. بمعنى أنه بالنسبة لكل حالتين p1 و p2 ينتمون إلى نفس فئة التكافؤ داخل القسم P ، وكل كلمة إدخال w ، يجب أن تأخذ التحولات المحددة بواسطة w دائمًا الحالات p1 و p2 إلى حالات متساوية، ينص على قبول كليهما، أو ينص على رفض كليهما. يجب ألا يكون من الممكن أن يأخذ p1 إلى حالة قبول و p2 إلى حالة رفض أو العكس.
يصف الكود الزائف التالي الخوارزمية:
P := {F, Q \ F};
W := {F};
while (W is not empty) do
choose and remove a set A from W
for each c in Σ do
let X be the set of states for which a transition on c leads to a state in A
for each set Y in P for which X ∩ Y is nonempty and Y \ X is nonempty do
replace Y in P by the two sets X ∩ Y and Y \ X
if Y is in W
replace Y in W by the same two sets
else
if |X ∩ Y| <= |Y \ X|
add X ∩ Y to W
else
add Y \ X to W
end;
end;
end;
تبدأ الخوارزمية بجزء خشن جدًا: كل زوج من الحالات المتساوية وفقًا لعلاقة Myhill – Nerode تنتمي إلى نفس المجموعة في القسم، ولكن الأزواج غير المتكافئة قد تنتمي أيضًا إلى نفس المجموعة. ويقوم تدريجياً بتحسين التقسيم إلى عدد أكبر من المجموعات الأصغر، في كل خطوة تقسم مجموعات الدول إلى أزواج من مجموعات فرعية لا تكفي بالضرورة. التقسيم الأولي هو فصل الولايات إلى مجموعتين من الدول التي من الواضح أنها لا تملك نفس السلوك مثل بعضها البعض: الحالات المقبولة والحالات المرفوضة. بعد ذلك، تختار الخوارزمية بشكل متكرر مجموعة A من القسم الحالي ورمز الإدخال c ، وتقسم كل مجموعة من المجموعات إلى جزأين (ربما فارغين): المجموعة الفرعية للحالات التي تؤدي إلى A على رمز الإدخال c ، مجموعة فرعية من الحالات التي لا تؤدي إلى A. نظرًا لأن A معروفة بالفعل بسلوك مختلف عن المجموعات الأخرى من القسم، فإن المجموعات الفرعية التي تؤدي إلى A لها أيضًا سلوك مختلف عن المجموعات الفرعية التي لا تؤدي إلى A. يمكن العثور على انقسامات من هذا النوع، تنتهي الخوارزمية.
ليما. بالنظر إلى حرف ثابت c ودرجة مكافئة من الصنف Y التي تنقسم إلى فئتين مكافحتين B و C ، يكون واحد فقط من B أو C ضروريًا لتحسين القسم بأكمله.
مثال: لنفترض أن لدينا فئة مكافئة Y التي تنقسم إلى فئتين مكافحتين B و C. لنفترض أن لدينا أيضًا فئات D و E و F ؛ يحتوي D و E على حالات مع انتقالات إلى B على حرف c ، بينما ينتقل F إلى C على حرف c. بواسطة ليما، يمكننا أن نختار إما B أو C كمعدِّل، دعنا نقول B. ثم تنقسم ولايتان D و E من خلال انتقالاتهما إلى B. لكن F ، التي لا تشير إلى B ، ببساطة لا تنقسم خلال التكرار الحالي للخوارزمية ؛ سيتم صقله بواسطة مطهرات أخرى.
الملاحظة: كل من B أو C ضروري لتقسيم فئات الإحالة مثل D و E و F بشكل صحيح - لن تفعل المجموعات الفرعية.
الغرض من العبارة الشرطية (إذا كان Y في W) هو تصحيح W ، مجموعة من المميّزين. نرى في البيان السابق في الخوارزمية أن Y قد تم تقسيمه للتو. إذا كانت Y في W ، فقد أصبحت قديمة كوسيلة لتقسيم الطبقات في التكرارات المستقبلية. لذا يجب استبدال Y بكلتا التقسيمات بسبب الملاحظة أعلاه. إذا لم تكن Y في W ، فستحتاج إلى إضافة واحدة فقط من الشريحتين، وليس كليهما، إلى W بسبب ليما أعلاه. اختيار الأصغر من الشقين يضمن أن الإضافة الجديدة إلى W لا تزيد عن نصف حجم Y ؛ هذا هو جوهر خوارزمية هوبكروفت : كيف يحصل على سرعته، كما هو موضح في الفقرة التالية.
أسوأ وقت تشغيل هذه الخوارزمية هو O(ns log n) ، حيث n هو عدد الحالات و s هو حجم الأبجدية. ويتبع هذا الالتزام من حقيقة أنه بالنسبة لكل من عمليات نقل البيانات الآلية، تكون للمجموعات المرسومة من Q التي تحتوي على الحالة المستهدفة للانتقال أحجام تنخفض بالنسبة لبعضها بعامل اثنين أو أكثر، وبالتالي فإن كل انتقال يشارك في O (سجل ن) من الخطوات تقسيم في الخوارزمية. تسمح بنية بيانات تقسيم التقسيم بتنفيذ كل خطوة منقسمة في الوقت الذي يتناسب مع عدد التحولات التي تشارك فيه. [5] يظل هذا هو أكثر الخوارزميات فعالية لحل المشكلة، وبالنسبة لتوزيعات معينة من المدخلات، يكون تعقيد الحالة المتوسطة أفضل، O(n log log n) .
بمجرد استخدام خوارزمية هوبكروفت في تجميع حالات الإدخال DFA في فئات التكافؤ، يمكن إنشاء DFA الأدنى من خلال تشكيل حالة واحدة لكل فئة من فصول المعادلة. إذا كانت S عبارة عن مجموعة من الحالات في P ، s هي حالة في S ، و c هي حرف إدخال، فإن الانتقال في الحد الأدنى DFA من حالة S ، عند الإدخال c ، ينتقل إلى المجموعة التي تحتوي على الحالة التي سوف يدخل إدخالات الحركة من الحالة s على الإدخال c. الحالة الأولية للحد الأدنى للميزانية هي التي تحتوي على الحالة الأولية للإدخال DFA ، والحالات المقبولة للـ DFA الأدنى هي الدول التي يقبل أعضاءها حالات إدخال DFA.
خوارزمية مور:
ترجع خوارزمية مور إلى الحد الأدنى من DFA إلى إدوارد مور مور (1956). مثل خوارزمية هوبكروفت، يحافظ على قسم يبدأ بفصل قبول من الحالات المرفوضة، ويكرر القسم بشكل متكرر حتى لا يمكن إجراء المزيد من التحسينات. في كل خطوة، فإنه يستبدل القسم الحالي بأكثر التحسينات المشتركة لقسم s + 1 ، واحد منها هو القسم الحالي والآخر هو التقديرات الأولية للقسم الحالي تحت وظائف النقل لكل من رموز الإدخال. تنتهي الخوارزمية عندما لا يغير هذا الاستبدال القسم الحالي. يعتبر تعقيد زمن الحالة الأسوأ هو O(n2s) : يمكن تنفيذ كل خطوة من الخوارزمية في الزمن O(ns) باستخدام متغير من فرز الجذر لإعادة ترتيب الحالات بحيث تكون الحالات في نفس المجموعة من القسم الجديد متتالية الترتيب، وهناك في الغالب n الخطوات منذ كل واحد ولكن الأخير يزيد عدد مجموعات في القسم. مثيلات مشكلة تصغير DFA التي تتسبب في سلوك أسوأ حالة هي نفسها الموجودة في خوارزمية هوبكروفت. يمكن أن يكون عدد الخطوات التي تؤديها الخوارزمية أصغر بكثير من n ، لذا في المتوسط (بالنسبة إلى s الثابت) ، يكون أدائها O(n log n) أو حتى O(n log log n) بناءً على التوزيع العشوائي على الحركة الذي تم اختياره نموذج سلوك متوسط الحالة الخوارزمية.
خوارزمية برزوزوفسكي :
وكما لاحظ برزوزوفسكي(1963)، فإن عكس حواف DFA ينتج عنه حركه غير محدد (NFA) لعكس اللغة الأصلية، وتحويل NFA إلى DFA باستخدام بنية قوة المجموعة القياسية (إنشاء حالات قابلة للوصول فقط من تحويل DFA) يؤدي إلى الحد الأدنى من DFA لنفس اللغة المعكوسة. يؤدي تكرار عملية الانعكاس هذه للمرة الثانية إلى إنشاء حد أدنى للغة DFA للغة الأصلية. يعتبر تعقيد خوارزمية برزوزوفسكي الأسوأ حالةً كبيرةً، حيث توجد لغات عادية يكون فيها DFA الأدنى من الانعكاس أكبر بشكل كبير من DFA الأدنى للغة، ولكنه عادةً ما يؤدي أفضل من هذه الحالة الأسوأ.
تصغير NFA
في حين أن الإجراءات المذكورة أعلاه تعمل على DFAs ، فإن طريقة التقسيم لا تعمل للحركات غير المحددة (NFA) على الرغم من أن البحث الشامل قد يقلل من NFA ، فلا توجد خوارزمية متعددة الحدود الزمنية لتقليل NFAs العامة إلا P = PSPACE ، وهو تخمين لم يتم حله في نظرية التعقيد الحسابي الذي يعتقد على نطاق واسع أنه غير صحيح. ومع ذلك، هناك أساليب لتقليل NFA يمكن أن تكون أكثر كفاءة من البحث عن القوة الغير واضحه.
أنظر أيضا
ترميز الحالة لقوة منخفضة.
ملاحظات
1. Hopcroft, Motwani & Ullman (2001), Section 4.4.3, "Minimization of DFA's".
2. Jump up^ Hopcroft & Ullman (1979), Section 3.4, Theorem 3.10, p. 67
3. Jump up^ Hopcroft, Motwani & Ullman (2001), Section 4.4.3, "Minimization of DFA's", p. 159, and p. 164 (remark after Theorem 4.26)
4. Jump up^ Based on Corollary 10 of Knuutila (2001)
5. Jump up^ Hopcroft (1971); Aho, Hopcroft & Ullman (1974)
6. ^ Jump up to:a b c Berstel et al. (2010).
7. Jump up^ David (2012).
8. Jump up^ For instance, the language of binary strings whose nth symbol is a one requires only n + 1 states, but its reversal requires 2n states. Leiss (1981) provides a ternary n-state DFA whose reversal requires 2n states, the maximum possible. For additional examples and the observation of the connection between these examples and the worst-case analysis of Brzozowski's algorithm, see Câmpeanu et al. (2001).
9. Jump up^ Hopcroft, Motwani & Ullman (2001), Section 4.4, Figure labeled "Minimizing the States of an NFA", p. 163.
10. Jump up^ Kameda & Weiner (1970).
المراجع
· Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), "4.13 Partitioning", The Design and Analysis of Computer Algorithms, Addison-Wesley, pp. 157–162.
· Berstel, Jean; Boasson, Luc; Carton, Olivier; Fagnot, Isabelle (2010), "Minimization of Automata", Automata: from Mathematics to Applications, European Mathematical Society, arXiv:1010.5318
· Brzozowski, J. A. (1963), "Canonical regular expressions and minimal state graphs for definite events", Proc. Sympos. Math. Theory of Automata (New York, 1962), Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y., pp. 529–561, MR 0175719.
· Câmpeanu, Cezar; Culik, Karel, II; Salomaa, Kai; Yu, Sheng (2001), "State Complexity of Basic Operations on Finite Languages", 4th International Workshop on Automata Implementation (WIA '99), Lecture Notes in Computer Science, 2214, Springer-Verlag, pp. 60–70, doi:10.1007/3-540-45526-4_6.
· David, Julien (2012), "Average complexity of Moore's and Hopcroft's algorithms", Theoretical Computer Science, 417: 50–65, doi:10.1016/j.tcs.2011.10.011.
· Hopcroft, John (1971), "An n log n algorithm for minimizing states in a finite automaton", Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971), New York: Academic Press, pp. 189–196, MR 0403320. See also preliminary version, Technical Report STAN-CS-71-190, Stanford University, Computer Science Department, January 1971.
· Hopcroft, John E.; Ullman, Jeffrey D. (1979), Introduction to Automata Theory, Languages, and Computation, Reading/MA: Addison-Wesley,
· Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001), Introduction to Automata Theory, Languages, and Computation (2nd ed.), Addison-Wesley.
· Kameda, Tsunehiko; Weiner, Peter (1970), "On the state minimization of nondeterministic finite automata", IEEE Transactions on Computers, 100 (7), doi:10.1109/T-C.1970.222994.
· Knuutila, Timo (2001), "Re-describing an algorithm by Hopcroft", Theoretical Computer Science, 250 (1-2): 333–363, doi:10.1016/S0304-3975(99)00150-4, MR 1795249.
· Leiss, Ernst (1981), "Succinct representation of regular languages by Boolean automata" (PDF), Theoretical Computer Science, 13 (3): 323–330, doi:10.1016/S0304-3975(81)80005-9, MR 0603263.
· Leiss, Ernst (1985), "Succinct representation of regular languages by Boolean automata II" (PDF), Theoretical Computer Science, 38: 133–136, doi:10.1016/0304-3975(85)90215-4
· Moore, Edward F. (1956), "Gedanken-experiments on sequential machines", Automata studies, Annals of mathematics studies, no. 34, Princeton, N. J.: Princeton University Press, pp. 129–153, MR 0078059.
· Sakarovitch, Jacques (2009), Elements of automata theory, Translated from French by Reuben Thomas, Cambridge University Press, , Zbl 1188.68177
روابط خارجية
· DFA minimization using the Myhill-Nerode theorem