DFA minimization (original) (raw)
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.
| Property | Value | |
|---|---|---|
| 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 | <= |
| dbo:thumbnail | wiki-commons:Special:FilePath/DFA_to_be_minimized.jpg?width=300 | |
| dbo:wikiPageExternalLink | http://i.stanford.edu/pub/cstr/reports/cs/tr/71/190/CS-TR-71-190.pdf https://web.archive.org/web/20150621004621/http:/www8.cs.umu.se/kurser/TDBC92/VT06/final/1.pdf https://archive.org/details/introductiontoau00hopc | |
| dbo:wikiPageID | 17447039 (xsd:integer) | |
| dbo:wikiPageLength | 23522 (xsd:nonNegativeInteger) | |
| dbo:wikiPageRevisionID | 1118660704 (xsd:integer) | |
| dbo:wikiPageWikiLink | dbr:Cambridge_University_Press dbr:Powerset_construction dbr:Probability_distribution dbr:Myhill–Nerode_theorem dbr:Non-deterministic_finite_automaton dbr:Deterministic_finite_automaton dbr:State_encoding_for_low_power dbr:Equivalence_class dbr:Computational_complexity_theory dbr:P_(complexity) dbr:Theoretical_Computer_Science_(journal) dbr:Theoretical_computer_science dbc:Articles_with_example_pseudocode dbc:Finite_automata dbr:Partition_of_a_set dbr:Partition_refinement dbr:Regular_language dbr:Automata_theory dbr:Average-case_complexity dbr:Radix_sort dbr:Pattern_matching dbr:European_Mathematical_Society dbr:NFA_minimization dbr:Pseudocode dbr:Worst_case dbr:PSPACE_(complexity) dbr:Polynomial-time_algorithm dbr:File:DFA_to_be_minimized.jpg dbr:File:Minimized_DFA.jpg | |
| dbp:authorlink | Edward F. Moore (en) | |
| dbp:first | Edward F. (en) | |
| dbp:last | Moore (en) | |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Main dbt:Math dbt:Mvar dbt:Reflist dbt:Sfnp dbt:Unsourced_section dbt:Harvs | |
| dbp:year | 1956 (xsd:integer) | |
| dcterms:subject | dbc:Articles_with_example_pseudocode dbc:Finite_automata | |
| gold:hypernym | dbr:Task | |
| rdf:type | dbo:Agent | |
| 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 | freebase:DFA minimization yago-res:DFA minimization wikidata:DFA minimization dbpedia-ar:DFA minimization dbpedia-fa:DFA minimization dbpedia-fr:DFA minimization dbpedia-it:DFA minimization dbpedia-pt:DFA minimization dbpedia-ru:DFA minimization dbpedia-sr:DFA minimization dbpedia-uk:DFA minimization dbpedia-zh:DFA minimization https://global.dbpedia.org/id/4j3qW | |
| prov:wasDerivedFrom | wikipedia-en:DFA_minimization?oldid=1118660704&ns=0 | |
| foaf:depiction | wiki-commons:Special:FilePath/DFA_to_be_minimized.jpg wiki-commons:Special:FilePath/Minimized_DFA.jpg | |
| foaf:isPrimaryTopicOf | wikipedia-en:DFA_minimization | |
| is dbo:wikiPageRedirects of | dbr:Dfa_minimization dbr:Automaton_minimization dbr:Minimal_automaton dbr:Minimal_deterministic_finite_state_machine dbr:Finite_state_machine_minimization dbr:Minimal_DFA dbr:Minimized_dfa dbr:Minimizing_deterministic_finite_automaton | |
| is dbo:wikiPageWikiLink of | dbr:Powerset_construction dbr:List_of_algorithms dbr:Deterministic_finite_automaton dbr:Aperiodic_finite_state_automaton dbr:Deterministic_acyclic_finite_state_automaton dbr:Timeline_of_Polish_science_and_technology dbr:State_encoding_for_low_power dbr:Glushkov's_construction_algorithm dbr:Thompson's_construction dbr:Suffix_automaton dbr:Dfa_minimization dbr:Tagged_Deterministic_Finite_Automaton dbr:McNaughton's_theorem dbr:Partition_refinement dbr:Regular_language dbr:Janusz_Brzozowski_(computer_scientist) dbr:Automata_theory dbr:Re2c dbr:Finite-state_machine dbr:NFA_minimization dbr:Automaton_minimization dbr:Minimal_automaton dbr:Minimal_deterministic_finite_state_machine dbr:Finite_state_machine_minimization dbr:Minimal_DFA dbr:Minimized_dfa dbr:Minimizing_deterministic_finite_automaton | |
| is dbp:knownFor of | dbr:Janusz_Brzozowski_(computer_scientist) | |
| is foaf:primaryTopic of | wikipedia-en:DFA_minimization |
