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

(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 में परिवर्तित करता है, जो एक सुविधाजनक संकेतन प्रदान करता है।

उदाहरण

m के लिए स्थिति आरेख। यह नियतात्मक नहीं है क्योंकि स्थिति p में 1 पढ़ने से p या q हो सकता है।	इनपुट स्ट्रिंग "10" पर m के सभी संभावित रन।
इनपुट स्ट्रिंग "1011" पर m के सभी संभावित रन।आर्क लेबल: इनपुट प्रतीक, नोड लेबल: स्थिति, हरा: प्रारंभ स्थिति, लाल: स्वीकार करने वाली स्थिति।

निम्नलिखित ऑटोमेटन $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 प्रतीक को पढ़कर। जबकि प्रारंभिक "1" का उपभोग करने के बाद q तक पहुंचा जा सकता है, इसका मतलब यह नहीं है कि इनपुट "10" स्वीकार किया गया है; बल्कि, इसका मतलब है कि एक इनपुट स्ट्रिंग "1" स्वीकार की जाएगी।

DFA के समतुल्य

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

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

यह परिणाम दर्शाता है कि NFA, अपने अतिरिक्त तन्यता के तथापि, उन भाषाओं को पहचानने में असमर्थ हैं जिन्हें कुछ DFA द्वारा पहचाना नहीं जा सकता है। निर्माण में आसान NFA को अधिक कुशलतापूर्वक निष्पादन योग्य DFA में परिवर्तित करना व्यवहार में भी महत्वपूर्ण है। यद्यपि, यदि NFA में n स्थिति हैं, तो परिणामी 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$ परिमित-अवस्था मशीन के रूप में $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$ इसे दो DFA एक स्थितियों के साथ $\{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 उपस्थित है।

एप्सिलॉन मूव्स $M=(Q,\Sigma ,\delta ,q_{0},F),$ के साथ 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.)