| dbo:abstract
|
- في نظرية احركه (فرع علوم الكمبيوتر) إن تقليل حتميه محدده الحركة إلى الحد الأدنى هو مهمة تحويل حتميه محدده الحرك ة(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 يمكن أن تكون أكثر كفاءة من البحث عن القوة الغير واضحه. (ar)
- In automata theory (a branch of theoretical computer science), DFA minimization is the task of transforming a given deterministic finite automaton (DFA) into an equivalent DFA that has a minimum number of states. Here, two DFAs are called equivalent if they recognize the same regular language. Several different algorithms accomplishing this task are known and described in standard textbooks on automata theory. (en)
- En informatique théorique, et plus particulièrement en théorie des automates, la minimisation d'un automate fini déterministe est l'opération qui consiste à transformer un automate fini déterministe donné en un automate fini déterministe ayant le nombre minimal d'états et qui reconnaît le même langage rationnel. La minimisation a une importance pratique évidente par le gain d'espace qu'elle permet. Il existe plusieurs algorithmes pour effectuer cette opération de minimisation ; les plus usuels sont décrits pour la plupart dans les manuels traitant de théorie des automates. Les algorithmes généraux les plus connus - nommés d'après leurs inventeurs - sont l'algorithme de Brzozowski, l'algorithme de Moore, et l'algorithme de Hopcroft. D'autres algorithmes spécifiques existent, par exemple pour la minimisation d'automates reconnaissant des ensembles finis de mots, comme l'algorithme de Revuz et ses variantes. Les algorithmes ont aussi été étendus à des cas plus généraux, comme les automates avec sortie (automate de Moore, automate de Mealy) ou les transducteurs finis. Il n'existe pas de procédé analogue pour la minimisation d'automates plus généraux, comme les automates à pile ou les automates linéairement bornés. Une application importante de la minimisation des automates finis déterministes est le test de l'équivalence de deux automates finis, c'est-à-dire le fait de décider s'ils reconnaissent le même langage. C'est une conséquence de l'unicité de l'automate fini minimal, à un renommage des états près. Pour répondre à la question, il suffit de minimiser les deux automates et de tester si leurs versions minimales sont égales. Étant donné l'importance de la minimisation, cette opération fait partie de la plupart des logiciels de manipulation d'automates. (fr)
- In Teoria degli automi (branca dell'Informatica) è detto minimizzazione di un DFA il procedimento che trasforma un dato automa a stati finiti deterministico (in breve DFA) nel DFA equivalente che ha il minor numero di stati. Due DFA sono detti equivalenti se riconoscono lo stesso linguaggio formale. Ci sono diversi algoritmi che producono il minimo DFA partendo da uno dato, con diversi metodi e complessità. (it)
- Em ciência da computação, mais especificamente no ramo da teoria dos autômatos, Minimização de AFD é o processo de transformação de um dado autômato finito determinístico (AFD) em outro equivalente que tenha um número mínimo de estados. Aqui, dois AFDs são ditos equivalentes se eles descrevem a mesma linguagem regular. Vários algoritmos diferentes que realizam essa tarefa estão descritos em livros-texto padrões que abordam a teoria dos autômatos. (pt)
- Минимизация ДКА — построение по детерминированному конечному автомату (ДКА) эквивалентного ДКА, имеющего наименьшее возможное число состояний. (ru)
- В інформатиці, чи якщо точніше в теорії автоматів, мінімізація ДСкА — це задача перетворення даного детермінованого скінченного автомата (ДСкА) в еквівалентний ДСкА який має мінімальне число станів. Два ДСкА називаються еквівалентними, якщо вони описують одну і ту ж регулярну мову. Існує кілька різних алгоритмів розв'язання цієї задачі, які описуються в підручниках теорії автоматів. (uk)
- 在自动机理论（计算机科学的一个分支）中，确定有限状态自动机最小化是将给定的确定有限状态自动机（DFA, Deterministic Finite Automaton）改造为等价且拥有最少状态的DFA的过程。这里，两个DFA等价意味着他们识别相同的正则语言。各自动机理论的教材中，已经给出了若干已知的最小化算法。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 23522 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:authorlink
| |
| dbp:first
| |
| dbp:last
| |
| dbp:wikiPageUsesTemplate
| |
| dbp:year
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- In automata theory (a branch of theoretical computer science), DFA minimization is the task of transforming a given deterministic finite automaton (DFA) into an equivalent DFA that has a minimum number of states. Here, two DFAs are called equivalent if they recognize the same regular language. Several different algorithms accomplishing this task are known and described in standard textbooks on automata theory. (en)
- In Teoria degli automi (branca dell'Informatica) è detto minimizzazione di un DFA il procedimento che trasforma un dato automa a stati finiti deterministico (in breve DFA) nel DFA equivalente che ha il minor numero di stati. Due DFA sono detti equivalenti se riconoscono lo stesso linguaggio formale. Ci sono diversi algoritmi che producono il minimo DFA partendo da uno dato, con diversi metodi e complessità. (it)
- Em ciência da computação, mais especificamente no ramo da teoria dos autômatos, Minimização de AFD é o processo de transformação de um dado autômato finito determinístico (AFD) em outro equivalente que tenha um número mínimo de estados. Aqui, dois AFDs são ditos equivalentes se eles descrevem a mesma linguagem regular. Vários algoritmos diferentes que realizam essa tarefa estão descritos em livros-texto padrões que abordam a teoria dos autômatos. (pt)
- Минимизация ДКА — построение по детерминированному конечному автомату (ДКА) эквивалентного ДКА, имеющего наименьшее возможное число состояний. (ru)
- В інформатиці, чи якщо точніше в теорії автоматів, мінімізація ДСкА — це задача перетворення даного детермінованого скінченного автомата (ДСкА) в еквівалентний ДСкА який має мінімальне число станів. Два ДСкА називаються еквівалентними, якщо вони описують одну і ту ж регулярну мову. Існує кілька різних алгоритмів розв'язання цієї задачі, які описуються в підручниках теорії автоматів. (uk)
- 在自动机理论（计算机科学的一个分支）中，确定有限状态自动机最小化是将给定的确定有限状态自动机（DFA, Deterministic Finite Automaton）改造为等价且拥有最少状态的DFA的过程。这里，两个DFA等价意味着他们识别相同的正则语言。各自动机理论的教材中，已经给出了若干已知的最小化算法。 (zh)
- في نظرية احركه (فرع علوم الكمبيوتر) إن تقليل حتميه محدده الحركة إلى الحد الأدنى هو مهمة تحويل حتميه محدده الحرك ة(DFA) إلى حتميه محدده الحركة مكافئ يحتوي على عدد أدنى من الحالات. هنا، يُطلق على اثنين من DFAs اسمًا مكافئًا في حالة تعرفهما على اللغة العادية نفسها. العديد من الخوارزميات المختلفة التي تحقق هذه المهمة معروفة وموصوفة في كتب قياسية حول نظرية الروتين. تصغير DFA لكل لغة عادية، يوجد أيضًا عدد قليل من الحركات يقبل ذلك، أي، DFA مع عدد أدنى من الحالات وهذا DFA فريد (باستثناء أنه يمكن إعطاء أسماء مختلفة). يضمن الحد الأدنى DFA الحد الأدنى من التكلفة الحسابية للمهام مثل مطابقة الأنماط. (ar)
- En informatique théorique, et plus particulièrement en théorie des automates, la minimisation d'un automate fini déterministe est l'opération qui consiste à transformer un automate fini déterministe donné en un automate fini déterministe ayant le nombre minimal d'états et qui reconnaît le même langage rationnel. La minimisation a une importance pratique évidente par le gain d'espace qu'elle permet. Il existe plusieurs algorithmes pour effectuer cette opération de minimisation ; les plus usuels sont décrits pour la plupart dans les manuels traitant de théorie des automates. (fr)
|
| rdfs:label
|
- تصغير DFA (ar)
- DFA minimization (en)
- Minimizzazione di DFA (it)
- Minimisation d'un automate fini déterministe (fr)
- Minimização de AFD (pt)
- Минимизация ДКА (ru)
- 确定有限状态自动机最小化 (zh)
- Мінімізація ДСкА (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is foaf:primaryTopic
of | |
