नॉनडेटर्मिनिस्टिक परिमित ऑटोमेटन

(0|1)^* 1 (0|1)³.
उस औपचारिक भाषा के लिए एक नियतात्मक परिमित ऑटोमेटन में कम से कम 16 अवस्थाएँ होती हैं।

ऑटोमेटा सिद्धांत में, एक परिमित-अवस्था मशीन को नियतात्मक परिमित ऑटोमेटन (DFA) कहा जाता है, यदि

• इसका प्रत्येक परिवर्तन स्रोत स्थिति और निविष्ट प्रतीक द्वारा विशिष्ट रूप से निर्धारित होता है, और
• प्रत्येक स्थिति परिवर्तन के लिए एक निविष्ट प्रतीक पढ़ना आवश्यक है।

'नॉनडेटर्मिनिस्टिक परिमित ऑटोमेटन' ('NFA'), या 'नॉनडेटर्मिनिस्टिक परिमित-स्थिति मशीन' को इन प्रतिबंधों का पालन करने की आवश्यकता नहीं है। विशेष रूप से, प्रत्येक DFA(DFA) एक NFA (NFA) भी है। कभी-कभी 'NFA' शब्द का प्रयोग एक संकीर्ण अर्थ में किया जाता है, जो एक NFA का संदर्भ देता है जो DFAनहीं है, लेकिन इस लेख में ऐसा नहीं है।

उप-समूचय निर्माण कलन विधि का उपयोग करके, प्रत्येक NFA को समकक्ष DFAमें अनुवादित किया जा सकता है अर्थात, DFAसमान औपचारिक भाषा को मान्यता देता है।DFAकी तरह, NFA केवल नियमित भाषाओं को पहचानते हैं।

NFA की प्रारम्भ 1959 में माइकल ओ. राबिन और दाना स्कॉट द्वारा की गई थी, जिन्होंने DFAके समकक्ष भी दिखाया। NFA का उपयोग नियमित अभिव्यक्तियों के कार्यान्वयन में किया जाता है: थॉम्पसन का निर्माण NFA में नियमित अभिव्यक्ति को संकलित करने के लिए एक कलन विधि है जो स्ट्रिंग्स पर पैटर्न मिलान को कुशलतापूर्वक निष्पादित कर सकता है। इसके विपरीत, क्लेन के कलन विधि का उपयोग NFA को नियमित अभिव्यक्ति में परिवर्तित करने के लिए किया जा सकता है (जिसका आकार सामान्यतः निविष्ट ऑटोमेटन में घातांक होता है)।

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

अनौपचारिक परिचय

NFA के व्यवहार का वर्णन करने के दो तरीके हैं, और ये दोनों समान हैं। पहला तरीका NFA के नाम पर गैर-नियतात्मक का उपयोग करता है। प्रत्येक निविष्ट प्रतीक के लिए, NFA एक नई स्थिति में परिवर्तित हो जाता है जब तक कि सभी निविष्ट प्रतीकों का उपभोग नहीं हो जाता। प्रत्येक चरण में, ऑटोमेटन गैर-नियतात्मक रूप से लागू परिवर्तनों में से एक को चुनता है। यदि कम से कम एक भाग्यशाली रनउपस्थित है, अर्थात विकल्पों का कुछ क्रम जो पूरी तरह से निविष्ट का उपभोग करने के बाद एक स्वीकार्य स्थिति की ओर ले जाता है, तो इसे स्वीकार कर लिया जाता है। अन्यथा, अर्थात यदि कोई विकल्प अनुक्रम नहीं है तो सभी निविष्ट का उपभोग कर सकता है और एक स्वीकार्य स्थिति की ओर ले जाता है, निविष्ट अस्वीकार कर दिया जाता है।

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

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

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

ऑटोमेटन

NFA को औपचारिक रूप से 5-टपल द्वारा दर्शाया जाता है, $(Q,\Sigma ,\delta ,q_{0},F)$, जिसमें सम्मिलित है

• स्थितियों का एक सीमित समुच्चय (गणित) $Q$।
• निविष्ट प्रतीकों का एक सीमित समुच्चय $\Sigma$.
• एक परिवर्तन फ़ंक्शन $\delta$ : $Q\times \Sigma \rightarrow {\mathcal {P}}(Q)$.
• एक प्रारंभिक (या आरंभ) अवस्था $q_{0}\in Q$.
• स्थितियों का एक समुच्चय $F$ स्वीकार करने वाले (या अंतिम) स्थितियों के रूप में प्रतिष्ठित $F\subseteq Q$.

यहाँ, ${\mathcal {P}}(Q)$ के पावर समुच्चय को दर्शाता है $Q$.

स्वीकृत भाषा

$M=(Q,\Sigma ,\delta ,q_{0},F)$ NFA दिया गया , इसकी स्वीकृत भाषा $L(M)$ द्वारा दर्शाया जाता है , और इसे वर्णमाला $\Sigma$ के सभी तारों के समुच्चय के रूप में परिभाषित किया गया है जिसे $M$ स्वीकार किया जाता है .उपरोक्त अनौपचारिक स्पष्टीकरणों के अनुरूप, एक स्ट्रिंग $w=a_{1}a_{2}...a_{n}$ की कई समान औपचारिक परिभाषाएँ हैं जिसे $M$ द्वारा स्वीकार किया जा रहा है :

• $w$ स्वीकार है यदि स्थितियों का अनुक्रम $r_{0},r_{1},...,r_{n}$, $Q$ में उपस्थित है, ऐसा है कि:
  1. $r_{0}=q_{0}$
  2. $r_{i+1}\in \delta (r_{i},a_{i+1})$, के लिए $i=0,\ldots ,n-1$
  3. $r_{n}\in F$.

शब्दों में, पहली शर्त कहती है कि मशीन प्रारंभ अवस्था $q_{0}$ में शुरू होती है . दूसरी शर्त कहती है कि स्ट्रिंग $w$ का प्रत्येक अक्षर दिया गया है , मशीन ट्रांज़िशन फ़ंक्शन $\delta$ के अनुसार एक स्थिति से दूसरे स्थिति में स्थानांतरित होगी . आखिरी शर्त कहती है कि मशीन स्वीकार करती है $w$ यदि अंतिम निविष्ट $w$ मशीन को स्वीकार करने वाले स्थितियों में से एक में रुकने का कारण बनता है। के क्रम में $w$ द्वारा स्वीकार किया जाना $M$, यह आवश्यक नहीं है कि प्रत्येक स्थिति अनुक्रम एक स्वीकार्य स्थिति में समाप्त हो, यदि कोई ऐसा करता है तो यह पर्याप्त है। अन्यथा, अर्थात यदि इसे प्राप्त करना बिल्कुल भी असंभव है $q_{0}$ से एक स्थिति तक $F$ अनुगमन करते हुए $w$, ऐसा कहा जाता है कि ऑटोमेटन स्ट्रिंग को अस्वीकार कर देता है। तार का समुच्चय $M$ एक्सेप्ट्स द्वारा स्वीकृत औपचारिक भाषा है $M$ तथा इस भाषा को निरूपित किया जाता है $L(M)$.

• वैकल्पिक रूप से, $w$ स्वीकार किया जाता है यदि $\delta ^{*}(q_{0},w)\cap F\not =\emptyset$, कहाँ $\delta ^{*}:Q\times \Sigma ^{*}\rightarrow {\mathcal {P}}(Q)$ रिकर्सन (कंप्यूटर विज्ञान) को इसके द्वारा परिभाषित किया गया है:
  1. $\delta ^{*}(r,\epsilon )=\{r\}$ कहाँ $\epsilon$ खाली स्ट्रिंग है, और
  2. $\delta ^{*}(r,xa)=\bigcup _{r'\in \delta ^{*}(r,x)}\delta (r',a)$ सभी के लिए $x\in \Sigma ^{*},a\in \Sigma$.

शब्दों में, $\delta ^{*}(r,x)$ स्थिति से पहुंच योग्य सभी स्थितियों का समूह है $r$ स्ट्रिंग का उपभोग करके $x$. डोर $w$ यदि कोई स्वीकार करने वाला स्थिति है तो स्वीकार किया जाता है $F$ आरंभिक स्थिति से पहुंचा जा सकता है $q_{0}$ सेवन करने से $w$.

प्रारंभिक अवस्था

उपरोक्त ऑटोमेटन परिभाषा एकल प्रारंभिक अवस्था का उपयोग करती है, जो आवश्यक नहीं है। कभी-कभी, NFA को प्रारंभिक अवस्थाओं के एक समुच्चय के साथ परिभाषित किया जाता है। एक आसान निर्माण है जो कई प्रारंभिक स्थितियों वाले NFA को एक प्रारंभिक स्थिति वाले NFA में परिवर्तित करता है, जो एक सुविधाजनक संकेतन प्रदान करता है।

उदाहरण

The state diagram for M. It is not deterministic since in state p reading a 1 can lead to p or to q.	All possible runs of M on input string "10".
All possible runs of M on input string "1011". Arc label: input symbol, node label: state, green: start state, red: accepting state(s).

निम्नलिखित ऑटोमेटन $M$, एक द्विआधारी वर्णमाला के साथ, यह निर्धारित करता है कि निविष्ट 1 के साथ समाप्त होता है या नहीं।माना कि $M=(\{p,q\},\{0,1\},\delta ,p,\{q\})$ जहाँ परिवर्तन फलन $\delta$ को स्थिति परिवर्तन तालिका द्वारा परिभाषित किया जा सकता है (ऊपरी बाएँ चित्र की तुलना करें):

Input State	0	1
$p$	$\{p\}$	$\{p,q\}$
$q$	$\emptyset$	$\emptyset$

समुच्चय के बाद से $\delta (p,1)$ इसमें एक से अधिक स्थिति सम्मिलित हैं, $M$ गैर नियतिवादी है. की भाषा $M$ रेगुलर एक्सप्रेशन द्वारा दी गई नियमित भाषा द्वारा वर्णित किया जा सकता है (0|1)*1.

निविष्ट स्ट्रिंग 1011 के लिए सभी संभावित स्थिति अनुक्रम निचले चित्र में दिखाए गए हैं। स्ट्रिंग द्वारा स्वीकार किया जाता है $M$ चूँकि एक अवस्था अनुक्रम उपरोक्त परिभाषा को संतुष्ट करता है; इससे कोई फर्क नहीं पड़ता कि अन्य अनुक्रम ऐसा करने में विफल रहते हैं। चित्र की व्याख्या दो प्रयोगो से की जा सकती है:

• #अनौपचारिक परिचय लकी-रन स्पष्टीकरण के संदर्भ में, चित्र में प्रत्येक पथ विकल्पों के अनुक्रम को दर्शाता है $M$.
• क्लोनिंग स्पष्टीकरण के संदर्भ में, प्रत्येक ऊर्ध्वाधर कॉलम सभी क्लोन दिखाता है $M$ किसी दिए गए समय बिंदु पर, एक नोड से निकलने वाले कई तीर क्लोनिंग का संकेत देते हैं, एक नोड जिसमें तीर नहीं निकल रहे हैं, एक क्लोन की मृत्यु का संकेत देता है।

एक ही चित्र को दो प्रयोगो से पढ़ने की व्यवहार्यता उपरोक्त दोनों स्पष्टीकरणों की समानता को भी इंगित करती है।

• #मान्य भाषा की औपचारिक परिभाषाओं में से प्रथम को ध्यान में रखते हुए 1011 को इसे पढ़ने के समय से ही स्वीकार किया जाता है $M$ स्थिति अनुक्रम को पार कर सकता है $\langle r_{0},r_{1},r_{2},r_{3},r_{4}\rangle =\langle p,p,p,p,q\rangle$, जो शर्तें 1 से 3 को संतुष्ट करता है।
• दूसरी औपचारिक परिभाषा के संबंध में, नीचे से ऊपर की गणना यह दर्शाती है $\delta ^{*}(p,\epsilon )=\{p\}$, इस तरह $\delta ^{*}(p,1)=\delta (p,1)=\{p,q\}$, इस तरह $\delta ^{*}(p,10)=\delta (p,0)\cup \delta (q,0)=\{p\}\cup \{\}$, इस तरह $\delta ^{*}(p,101)=\delta (p,1)=\{p,q\}$, और इसलिए $\delta ^{*}(p,1011)=\delta (p,1)\cup \delta (q,1)=\{p,q\}\cup \{\}$; चूँकि वह समुच्चय असंयुक्त नहीं है $\{q\}$, स्ट्रिंग 1011 स्वीकार की जाती है।

इसके विपरीत, स्ट्रिंग 10 को अस्वीकार कर दिया गया है $M$ (उस निविष्ट के लिए सभी संभावित स्थिति अनुक्रम ऊपरी दाएँ चित्र में दिखाए गए हैं), चूँकि एकमात्र स्वीकार्य स्थिति तक पहुँचने का कोई रास्ता नहीं है, $q$, अंतिम 0 प्रतीक को पढ़कर। जबकि $q$ आरंभिक 1 का उपभोग करने के बाद पहुंचा जा सकता है, इसका मतलब यह नहीं है कि निविष्ट 10 स्वीकार कर लिया गया है; बल्कि, इसका मतलब है कि एक निविष्ट स्ट्रिंग 1 स्वीकार किया जाएगा।

DFAके समतुल्य

एक नियतात्मक परिमित ऑटोमेटन (डीएफए) को एक विशेष प्रकार के NFA के रूप में देखा जा सकता है, जिसमें प्रत्येक स्थिति और प्रतीक के लिए, परिवर्तन फ़ंक्शन में बिल्कुल एक स्थिति होता है। इस प्रकार, यह स्पष्ट है कि प्रत्येक औपचारिक भाषा जिसे DFAद्वारा मान्यता दी जा सकती है, उसे NFA द्वारा मान्यता दी जा सकती है।

इसके विपरीत, प्रत्येक NFA के लिए, एक DFAहोता है जो समान औपचारिक भाषा को पहचानता है। DFAका निर्माण पॉवरसमुच्चय निर्माण का उपयोग करके किया जा सकता है।

यह परिणाम दर्शाता है कि NFA, अपने अतिरिक्त लचीलेपन के बावजूद, उन भाषाओं को पहचानने में असमर्थ हैं जिन्हें कुछ DFAद्वारा पहचाना नहीं जा सकता है। निर्माण में आसान NFA को अधिक कुशलतापूर्वक निष्पादन योग्य DFAमें परिवर्तित करना व्यवहार में भी महत्वपूर्ण है। हालाँकि, यदि NFA में एन स्थिति हैं, तो परिणामी DFAमें 2 तक हो सकते हैंⁿ स्थिति, जो कभी-कभी बड़े NFA के लिए निर्माण को अव्यवहारिक बना देता है।

NFA ε-चालों के साथ

ε-मूव्स (NFA-ε) के साथ नॉनडेटर्मिनिस्टिक परिमित ऑटोमेटन NFA का एक और सामान्यीकरण है। इस प्रकार के ऑटोमेटन में, परिवर्तन फ़ंक्शन को खाली स्ट्रिंग ε पर अतिरिक्त रूप से परिभाषित किया गया है। निविष्ट प्रतीक का उपभोग किए बिना एक परिवर्तन को ε-परिवर्तन कहा जाता है और स्थिति आरेखों में ε लेबल वाले तीर द्वारा दर्शाया जाता है। ε-परिवर्तन उन प्रणालियों को मॉडलिंग करने का एक सुविधाजनक तरीका प्रदान करता है जिनकी वर्तमान स्थिति सटीक रूप से ज्ञात नहीं है: अर्थात, यदि हम एक प्रणाली का मॉडलिंग कर रहे हैं और यह स्पष्ट नहीं है कि वर्तमान स्थिति (कुछ निविष्ट स्ट्रिंग को संसाधित करने के बाद) q या q' होनी चाहिए, तो हम इन दोनों स्थितियों के बीच एक ε-परिवर्तन जोड़ सकते हैं, इस प्रकार दोनों स्थितियों में ऑटोमेटन को एक साथ रख सकते हैं।

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

NFA-ε को औपचारिक रूप से 5-टुपल द्वारा दर्शाया जाता है, $(Q,\Sigma ,\delta ,q_{0},F)$, को मिलाकर

• स्थिति का एक सीमित समुच्चय (गणित) (कंप्यूटर विज्ञान) $Q$
• निविष्ट प्रतीकों का एक सीमित समुच्चय जिसे वर्णमाला (कंप्यूटर विज्ञान) कहा जाता है $\Sigma$
• एक परिवर्तन फ़ंक्शन (गणित) $\delta :Q\times (\Sigma \cup \{\epsilon \})\rightarrow {\mathcal {P}}(Q)$
• एक प्रारंभिक (या परिमित-अवस्था मशीन#प्रारंभ स्थिति) स्थिति $q_{0}\in Q$
• स्थितियों का एक समुच्चय $F$ परिमित-अवस्था मशीन के रूप में प्रतिष्ठित#स्वीकार .28या अंतिम.29 स्थिति|स्वीकार (या अंतिम) स्थिति $F\subseteq Q$.

यहाँ, ${\mathcal {P}}(Q)$ के पावर समुच्चय को दर्शाता है $Q$ और $\epsilon$ खाली स्ट्रिंग को दर्शाता है.

ε-किसी स्थिति या स्थितियों के समूह का बंद होना

एक स्थिति के लिए $q\in Q$, माना कि $E(q)$ उन स्थितियों के समूह को निरूपित करें जिनसे पहुंच योग्य है $q$ परिवर्तन फलन में ε-परिवर्तन का अनुसरण करके $\delta$, अर्थात।, $p\in E(q)$ यदि स्थितियों का कोई क्रम है $q_{1},...,q_{k}$ ऐसा है कि

• $q_{1}=q$,
• $q_{i+1}\in \delta (q_{i},\varepsilon )$ प्रत्येक के लिए $1\leq i<k$, और
• $q_{k}=p$.

$E(q)$ इसे एप्सिलॉन क्लोजर (ε-क्लोजर भी) के रूप में जाना जाता है $q$.

एक समुच्चय का ε-क्लोजर $P$ NFA के स्थितियों की संख्या को किसी भी स्थिति से पहुंच योग्य स्थितियों के समूह के रूप में परिभाषित किया गया है $P$ निम्नलिखित ε-परिवर्तन। औपचारिक रूप से, के लिए $P\subseteq Q$, परिभाषित करना $E(P)=\bigcup \limits _{q\in P}E(q)$.

विस्तारित परिवर्तन फ़ंक्शन

ε-चालों के बिना NFA के समान, परिवर्तन फ़ंक्शन $\delta$ NFA-ε को स्ट्रिंग्स तक बढ़ाया जा सकता है। अनौपचारिक रूप से, $\delta ^{*}(q,w)$ उन सभी अवस्थाओं के समुच्चय को दर्शाता है जिन तक ऑटोमेटन स्थिति में शुरू होने पर पहुंच सकता है $q\in Q$ और स्ट्रिंग को पढ़ना $w\in \Sigma ^{*}.$ कार्यक्रम $\delta ^{*}:Q\times \Sigma ^{*}\rightarrow {\mathcal {P}}(Q)$ निम्नानुसार पुनरावर्ती रूप से परिभाषित किया जा सकता है।

• $\delta ^{*}(q,\varepsilon )=E(q)$, प्रत्येक स्थिति के लिए $q\in Q,$ और कहाँ $E$ एप्सिलॉन बंद होने को दर्शाता है;

अनौपचारिक रूप से: खाली स्ट्रिंग को पढ़ने से ऑटोमेटन स्थिति से बाहर हो सकता है $q$ ईपीएसलॉन के बंद होने की किसी भी स्थिति के लिए $q.$

• ${\textstyle \delta ^{*}(q,wa)=\bigcup _{r\in \delta ^{*}(q,w)}E(\delta (r,a)),}$ प्रत्येक स्थिति के लिए $q\in Q,$ प्रत्येक स्ट्रिंग $w\in \Sigma ^{*}$ और प्रत्येक प्रतीक $a\in \Sigma .$

अनौपचारिक रूप से: स्ट्रिंग पढ़ना $w$ ऑटोमेटन को स्थिति से बाहर चला सकता है $q$ किसी भी स्थिति के लिए $r$ पुनरावर्ती गणना समुच्चय में $\delta ^{*}(q,w)$; उसके बाद, प्रतीक को पढ़ना $a$ इसे चला सकते हैं $r$ ईपीएसलॉन बंद करने में किसी भी स्थिति के लिए $\delta (r,a).$ कहा जाता है कि ऑटोमेटन एक स्ट्रिंग को स्वीकार करता है $w$ यदि

$\delta ^{*}(q_{0},w)\cap F\neq \emptyset ,$ अर्थात यदि पढ़ रहे हैं $w$ ऑटोमेटन को उसकी आरंभिक स्थिति से चला सकता है $q_{0}$ कुछ स्वीकार करने वाले स्थिति में $F.$

उदाहरण

एम के लिए स्थिति आरेख

माना कि $M$ एक बाइनरी वर्णमाला के साथ एक NFA-ε हो, जो यह निर्धारित करता है कि निविष्ट में 0 की सम संख्या है या 1 की सम संख्या है। ध्यान दें कि 0 घटनाएँ भी घटनाओं की एक सम संख्या है।

औपचारिक संकेतन में, चलो

$$M=(\{S_{0},S_{1},S_{2},S_{3},S_{4}\},\{0,1\},\delta ,S_{0},\{S_{1},S_{3}\})$$

कहाँ परिवर्तन संबंध $\delta$ इस स्थिति परिवर्तन तालिका द्वारा परिभाषित किया जा सकता है:

Input State	0	1	ε
S0	{}	{}	{S1, S3}
S1	{S2}	{S1}	{}
S2	{S1}	{S2}	{}
S3	{S3}	{S4}	{}
S4	{S4}	{S3}	{}

$M$ इसे दो नियतात्मक परिमित स्वचालित यंत्रों के मिलन के रूप में देखा जा सकता है: एक स्थितियों के साथ $\{S_{1},S_{2}\}$ और दूसरा स्थितियों के साथ $\{S_{3},S_{4}\}$. की भाषा $M$ इस नियमित अभिव्यक्ति द्वारा दी गई नियमित भाषा द्वारा वर्णित किया जा सकता है $(1^{*}01^{*}0)^{*}\cup (0^{*}10^{*}1)^{*}$. हम परिभाषित करते हैं $M$ ε-चालों का उपयोग करना लेकिन $M$ ε-चालों का उपयोग किए बिना परिभाषित किया जा सकता है।

NFA के समतुल्य

यह दिखाने के लिए कि NFA-ε NFA के बराबर है, पहले ध्यान दें कि NFA NFA-ε का एक विशेष मामला है, इसलिए यह दिखाना बाकी है कि प्रत्येक NFA-ε के लिए, एक समकक्ष NFAउपस्थित है।

एप्सिलॉन चालों के साथ एक NFA दिया गया o show NFA-ε is equivalent to NFA, first note that NFA is a speciaase of $q\in Q$ NFA-ε, so it remains to show for every NFफ़ंक्शन, there exists an equivalent NFA.

Given an NFA with epsilon moves  define an NFA

where NFA को परिभाषित करें $M'=(Q,\Sigma ,\delta ',q_{0},F'),$ कहाँ

$F'={\begin{cases}F\cup \{q_{0}\}&{\text{ if }}E(q_{0})\cap F\neq \{\}\\F&{\text{ otherwise }}\\\end{cases}}$

और

$\delta '(q,a)=\delta ^{*}(q,a)$ प्रत्येक स्थिति $q\in Q$ के लिए और प्रत्येक प्रतीक $a\in \Sigma ,$ विस्तारित परिवर्तन फलन का उपयोग करना $\delta ^{*}$ ऊपर परिभाषित.

$M$ और $M'$ $\delta$ और $\delta '$ के परिवर्तन कार्यों में अंतर करना होगा अर्थात. और स्ट्रिंग्स में उनका विस्$\delta ^{*}(q_{0},w)\cap F\neq \{\},$ तार, $\delta$ और $\delta '^{*},$ क्रमशः निर्मारा, $M'$ कोई ε-परिवर्तन नहीं है।

कोई $\delta '^{*}(q_{0},w)=\delta ^{*}(q_{0},w)$ साबित कर सकता है प्रत्येक स्ट्रिंग $w\neq \varepsilon$ के लिए , की लंबाई $w$ पर गणितीय प्रेरण द्वारा

इसके आधार पर $\delta '^{*}(q_{0},w)\cap F'\neq \{\}$ यह दिखा सकता है यदि और केवल यदि, प्रत्येक स्ट्रिंग के लिए $w\in \Sigma ^{*}$ $\delta ^{*}(q_{0},w)\cap F\neq \{\}$ है

• यदि $w=\varepsilon ,$ यह $F'$ की परिभाषा से अनुसरण करता है
• अन्यथा माना  कि $w=va$ साथ $v\in \Sigma ^{*}$ और $a\in \Sigma .$ :से $\delta '^{*}(q_{0},w)=\delta ^{*}(q_{0},w)$ और $F\subseteq F',$ अपने पास
  $$\delta '^{*}(q_{0},w)\cap F'\neq \{\}\;\Leftarrow \;\delta ^{*}(q_{0},w)\cap F\neq \{\};$$
  हमें अभी भी $\Rightarrow$ दिशा दिखाना है।

• यदि $\delta '^{*}(q_{0},w)$ स्थिति $F'\setminus \{q_{0}\}$ में सम्मिलित है तब $\delta ^{*}(q_{0},w)$ जिसमें वही स्थिति सम्मिलित है, जो $F$ में निहित है .
• यदि $\delta '^{*}(q_{0},w)$ $q_{0},$ और $q_{0}\in F$ में सम्मिलित है तब $\delta ^{*}(q_{0},w)$ में स्थिति $F$ अर्थात. $q_{0}$ भी सम्मिलित है
• यदि $\delta '^{*}(q_{0},w)$ $q_{0}$ और $q_{0}\not \in F$ में सम्मिलित है तब स्थिति in $E(q_{0})\cap F$ ${\textstyle \delta ^{*}(q_{0},w)=\bigcup _{r\in \delta ^{*}(q,v)}E(\delta (r,a))}$ में होना चाहिए

चूंकि NFA DFA के बराबर है, NFA-ε भी DFA के बराबर है।

बंद गुण

कुछ दिए गए NFA की भाषाओं के मिलन को स्वीकार करते हुए NFA की रचना की गई N(s) और N(t). भाषा संघ में एक निविष्ट स्ट्रिंग w के लिए, रचित ऑटोमेटन q से एक उपयुक्त सबऑटोमेटन की प्रारंभ स्थिति (बाएं रंगीन सर्कल) में ε-परिवर्तन का अनुसरण करता है - N(s) या N(t) - जो, w का अनुसरण करके, एक स्वीकार्य स्थिति (दाएं रंग का वृत्त) तक पहुंच सकता है; वहां से, अवस्था f तक दूसरे ε-परिवर्तन द्वारा पहुंचा जा सकता है। ε-परिवर्तनों के कारण, संकलित NFA उचित रूप से गैर-नियतात्मक है, भले ही दोनों हों N(s) और N(t) DFAथे; इसके विपरीत, संघ भाषा (यहां तक ​​कि दो डीएफए) के लिए DFAका निर्माण करना अधिक जटिल है।

NFA द्वारा स्वीकृत भाषाओं का समुच्चय निम्नलिखित परिचालनों के तहत बंद है। इन क्लोजर ऑपरेशंस का उपयोग थॉम्पसन के निर्माण कलन विधि में किया जाता है, जो किसी भी नियमित अभिव्यक्ति से NFA का निर्माण करता है। उनका उपयोग यह साबित करने के लिए भी किया जा सकता है कि NFA बिल्कुल नियमित भाषाओं को पहचानते हैं।

• संघ (सीएफ. चित्र); अर्थात्, यदि भाषा L1 को कुछ NFA A1 द्वारा और L2 को कुछ A2 द्वारा स्वीकार किया जाता है, तो एक NFA Au का निर्माण किया जा सकता है जो भाषा L1∪L2 को स्वीकार करता है।
• चौराहा; इसी तरह, A1 और A2 से एक NFA Ai का निर्माण किया जा सकता है जो L1∩L2 को स्वीकार करता है।
• कड़ी
• नकार; इसी तरह, A1 से एक NFA An का निर्माण किया जा सकता है जो Σ*\L1 को स्वीकार करता है।
• क्लीन क्लोजर

चूंकि NFA ε-मूव्स (NFA-ε) के साथ नॉनडेटर्मिनिस्टिक परिमित ऑटोमेटन के बराबर हैं, उपरोक्त क्लोजर NFA-ε के क्लोजर गुणों का उपयोग करके सिद्ध किए जाते हैं।

गुण

मशीन फ़ंक्शन्दिष्ट प्रारंभिक अवस्था में शुरू होती है और अपने वर्णमाला (कंप्यूटर विज्ञान) से प्रतीकों की एक श्रृंखला में पढ़ती है। ऑटोमेटन वर्तमान स्थिति का उपयोग करके अगली स्थिति निर्धारित करने के लिए स्थिति परिवर्तन फलन Δ का उपयोग करता है, और प्रतीक बस पढ़ता है या खाली स्ट्रिंग। हालाँकि, NFA की अगली स्थिति न केवल वर्तमान निविष्ट घटना पर निर्भर करती है, बल्कि बाद की निविष्ट घटनाओं की मनमानी संख्या पर भी निर्भर करती है। जब तक ये आगामी घटनाएँ घटित नहीं हो जातीं तब तक यह निर्धारित करना संभव नहीं है कि मशीन किस स्थिति में है। यदि, जब ऑटोमेटन ने पढ़ना समाप्त कर लिया है, यह स्वीकार करने की स्थिति में है, तो NFA को स्ट्रिंग को स्वीकार करने के लिए कहा जाता है, अन्यथा इसे स्ट्रिंग को अस्वीकार करने के लिए कहा जाता है।

NFA द्वारा स्वीकृत सभी स्ट्रिंग्स का समुच्चय वह भाषा है जिसे NFA स्वीकार करता है। यह भाषा एक नियमित भाषा है.

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

कार्यान्वयन

NFA लागू करने के कई तरीके हैं:

• समतुल्य DFAमें कनवर्ट करें। कुछ मामलों में इससे स्थितियों की संख्या में तेजी से बढ़ोतरी होफ़ंक्शनती है।
• सभी स्थितियों की एक समुच्चय डेटा संरचना रखें जिसमें NFA वर्तमान में हो सकता है। एक निविष्ट प्रतीक की खपत पर, अगले स्थितियों का समुच्चय प्राप्त करने के लिए सभीउपस्थित स्थितियों पर लागू परिवर्तन फलन के परिणामों को समुच्चय करें; यदि ε-चालों की अनुमति है, तो ऐसी चाल (ε-बंद) द्वारा पहुंच योग्य सभी स्थितियों को सम्मिलित करें। प्रत्येक चरण के लिए अधिकतम s² गणना की आवश्यकता होती है , जहां s NFA के स्थितियों की संख्या है। अंतिम निविष्ट प्रतीक की खपत पर, यदि वर्तमान स्थिति में से एक अंतिम स्थिति है, तो मशीन स्ट्रिंग को स्वीकार करती है। लंबाई n की एक स्ट्रिंग को समय O(ns²),और स्थान O(s) में संसाधित किया जा सकता है)।
• एकाधिक प्रतियाँ बनाएँ। प्रत्येक n-तरफ़ा निर्णय के लिए, NFA मशीन की n−1 प्रतियां बनाता है। प्रत्येक एक अलग स्थिति में प्रवेश करेगा। यदि, अंतिम निविष्ट प्रतीक का उपभोग करने पर, NFA की कम से कम एक प्रति स्वीकार करने की स्थिति में है, तो NFA स्वीकार करेगा। (इसके लिए भी, NFA स्थितियों की संख्या के संबंध में रैखिक भंडारण की आवश्यकता होती है, क्योंकि प्रत्येक NFA स्थिति के लिए एक मशीन हो सकती है।)
• NFA की परिवर्तन संरचना के माध्यम से टोकन को स्पष्ट रूप से प्रचारित करें और जब भी कोई टोकन अंतिम स्थिति में पहुंचे तो उसका मिलान करें। यह कभी-कभी उपयोगी होता है जब NFA को उन घटनाओं के बारे में अतिरिक्त संदर्भ को एन्कोड करना चाहिए जिन्होंने परिवर्तन को ट्रिगर किया। (ऐसे कार्यान्वयन के लिए जो ऑब्जेक्ट संदर्भों पर नज़र रखने के लिए इस तकनीक का उपयोग करता है, ट्रेसमैच पर एक नज़र डालें।)
• NFA दिए जाने पर यह जांचने के लिए पीएसपीएसीई-पूर्ण है कि क्या यह सार्वभौमिक है, अर्थात, यदि कोई स्ट्रिंग है जिसे यह स्वीकार नहीं करता है। समावेशन समस्या के बारे में भी यही सच है, अर्थात, दो NFA दिए जाने पर, एक की भाषा दूसरे की भाषा का उप-समूचय है।

NFA का अनुप्रयोग

NFA और DFAइस मायने में समतुल्य हैं कि यदि कोई भाषा NFA द्वारा स्वीकृत है, तो इसे DFAद्वारा भी स्वीकृत है और इसके विपरीत भी। ऐसी समतुल्यता की स्थापना महत्वपूर्ण एवं उपयोगी है। यह उपयोगी है क्योंकि किसी दी गई भाषा को पहचानने के लिए NFA का निर्माण करना कभी-कभी उस भाषा के लिए DFAके निर्माण की तुलना में बहुत आसान होता है। यह महत्वपूर्ण है क्योंकि गणना के सिद्धांत में कई महत्वपूर्ण गुणों को समुच्चय करने के लिए आवश्यक गणितीय कार्य की जटिलता को कम करने के लिए NFA का उपयोग किया जा सकता है। उदाहरण के लिए, DFAकी तुलना में NFA का उपयोग करके नियमित भाषाओं के क्लोजर गुणों को साबित करना बहुत आसान है।

यह भी देखें

• नियतात्मक परिमित स्वचालन
• दोतरफा गैर-नियतात्मक परिमित ऑटोमेटन
• पुशडाउन ऑटोमेटन
• नॉनडेटर्मिनिस्टिक ट्यूरिंग मशीन

संदर्भ

• M. O. Rabin and D. Scott, "Finite Automata and their Decision Problems", IBM Journal of Research and Development, 3:2 (1959) pp. 115–125.
• Michael Sipser, Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 0-534-94728-X. (see section 1.2: Nondeterminism, pp. 47–63.)
• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 2.)