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

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

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

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

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

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

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

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

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

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

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

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

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

ऑटोमेटन

एनफए को औपचारिक रूप से 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)$ एनफए दिया गया , इसकी स्वीकृत भाषा $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$ से पहुंचा जा सकता है

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

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

उदाहरण

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" स्वीकार की जाएगी।

डीएफए के समतुल्य

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

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

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

एनफए ε-मूव्स(स्थान-परिवर्तन) के साथ

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

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

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

विस्तारित परिवर्तन फलन

ε-मूव्स के रहित एनफए के समान, परिवर्तन फलन $\delta$ एनफए-ε को स्ट्रिंग्स तक बढ़ाया जा सकता है। अनौपचारिक रूप से, $\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$ एक बाइनरी वर्णमाला के साथ एक एनफए-ε हो, जो यह निर्धारित करता है कि निविष्ट में 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$ को परिभाषित किया जा सकता है।

एनफए के समतुल्य

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

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

चूंकि एनफए डीएफए के बराबर है, एनफए-ε भी डीएफए के बराबर है।

संवरण गुण

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

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

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

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

गुण

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

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

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

कार्यान्वयन

एनफए लागू करने के कई विधि हैं:

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

एनफए का अनुप्रयोग

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

यह भी देखें

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

संदर्भ

• 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.)