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

NDFA में, एक विशेष इनपुट प्रतीक के लिए, मशीन मशीन में राज्यों के किसी भी संयोजन को स्थानांतरित कर सकती है। दूसरे शब्दों में, मशीन ले जाने के लिए सटीक स्थिति निर्धारित नहीं की जा सकती। इसलिए, इसे कहा जाता हैNon-deterministic Automaton। जैसा कि इसमें राज्यों की सीमित संख्या है, मशीन कहा जाता हैNon-deterministic Finite Machine या Non-deterministic Finite Automaton।

एक NDFA की औपचारिक परिभाषा

एक एनडीएफए का प्रतिनिधित्व 5-ट्यूपल (क्यू, represented, represented, q ₀ , F) द्वारा किया जा सकता है , जहां -

Q राज्यों का एक समुच्चय है।
∑ प्रतीकों का एक छोटा सेट है जिसे अक्षर कहा जाता है।
δसंक्रमण समारोह है जहां δ: Q × Q → 2 ^Q

(यहां क्यू (2 ^क्यू ) का पावर सेट लिया गया है क्योंकि एनडीएफए के मामले में, एक राज्य से, क्यू राज्यों के किसी भी संयोजन में संक्रमण हो सकता है)
q₀वह प्रारंभिक अवस्था है जहां से किसी भी इनपुट को संसाधित किया जाता है (q ₀ ) Q)।
F अंतिम स्थिति / Q (F। Q) के राज्यों का एक समूह है।

एक NDFA का चित्रमय प्रतिनिधित्व: (DFA के समान)

एनडीएफए को राज्य आरेख नामक डिग्राफ द्वारा दर्शाया जाता है।

कोने राज्यों का प्रतिनिधित्व करते हैं।
इनपुट वर्णमाला के साथ लेबल किए गए आर्क्स संक्रमण दिखाते हैं।
प्रारंभिक अवस्था को एक खाली आवक चाप द्वारा निरूपित किया जाता है।
अंतिम अवस्था को दोहरे वृत्तों द्वारा इंगित किया जाता है।

Example

एक गैर-नियतात्मक परिमित ऑटोमेटन होने दें →

क्यू = {ए, बी, सी}
, = {0, 1}
q ₀ = {a}
F = {c}

संक्रमण फ़ंक्शन δ जैसा कि नीचे दिखाया गया है -

वर्तमान स्थिति	इनपुट के लिए अगला राज्य 0	इनपुट के लिए अगला राज्य 1
ए	ए, बी	ख
ख	सी	एसी
सी	बी, सी	सी

इसका ग्राफिकल प्रतिनिधित्व इस प्रकार होगा -

DFA बनाम NDFA

निम्न तालिका डीएफए और एनडीएफए के बीच अंतर को सूचीबद्ध करती है।

DFA	NDFA
एक राज्य से संक्रमण प्रत्येक इनपुट प्रतीक के लिए एक विशेष अगले राज्य के लिए है। इसलिए इसे नियतात्मक कहा जाता है ।	प्रत्येक इनपुट प्रतीक के लिए एक राज्य से संक्रमण कई अगले राज्यों में हो सकता है। इसलिए इसे गैर-नियतात्मक कहा जाता है ।
डीएफए में खाली स्ट्रिंग संक्रमण नहीं देखा जाता है।	NDFA खाली स्ट्रिंग संक्रमण की अनुमति देता है।
डीएफए में बैकट्रैकिंग की अनुमति है	NDFA में, बैकट्रैकिंग हमेशा संभव नहीं होता है।
अधिक स्थान की आवश्यकता है।	कम जगह चाहिए।
एक स्ट्रिंग को डीएफए द्वारा स्वीकार किया जाता है, अगर यह एक अंतिम स्थिति में स्थानांतरित होता है।	एक स्ट्रिंग एक NDFA द्वारा स्वीकार की जाती है, यदि अंतिम अवस्था में सभी संभावित संक्रमणों में से कम से कम एक समाप्त हो जाती है।

स्वीकर्ता, क्लासिफायर और ट्रांसड्यूसर

स्वीकर्ता (पहचानकर्ता)

एक ऑटोमेटन जो एक बूलियन फ़ंक्शन की गणना करता है, एक कहा जाता है acceptor। एक स्वीकर्ता के सभी राज्य या तो दिए गए इनपुट को स्वीकार या अस्वीकार कर रहे हैं।

वर्गीकरणकर्ता

ए classifier दो से अधिक अंतिम अवस्थाएं हैं और यह समाप्त होने पर एकल आउटपुट देता है।

ट्रांसड्यूसर

एक ऑटोमेटन जो वर्तमान इनपुट और / या पिछली स्थिति के आधार पर आउटपुट उत्पन्न करता है, a कहलाता है transducer। ट्रांसड्यूसर दो प्रकार के हो सकते हैं -

Mealy Machine - आउटपुट वर्तमान स्थिति और वर्तमान इनपुट दोनों पर निर्भर करता है।
Moore Machine - आउटपुट केवल वर्तमान स्थिति पर निर्भर करता है।

DFA और NDFA द्वारा स्वीकार्यता

एक स्ट्रिंग को डीएफए / एनडीएफए द्वारा स्वीकार किया जाता है यदि प्रारंभिक अवस्था में शुरू होने वाले डीएफए / एनडीएफए स्ट्रिंग को पूरी तरह से पढ़ने के बाद एक स्वीकृत राज्य (अंतिम राज्यों में से किसी भी) में समाप्त होता है।

एक स्ट्रिंग S को DFA / NDFA (Q, δ, q, q ₀ , F), iff द्वारा स्वीकार किया जाता है

δ*(q₀, S) ∈ F

भाषा L DFA / NDFA द्वारा स्वीकार किया जाता है

{S | S ∈ ∑* and δ*(q₀, S) ∈ F}

एक स्ट्रिंग S ND को DFA / NDFA (Q, δ, ′, q ₀ , F), iff द्वारा स्वीकार नहीं किया जाता है

δ*(q₀, S′) ∉ F

डीएफए / एनडीएफए (स्वीकृत भाषा एल का पूरक) द्वारा स्वीकृत भाषा The नहीं है

{S | S ∈ ∑* and δ*(q₀, S) ∉ F}

Example

आइए हम चित्र 1.3 में दिखाए गए डीएफए पर विचार करें। DFA से स्वीकार्य तार निकाले जा सकते हैं।