नियतात्मक परिमित ऑटोमेटन

"एफएसबी" redirects here. एफएसबी may also refer to नशीली दवाओं से यौन उत्पीड़न.

एक नियतात्मक परिमित स्वचालित का उदाहरण जो केवल बाइनरी संख्याओं को स्वीकार करता है जोकी 3 के गुणज हैं। अवस्थाएँ एस₀ प्रारंभ अवस्था और स्वीकृत अवस्था दोनों है। उदाहरण के लिए, स्ट्रिंग 1001 अवस्थाएँ अनुक्रम एस की ओर ले जाती है S₀, S₁ ,S₂, S₀, S₁, और इसलिए स्वीकार किया जाता है।

गणना के सिद्धांत में, सैद्धांतिक कंप्यूटर विज्ञान की शाखा, नियतात्मक परिमित स्वचालित (डीएफए) - जिसे परिमित-अवस्थाएँ मशीन या स्वीकर्ता (पहचानकर्ता) (डीएफए), नियतात्मक परिमित-अवस्थाएँ मशीन (डीएफएसएम), या नियतात्मक परिमित- के रूप में भी जाना जाता है। अवस्थाएँ स्वचालित (डीएफएसए) - परिमित-अवस्थाएँ मशीन है जोकी स्ट्रिंग द्वारा विशिष्ट रूप से निर्धारित अवस्थाएँ अनुक्रम के माध्यम से चलकर प्रतीकों के दिए गए स्ट्रिंग (कंप्यूटर विज्ञान) को स्वीकार या अस्वीकार करती है। नियतिवादी गणना चलाने की विशिष्टता को संदर्भित करता है। और परिमित-अवस्थाएँ मशीनों को अधिकृत के लिए अधिक सरल मॉडल की खोज में, वॉरेन मैकुलोच और वाल्टर पिट्स ने 1943 में परिमित ऑटोमेटा के समान अवधारणा प्रस्तुत करने वाले प्रथम शोधकर्ताओं में से थे।

इस प्रकार से यह चित्र अवस्थाएँ आरेख का उपयोग करके नियतात्मक परिमित स्वचालित को दर्शाता है। इस उदाहरण स्वचालित में, तीन अवस्थाएँ हैं: S₀, S₁, और S₂ (मंडलियों द्वारा रेखांकन द्वारा निरूपित)। स्वचालित इनपुट के रूप में 0s और 1s का सीमित अनुक्रम लेता है। प्रत्येक अवस्थाएँ के लिए, संक्रमण तीर होता है जो 0 और 1 दोनों के लिए अगले अवस्थाएँ की ओर ले जाता है। प्रतीक को पढ़ने पर, डीएफए संक्रमण तीर का अनुसरण करके निश्चित रूप से अवस्थाएँ से दूसरे अवस्थाएँ में कूद जाता है। उदाहरण के लिए, यदि स्वचालित वर्तमान में अवस्थाएँ S₀ में है और वर्तमान इनपुट प्रतीक 1 है, तो यह निश्चित रूप से अवस्थाएँ S₁ पर पहुंच जाता है. डीएफए में प्रारंभ स्थिति होती है (कहीं से आने वाले तीर द्वारा ग्राफिक रूप से चिह्नित) जहां गणना प्रारंभ होती है, और स्वीकार्य अवस्थाएँ ों का सेट (गणित) (दोहरे सर्कल द्वारा ग्राफिक रूप से चिह्नित) होता है जो गणना सफल होने पर परिभाषित करने में सहायता करता है।

किन्तु डीएफए को अमूर्त गणितीय अवधारणा के रूप में परिभाषित किया गया है, जिससे सदैव इसे शाब्दिक विश्लेषण और पैटर्न मिलान जैसी विभिन्न विशिष्ट समस्याओं को हल करने के लिए हार्डवेयर और सॉफ्टवेयर में प्रयुक्त किया जाता है।इस प्रकार उदाहरण के लिए, डीएफए ऐसे सॉफ़्टवेयर को मॉडल कर सकता है जो यह तय करता है कि ईमेल पते जैसे ऑनलाइन उपयोगकर्ता इनपुट वाक्यात्मक रूप से मान्य हैं या नहीं है ।

अतः डीएफए को गैर-नियतात्मक परिमित ऑटोमेटा (एनएफए) के रूप में सामान्यीकृत किया गया है, जिसमें अवस्थाएँ से प्रारंभ होने वाले ही लेबल के कई तीर हो सकते हैं। पॉवरसेट निर्माण पद्धति का उपयोग करके, प्रत्येक एनएफए को डीएफए में अनुवादित किया जा सकता है जोकी समान भाषा को पहचानता है। डीएफए, और एनएफए भी, नियमित भाषाओं के सेट को बिल्कुल पहचानते हैं।

औपचारिक परिभाषा

एक नियतात्मक परिमित स्वचालित M एक 5-टपल है, (Q, Σ, δ, q₀, F), को मिलाकर

• अवस्थाएँ का सीमित सेट Q (कंप्यूटर विज्ञान)
• इनपुट प्रतीकों का सीमित सेट Σ जिसे वर्णमाला (कंप्यूटर विज्ञान) कहा जाता है
• एक संक्रमण फलन (गणित) δ : Q × Σ → Q
• एक प्रारंभिक या परिमित-अवस्था मशीन या प्रारंभ स्थिति $q_{0}\in Q$
• परिमित-अवस्था मशीन या स्वीकार .28या अंतिम.29 अवस्थाओं का सेट $F\subseteq Q$

मान लीजिए कि r₀, r₁, …, r_n अक्षर Σ के ऊपर एक स्ट्रिंग है। स्वचालित M स्ट्रिंग w को स्वीकार करता है यदि निम्न स्थितियों के साथ Q में अवस्थाएँ ों, r₀, r₁, …, r_n का अनुक्रम उपस्तिथ है:

1. r₀ = q₀
2. r_i+1 = δ(r_i, a_i+1), के लिए i = 0, …, n − 1
3. $r_{n}\in F$.

इस प्रकार से शब्दों में, प्रथम नियम कहती है कि मशीन प्रारंभ अवस्था q₀ में प्रारंभ होती है . दूसरी नियम कहती है कि स्ट्रिंग w का प्रत्येक अक्षर दिया गया है , मशीन ट्रांज़िशन फलन δ के अनुसार अवस्थाएँ से दूसरे अवस्थाएँ में स्थानांतरित होगी. अंतिम नियम कहलाता है कि मशीन w स्वीकार करती है यदि w अंतिम इनपुट मशीन को स्वीकार करने वाले अवस्थाएँ ों में से में रुकने का कारण बनता है। अन्यथा, यह कहा जाता है कि स्वचालित स्ट्रिंग को अस्वीकार कर देता है। वह तार का सेट M स्वीकार द्वारा मान्यता M प्राप्त औपचारिक भाषा है तथा इस भाषा को L(M) द्वारा निरूपित किया जाता है .

इस प्रकार से स्वीकृत अवस्थाओं के बिना और प्रारंभिक अवस्था के बिना नियतात्मक परिमित स्वचालित को संक्रमण प्रणाली या सेमीस्वचालित के रूप में जाना जाता है।

अतः औपचारिक परिभाषा के अधिक व्यापक परिचय के लिए ऑटोमेटा सिद्धांत देखें।

उदाहरण

इस प्रकार से निम्नलिखित उदाहरण DFA M, का है द्विआधारी वर्णमाला के साथ, जिसके लिए आवश्यक है कि इनपुट में 0 की सम संख्या हो।

एम के लिए अवस्थाएँ आरेख

M = (Q, Σ, δ, q₀, F) जहाँ

• Q = {S₁, S₂}
• Σ = {0, 1}
• q₀ = S₁
• F = {S₁} और
• δ को निम्नलिखित अवस्थाएँ संक्रमण तालिका द्वारा परिभाषित किया गया है:

	0	1
S1	S2	S1
S2	S1	S2

अवस्थाएँ S₁ दर्शाता है कि अब तक इनपुट में 0 की एक सम संख्या रही है, जबकि S₂ एक विषम संख्या को दर्शाता है। इनपुट में 1 स्वचालित की स्थिति को नहीं परिवर्तित होता है। जब इनपुट समाप्त हो जाता है, तो अवस्थाएँ दिखाएगा कि इनपुट में 0 की सम संख्या है या नहीं। यदि इनपुट में 0 की सम संख्या है, तो M अवस्थाएँ S₁, एक स्वीकार्य स्थिति में समाप्त हो जाएगा, इसलिए इनपुट स्ट्रिंग स्वीकार कर ली जाएगी

M द्वारा मान्यता प्राप्त भाषा नियमित अभिव्यक्ति (1*) (0 (1*) 0 (1*))*, द्वारा दी गई नियमित भाषा है, जहां * क्लेन स्टार है, उदाहरण के लिए, 1* किसी भी संख्याओं (संभवतः शून्य) को निरंतर दर्शाता है।

भिन्नताएँ

पूर्ण और अपूर्ण

इस प्रकार से उपरोक्त परिभाषा के अनुसार, नियतात्मक परिमित ऑटोमेटा सदैव पूर्ण होते हैं: वे प्रत्येक अवस्थाएँ से प्रत्येक इनपुट प्रतीक के लिए संक्रमण को परिभाषित करते हैं।

चूंकि यह अधिक सरल परिभाषा है, कुछ लेखक थोड़ी अलग धारणा के लिए नियतात्मक परिमित स्वचालित शब्द का उपयोग करते हैं: स्वचालित जोकी प्रत्येक अवस्थाएँ और प्रत्येक इनपुट प्रतीक के लिए अधिकतम संक्रमण को परिभाषित करता है; संक्रमण फलन को आंशिक फलन होने की अनुमति होती है। जब कोई संक्रमण परिभाषित नहीं होता है, तो यह स्वचालित रुक जाता है।

स्थानीय स्वचालित

एक स्थानीय स्वचालित डीएफए है, आवश्यक नहीं कि वह पूर्ण हो, जिसके लिए समान लेबल वाले सभी किनारे ही शीर्ष पर ले जाते हैं। और स्थानीय ऑटोमेटा स्थानीय भाषा (औपचारिक भाषा) के वर्ग को स्वीकार करते हैं, जिनके लिए भाषा में किसी शब्द की सदस्यता शब्द पर दो लंबाई की स्लाइडिंग विंडो द्वारा निर्धारित की जाती है।

वर्णमाला A पर माइहिल ग्राफ वर्टेक्स (ग्राफ सिद्धांत) A और प्रारंभ और समाप्ति लेबल वाले शीर्षों के उपसमुच्चय के साथ निर्देशित ग्राफ है। माइहिल ग्राफ़ द्वारा स्वीकृत भाषा प्रारंभिक शीर्ष से अंतिम शीर्ष तक निर्देशित पथों का सेट है: इस प्रकार ग्राफ़ स्वचालित के रूप में कार्य करता है। माइहिल ग्राफ़ द्वारा स्वीकृत भाषाओं का वर्ग स्थानीय भाषाओं का वर्ग है।

यादृच्छिकता

इस प्रकार से जब प्रारंभ स्थिति और स्वीकृत अवस्थाओं को तिरस्कार कर दिया जाता है, तो n अवस्थाओं का डीएफए और k आकार के वर्णमाला को n शीर्षों के एक डिग्राफ के रूप में देखा जा सकता है, जिसमें सभी शीर्षों पर kआउट-आर्क्स 1, …, k (a k-आउट) लेबल होते हैं डिग्राफ)। यह ज्ञात है कि जब k ≥ 2 एक निश्चित पूर्णांक होता है, तो उच्च संभावना के साथ, यादृच्छिक रूप से समान रूप से चुने गए ऐसे k-आउट डायग्राफ में सबसे उच्च कठोरता से जुड़ा घटक (एससीसी) रैखिक आकार का होता है और इसे सभी शीर्षों द्वारा पहुंचा जा सकता है। यह भी सिद्ध हो चुका है कि यदि n के बढ़ने पर k को बढ़ने की अनुमति दी जाती है, तो पूर्ण डायग्राफ में कनेक्टिविटी के लिए एर्डोस-रेनी मॉडल के समान कठोर कनेक्टिविटी के लिए एक चरण संक्रमण होता है।

किन्तु यादृच्छिक डीएफए में, शीर्ष से पहुंचने योग्य शीर्षों की अधिकतम संख्या उच्च संभावना वाले अधिक उच्च दृढ़ता से जुड़े घटक में शीर्षों की संख्या के अधिक समीप है। यह ग्राफ़ सिद्धांत की अधिक उच्च शब्दावली के लिए भी सत्य होते है या सबग्राफ न्यूनतम इन-डिग्री के प्रेरित उप-डिग्राफ, जिसे डिजेनरेसी (ग्राफ सिद्धांत) या 1-मुख्य कोर-के निर्देशित संस्करण के रूप में देखा जा सकता है।।

समापन गुण

ऊपरी बायां स्वचालित 00 की कम से कम घटना वाले सभी बाइनरी स्ट्रिंग्स की भाषा को पहचानता है। निचला दायां स्वचालित 1 की सम संख्या वाली सभी बाइनरी स्ट्रिंग्स को पहचानता है। निचले बाएँ स्वचालित को पूर्व दो के उत्पाद के रूप में प्राप्त किया जाता है, यह दोनों भाषाओं के प्रतिच्छेदन को पहचानता है।

यदि डीएफए उन भाषाओं को पहचानते हैं जो डीएफए पहचानने योग्य भाषाओं पर एक ऑपरेशन प्रयुक्त करके प्राप्त की जाती हैं तो डीएफए को ऑपरेशन के तहत बंद कर दिया जाता है। डीएफए निम्नलिखित परिचालनों के तहत बंद किए गए हैं।

• यूनियन
• इंटरसेक्शन
• संयोजन
• पूरक
• क्लीन क्लोजर
• व्युत्क्रम
• भागफल
• प्रतिस्थापन
• समरूपता

प्रत्येक ऑपरेशन के लिए, अवस्थाएँ जटिलता अनुसंधान में अवस्थाएँ की संख्या के संबंध में इष्टतम निर्माण निर्धारित किया गया है।

चूंकि डीएफए गैर-नियतात्मक परिमित स्वचालित (एनएफए) के लिए पावरसेट निर्माण हैं, इसलिए इन क्लोजर को एनएफए के क्लोजर गुणों का उपयोग करके भी प्रमाणित किया जा सकता है।

संक्रमण मोनोइड के रूप में

इस प्रकार से किसी दिए गए डीएफए के रन को स्वयं के साथ संक्रमण फलन के अधिक ही सामान्य सूत्रीकरण की रचनाओं के अनुक्रम के रूप में देखा जा सकता है। यहां हम उस फलन का निर्माण करते हैं।

किसी दिए गए इनपुट प्रतीक $a\in \Sigma$ के लिए कोई भी सभी $q\in Q$ के लिए $\delta _{a}(q)=\delta (q,a)$ को परिभाषित करके एक संक्रमण फलन $\delta _{a}:Q\rightarrow Q$ का निर्माण कर सकता है (इस ट्रिक को करीइंग कहा जाता है।) इस परिप्रेक्ष्य से $\delta _{a}$ दूसरे अवस्थाएँ को प्राप्त करने के लिए Q में एक अवस्थाएँ पर "कार्य" करता है। इसके पश्चात कोई अन्य स्थिति प्राप्त करने के लिए Q में एक स्थिति पर विभिन्न फलन $\delta _{a}$$\delta _{b}$ "कार्य" पर बार-बार प्रयुक्त फलन संरचना के परिणाम पर विचार कर सकता है। फिर कोई व्यक्ति विभिन्न फलन $a,b\in \Sigma$ पर बार-बार प्रयुक्त किए गए फलन संरचना के परिणाम पर विचार कर सकता है, कोई एक नए फलन ${\widehat {\delta }}_{ab}=\delta _{a}\circ \delta _{b}$ को परिभाषित कर सकता है जहां $\circ$ फलन संरचना को दर्शाता है।

अतः स्पष्ट रूप से, इस प्रक्रिया को निम्नलिखित पुनरावर्ती परिभाषा देते हुए पुनरावर्ती रूप से प्रवाहित रखा जा सकता है ${\widehat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q$:

${\widehat {\delta }}(q,\epsilon )=q$, जहाँ $\epsilon$ खाली स्ट्रिंग है और

${\widehat {\delta }}(q,wa)=\delta _{a}({\widehat {\delta }}(q,w))$, जहाँ $w\in \Sigma ^{*},a\in \Sigma$ और $q\in Q$.

${\widehat {\delta }}$ सभी शब्दों के लिए परिभाषित है $w\in \Sigma ^{*}$. डीएफए का रन रचनाओं का क्रम है ${\widehat {\delta }}$ खुद के साथ.

निरंतर फलन संरचना एक मोनॉइड बनाती है। संक्रमण कार्यों के लिए, इस मोनोइड को संक्रमण मोनोइड, या कभी-कभी परिवर्तन अर्धसमूह के रूप में जाना जाता है। निर्माण को उलटा भी किया जा सकता है: $\delta$ दिए जाने पर कोई ${\widehat {\delta }}$, का पुनर्निर्माण कर सकता है और इसलिए दोनों विवरण समतुल्य होते हैं।

लाभ और हानि

डीएफए गणना के अधिक व्यावहारिक मॉडलों में से है, क्योंकि इनपुट की धारा पर डीएफए अनुकरण करने के लिए तुच्छ रैखिक समय, निरंतर-स्थान, ऑनलाइन एल्गोरिदम है। इसके अतिरिक्त , डीएफए को पहचानने के लिए कुशल एल्गोरिदम भी होते हैं:

• किसी दिए गए डीएफए द्वारा मान्यता प्राप्त भाषा का पूरक।
• दो दिए गए डीएफए द्वारा मान्यता प्राप्त भाषाओं का मिलन/प्रतिच्छेदन।

चूँकि डीएफए को विहित रूप (डीएफए न्यूनतमकरण) में घटाया जा सकता है, यह निर्धारित करने के लिए कुशल एल्गोरिदम भी हैं:

• क्या डीएफए किसी स्ट्रिंग को स्वीकार करता है (खालीपन समस्या)
• क्या डीएफए सभी स्ट्रिंग्स को स्वीकार करता है (सार्वभौमिकता समस्या)
• क्या दो डीएफए ही भाषा को पहचानते हैं (समानता समस्या)
• क्या डीएफए द्वारा मान्यता प्राप्त भाषा दूसरे डीएफए द्वारा मान्यता प्राप्त भाषा में सम्मिलित होते है (समावेशन समस्या)
• किसी विशेष नियमित भाषा के लिए न्यूनतम संख्या में अवस्थाएँ ों वाला डीएफए (न्यूनीकरण समस्या)

इस प्रकार से डीएफए गैर-नियतात्मक परिमित ऑटोमेटा (एनएफए) की कंप्यूटिंग पॉवर के समान हैं। ऐसा इसलिए है, क्योंकि सबसे प्रथम कोई भी डीएफए भी एनएफए है, इसलिए एनएफए वही कर सकता है जोकी डीएफए कर सकता है। इसके अतिरिक्त , एनएफए दिए जाने पर, पावरसेट निर्माण का उपयोग करके कोई डीएफए बना सकता है जो एनएफए के समान भाषा को पहचानता है, चूंकि डीएफए में एनएफए की तुलना में तीव्र से उच्च संख्या में अवस्थाएँ हो सकते हैं। चूंकि , भले ही एनएफए कम्प्यूटेशनल रूप से डीएफए के समान होते हैं, जिससे एनएफए के लिए भी उपर्युक्त समस्याओं को कुशलतापूर्वक हल नहीं किया जा सकता है।और एनएफए के लिए गैर-सार्वभौमिकता समस्या पीएसपीएसीई पूर्ण माने जाते है क्योंकि घातीय आकार में अधिक कम अस्वीकार करने वाले शब्द वाले छोटे एनएफए हैं। डीएफए सार्वभौमिक है यदि और केवल तभी जब सभी अवस्थाएँ अंतिम अवस्थाएँ हों, जिससे यह एनएफए के लिए प्रयुक्त नहीं होता है। समानता, समावेशन और न्यूनतमकरण की समस्याएं भी पीस्पेस पूर्ण हैं क्योंकि उन्हें एनएफए के पूरक बनाने की आवश्यकता होती है जिसके परिणामस्वरूप आकार में तीव्र से वृद्धि होती है।

जिससे दूसरी ओर, परिमित-अवस्थाएँ ऑटोमेटा उन भाषाओं में सख्ती से सीमित पॉवर के होते हैं जिन्हें वे पहचान सकते हैं; कई सरल भाषाएँ, जिनमें कोई भी समस्या सम्मिलित होती है जिसे हल करने के लिए निरंतर स्थान से अधिक की आवश्यकता होती है, को डीएफए द्वारा पहचाना नहीं जा सकता है। सरल रूप से वर्णित भाषा का उत्कृष्ट उदाहरण जिसे कोई भी डीएफए नहीं पहचान सकता, वह ब्रैकेट या डाइक भाषा है, अर्थात , वह भाषा जिसमें शब्द "(()())" जैसे उचित रूप से युग्मित ब्रैकेट होते हैं। सहज रूप से, कोई भी डीएफए डाइक भाषा को नहीं पहचान सकता क्योंकि डीएफए गिनती करने में सक्षम नहीं हैं: डीएफए-जैसे स्वचालित को वर्तमान में विवृत कोष्ठकों की किसी भी संभावित संख्या का प्रतिनिधित्व करने के लिए अवस्थाएँ की आवश्यकता होती है, जिसका अर्थ है कि इसे असीमित संख्या में अवस्थाएँ ों की आवश्यकता होगी। और इस प्रकार से सरल उदाहरण वह भाषा है जिसमें a की कुछ सीमित लेकिन मनमानी संख्या के लिए aⁿbⁿ रूप की स्ट्रिंग्स शामिल होती हैं, जिसके बाद b की समान संख्या होती है।।

लेबल किए गए शब्दों से डीएफए की पहचान

Main article: नियमित भाषाओं का प्रेरण

सकारात्मक शब्दों का सेट $S^{+}\subset \Sigma ^{*}$ दिया गया और नकारात्मक शब्दों का सेट $S^{-}\subset \Sigma ^{*}$ कोई ऐसा डीएफए बना सकता है जो $S^{+}$सभी शब्दों को स्वीकार करता हो और $S^{-}$सभी शब्दों को अस्वीकार करता है : इस समस्या को डीएफए पहचान (संश्लेषण, सीखना) कहा जाता है।

जबकि कुछ डीएफए का निर्माण रैखिक समय में किया जा सकता है, अवस्थाएँ ों की न्यूनतम संख्या के साथ डीएफए की पहचान करने की समस्या एनपी-पूर्ण है।

न्यूनतम डीएफए पहचान के लिए पहला एल्गोरिदम ट्रैखटेनब्रॉट और बार्ज़डिन द्वारा प्रस्तावित किया गया है और इसे टीबी-एल्गोरिदम कहा जाता है।

चूंकि , टीबी-एल्गोरिदम मानता है कि सभी शब्द $\Sigma$ किसी दी गई लंबाई तक दोनों में समाहित $S^{+}\cup S^{-}$हैं .

तत्पश्चात , के. लैंग ने टीबी-एल्गोरिदम का विस्तार प्रस्तावित किया जिसके बारे में किसी भी धारणा का उपयोग नहीं किया जाता है $S^{+}$ और $S^{-}$, ट्रैक्सबार एल्गोरिदम।

चूंकि , ट्रैक्सबार निर्मित डीएफए की न्यूनतमता का प्रमाण नहीं देता है।

इस प्रकार से ई.एम. गोल्ड ने न्यूनतम डीएफए पहचान के लिए अनुमानी एल्गोरिदम का भी प्रस्ताव रखा।

गोल्ड का एल्गोरिदम यह मानता है $S^{+}$ और $S^{-}$ नियमित भाषा का विशिष्ट सेट सम्मिलित करें; अन्यथा, निर्मित डीएफए असंगत होगा $S^{+}$ या $S^{-}$.

अन्य उल्लेखनीय डीएफए पहचान एल्गोरिदम में आरपीएनआई एल्गोरिदम सम्मिलित है, ब्लू-फ्रिंज साक्ष्य-संचालित अवस्थाएँ -विलय एल्गोरिदम, और विंडोड-ईडीएसएम।

एक अन्य शोध दिशा विकासवादी एल्गोरिदम का अनुप्रयोग है: स्मार्ट अवस्थाएँ लेबलिंग विकासवादी एल्गोरिदम संशोधित डीएफए पहचान समस्या को हल करने की अनुमति दी गई है जिसमें प्रशिक्षण डेटा (सेट)। $S^{+}$ और $S^{-}$) इस अर्थ में ध्वनि है कि कुछ शब्दों को गलत वर्गों के लिए उत्तरदायी ठहराया गया है।

तत्पश्चात और कदम मैरिजन ह्यूले मार्जिन जे.एच. ह्यूले और एस. वर्वर द्वारा बूलियन संतुष्टि समस्या समाधानकर्ताओं के अनुप्रयोग के कारण है: न्यूनतम डीएफए पहचान समस्या बूलियन सूत्र की संतुष्टि का निर्णय लेने के लिए कम हो गई है। मुख्य विचार इनपुट सेट के आधार पर संवर्धित उपसर्ग-वृक्ष स्वीकर्ता (एक प्रयास जिसमें सभी इनपुट शब्द संबंधित लेबल के साथ सम्मिलित हैं) का निर्माण करना और डीएफए खोजने की समस्या को कम करना है। $C$ पेड़ के शीर्षों को रंगने के लिए कहा गया है $C$ इस तरह से बताता है कि जब रंग वाले शीर्षों को अवस्थाएँ में विलय कर दिया जाता है, तो उत्पन्न स्वचालित नियतात्मक होता है और इसका अनुपालन करता है $S^{+}$ और $S^{-}$ प्रयास किया.

यद्यपि यह दृष्टिकोण न्यूनतम डीएफए खोजने की अनुमति देता है, जिससे इनपुट डेटा का आकार बढ़ने पर यह निष्पादन समय के तीव्र से बढ़ने से ग्रस्त होता है।

इसलिए, ह्यूले और वेरवर के प्रारंभिक एल्गोरिदम को बाद में एसएटी सॉल्वर निष्पादन से प्रथम ईडीएसएम एल्गोरिदम के कई चरण बनाने के साथ संवर्धित किया गया है: डीएफए एसएटी एल्गोरिदम।

इससे समस्या के खोज स्थान को कम करने की अनुमति मिलती है, जिससे न्यूनतम आश्वासन की हानि होता है।

खोज स्थान को कम करने का और विधि उलियंटसेव एट अल द्वारा प्रस्तावित किया गया है। चौड़ाई-प्रथम खोज एल्गोरिदम के आधार पर नई समरूपता तोड़ने वाले विधेय के माध्यम से:

इस प्रकार से माने गए डीएफए के अवस्थाएँ ों को प्रारंभिक अवस्थाएँ से लॉन्च किए गए बीएफएस एल्गोरिदम के अनुसार क्रमांकित करने के लिए बाध्य किया गया है। यह दृष्टिकोण खोज स्थान को $C!$ कम कर देता है आइसोमोर्फिक ऑटोमेटा को समाप्त कर देता है ।

समतुल्य मॉडल

केवल पढ़ने के लिए दाहिनी ओर चलने वाली ट्यूरिंग मशीन

रीड-ओनली राइट-मूविंग ट्यूरिंग मशीनें विशेष प्रकार की ट्यूरिंग मशीन हैं जो केवल राइट-मूविंग होती हैं; इन

लगभग बिल्कुल डीएफए के समतुल्य हैं।

एकल अनंत टेप पर आधारित परिभाषा 7- टपल है

$M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle ,$

जहाँ

$Q$ अवस्थाएँ ों का सीमित समूह है;

$\Gamma$ टेप वर्णमाला/प्रतीकों का सीमित सेट है;

$b\in \Gamma$ रिक्त प्रतीक है (गणना के दौरान किसी भी चरण में टेप पर अनंत बार आने वाला एकमात्र प्रतीक);

$\Sigma$, का उपसमुच्चय $\Gamma$ b सम्मिलित नहीं है, इनपुट प्रतीकों का सेट है;

$\delta :Q\times \Gamma \to Q\times \Gamma \times \{R\}$ फलन (गणित) है जिसे अवस्थाएँ संक्रमण प्रणाली कहा जाता है, R सही आंदोलन (एक सही परिवर्तन) है;

$q_{0}\in Q$ प्रारंभिक अवस्था है;

$F\subseteq Q$ अंतिम या स्वीकृत अवस्थाओं का समूह है।

इस प्रकार से मशीन सदैव नियमित भाषा स्वीकार करती है। सेट F का कम से कम तत्व उपस्तिथ होना चाहिए (एक हॉल्ट स्थिति) भाषा के गैर-रिक्त होने के लिए।

3-अवस्था, 2-प्रतीक रीड-ओनली ट्यूरिंग मशीन का उदाहरण

	Current state A			Current state B			Current state C
टेप प्रतीक	प्रतीक लिखें	टेप ले जाएँ	अगला अवस्थाएँ	प्रतीक लिखें	टेप ले जाएँ	अगला अवस्थाएँ	प्रतीक लिखें	टेप ले जाएँ	अगला अवस्थाएँ
0	1	R	B	1	R	A	1	R	B
1	1	R	C	1	R	B	1	N	HALT

$Q=\{A,B,C,{\text{HALT}}\};$

$\Gamma =\{0,1\};$

$b=0$, खाली ;

$\Sigma =\varnothing$, खाली सेट;

$\delta =$ ऊपर अवस्थाएँ -तालिका देखें;

$q_{0}=A$, आरंभिक अवस्थाएँ ;

$F=$ अंतिम अवस्थाओं का तत्व सेट: $\{{\text{HALT}}\}$.

यह भी देखें

• नियतात्मक चक्रीय परिमित अवस्था स्वचालन
• डीएफए न्यूनीकरण
• मोनाडिक दूसरे क्रम का तर्क
• पॉवरसेट निर्माण
• क्वांटम परिमित स्वचालित
• शब्दों को अलग करने की समस्या
• ट्यूरिंग मशीन
• दो-तरफा परिमित स्वचालित
• भारित स्वचालित

संदर्भ

• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Introduction to Automata Theory, Languages, and Computation (2 ed.). Addison Wesley. ISBN 0-201-44124-1. Retrieved 19 November 2012.
• Lawson, Mark V. (2004). Finite automata. Chapman and Hall/CRC. ISBN 1-58488-255-7. Zbl 1086.68074.
• McCulloch, W. S.; Pitts, W. (1943). "A Logical Calculus of the Ideas Immanent in Nervous Activity". Bulletin of Mathematical Biophysics. 5 (4): 115–133. doi:10.1007/BF02478259. PMID 2185863.
• Rabin, M. O.; Scott, D. (1959). "Finite automata and their decision problems". IBM J. Res. Dev. 3 (2): 114–125. doi:10.1147/rd.32.0114.
• Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177.
• Sipser, Michael (1997). Introduction to the Theory of Computation. Boston: PWS. ISBN 0-534-94728-X.. Section 1.1: Finite Automata, pp. 31–47. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp. 152–155.4.4 डीएफए can accept only regular language