संभाव्य ऑटोमेटन

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

1963 में माइकल ओ राबिन द्वारा अवधारणा पेश की गई थी; एक निश्चित विशेष मामले को कभी-कभी राबिन ऑटोमेटन के रूप में जाना जाता है (ω-automaton#स्वीकृति की शर्तों के उपवर्ग के साथ भ्रमित नहीं होना चाहिए। ω-automata को राबिन ऑटोमेटा भी कहा जाता है)। हाल के वर्षों में, क्वांटम संभावनाओं, क्वांटम परिमित automaton के संदर्भ में एक संस्करण तैयार किया गया है।

अनौपचारिक विवरण

किसी दिए गए प्रारंभिक राज्य और इनपुट चरित्र के लिए, एक नियतात्मक परिमित automaton (DFA) में ठीक एक अगला राज्य होता है, और एक nondeterministic परिमित automaton (NFA) में अगले राज्यों का एक सेट होता है। इसके बजाय एक संभाव्य automaton (PA) में अगले राज्यों का एक भारित सेट (या पंक्ति और स्तंभ वैक्टर) होता है, जहाँ वज़न 1 होना चाहिए और इसलिए इसे संभावनाओं के रूप में व्याख्या किया जा सकता है (इसे एक स्टोकेस्टिक वेक्टर बनाते हुए)। इन भारों के परिचय को प्रतिबिंबित करने के लिए धारणाएं बताती हैं और स्वीकृति को भी संशोधित किया जाना चाहिए। दिए गए कदम के रूप में मशीन की स्थिति को अब राज्यों के एक स्टोचैस्टिक वेक्टर द्वारा भी दर्शाया जाना चाहिए, और एक राज्य को स्वीकार किया जाता है यदि इसकी स्वीकृति स्थिति में होने की कुल संभावना कुछ कट-ऑफ से अधिक हो जाती है।

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

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

संभाव्य automaton को एक nondeterministic परिमित automaton के विस्तार के रूप में परिभाषित किया जा सकता है $(Q,\Sigma ,\delta ,q_{0},F)$, दो संभावनाओं के साथ: संभावना $P$ एक विशेष राज्य संक्रमण हो रहा है, और प्रारंभिक अवस्था के साथ $q_{0}$ एक दिए गए प्रारंभिक अवस्था में ऑटोमेटन की संभावना देने वाले स्टोचैस्टिक वेक्टर द्वारा प्रतिस्थापित किया गया।

साधारण गैर-नियतात्मक परिमित automaton के लिए, किसी के पास है

• राज्यों का एक परिमित सेट (गणित)। $Q$
• इनपुट प्रतीकों का एक परिमित सेट $\Sigma$
• एक संक्रमण समारोह $\delta :Q\times \Sigma \to \wp (Q)$
• राज्यों का एक समूह $F$ स्वीकृत (या अंतिम) राज्यों के रूप में प्रतिष्ठित $F\subseteq Q$.

यहाँ, $\wp (Q)$ के सत्ता स्थापित को दर्शाता है $Q$.

करींग के उपयोग से, संक्रमण समारोह $\delta :Q\times \Sigma \to \wp (Q)$ एक गैर-नियतात्मक परिमित automaton को सदस्यता समारोह के रूप में लिखा जा सकता है

$\delta :Q\times \Sigma \times Q\to \{0,1\}$

ताकि $\delta (q,a,q^{\prime })=1$ अगर $q^{\prime }\in \delta (q,a)$ और $0$ अन्यथा। करी ट्रांज़िशन फ़ंक्शन को मैट्रिक्स प्रविष्टियों के साथ मैट्रिक्स के रूप में समझा जा सकता है

$\left[\theta _{a}\right]_{qq^{\prime }}=\delta (q,a,q^{\prime })$

गणित का सवाल $\theta _{a}$ तब एक वर्ग मैट्रिक्स है, जिसकी प्रविष्टियाँ शून्य या एक हैं, यह दर्शाता है कि संक्रमण है या नहीं $q{\stackrel {a}{\rightarrow }}q^{\prime }$ एनएफए द्वारा अनुमति दी जाती है। इस तरह के एक संक्रमण मैट्रिक्स को हमेशा एक गैर-नियतात्मक परिमित automaton के लिए परिभाषित किया जाता है।

संभाव्य automaton इन matrices को स्टोकास्टिक मैट्रिक्स के परिवार द्वारा प्रतिस्थापित करता है $P_{a}$, वर्णमाला में प्रत्येक प्रतीक a के लिए $\Sigma$ ताकि एक संक्रमण की संभावना द्वारा दिया जाता है

$\left[P_{a}\right]_{qq^{\prime }}$

किसी राज्य से किसी भी राज्य में एक राज्य परिवर्तन निश्चित रूप से प्रायिकता के साथ होना चाहिए, और इसलिए किसी के पास होना चाहिए

$\sum _{q^{\prime }}\left[P_{a}\right]_{qq^{\prime }}=1$

सभी इनपुट पत्रों के लिए $a$ और आंतरिक राज्य $q$. एक संभाव्य automaton की प्रारंभिक स्थिति एक पंक्ति वेक्टर द्वारा दी गई है $v$, जिनके घटक व्यक्तिगत प्रारंभिक अवस्थाओं की संभावनाएँ हैं $q$, जो 1 में जोड़ें:

$\sum _{q}\left[v\right]_{q}=1$

संक्रमण मैट्रिक्स दाईं ओर कार्य करता है, ताकि इनपुट स्ट्रिंग का उपभोग करने के बाद, संभाव्य automaton की स्थिति $abc$, होगा

$vP_{a}P_{b}P_{c}$

विशेष रूप से, एक संभाव्य automaton की स्थिति हमेशा एक स्टोकास्टिक वेक्टर होती है, क्योंकि किसी भी दो स्टोकास्टिक मैट्रिक्स का उत्पाद एक स्टोकास्टिक मैट्रिक्स होता है, और एक स्टोकास्टिक वेक्टर और स्टोकास्टिक मैट्रिक्स का उत्पाद फिर से एक स्टोकास्टिक वेक्टर होता है। इस सदिश को कभी-कभी राज्यों का वितरण कहा जाता है, यह बल देते हुए कि यह एक असतत संभाव्यता वितरण है।

औपचारिक रूप से, एक संभाव्य ऑटोमेटन की परिभाषा के लिए गैर-नियतात्मक ऑटोमेटन के यांत्रिकी की आवश्यकता नहीं होती है, जिसके साथ विवाद हो सकता है। औपचारिक रूप से, एक संभाव्य automaton PA को tuple के रूप में परिभाषित किया गया है $(Q,\Sigma ,P,v,F)$. एक राबिन automaton वह है जिसके लिए प्रारंभिक वितरण होता है $v$ एक समन्वय वेक्टर है; अर्थात्, एक प्रविष्टि को छोड़कर सभी के लिए शून्य है, और शेष प्रविष्टि एक है।

स्टोकेस्टिक भाषाएँ

संभाव्य ऑटोमेटा द्वारा मान्यता प्राप्त औपचारिक भाषा के सेट को स्टोकेस्टिक भाषा कहा जाता है। वे एक उपसमुच्चय के रूप में नियमित भाषाओं को शामिल करते हैं।

होने देना $F=Q_{\text{accept}}\subseteq Q$ ऑटोमेटन की स्वीकृति या अंतिम अवस्थाओं का सेट हो। अंकन के दुरुपयोग से, $Q_{\text{accept}}$ कॉलम वेक्टर के रूप में भी समझा जा सकता है जो कि सदस्यता कार्य है $Q_{\text{accept}}$; अर्थात्, इसमें तत्वों के संगत स्थानों पर 1 है $Q_{\text{accept}}$, और एक शून्य अन्यथा। इस वेक्टर को एक स्केलर (गणित) बनाने के लिए आंतरिक स्थिति संभावना के साथ अनुबंधित किया जा सकता है। एक विशिष्ट automaton द्वारा मान्यता प्राप्त भाषा को तब परिभाषित किया जाता है

$L_{\eta }=\{s\in \Sigma ^{*}\vert vP_{s}Q_{\text{accept}}>\eta \}$

कहाँ $\Sigma ^{*}$ वर्णमाला (कंप्यूटर विज्ञान) में सभी स्ट्रिंग (कंप्यूटर विज्ञान) का सेट है $\Sigma$ (ताकि * क्लेन स्टार हो)। भाषा कट-पॉइंट के मान पर निर्भर करती है $\eta$, आमतौर पर सीमा में होने के लिए लिया जाता है $0\leq \eta <1$.

एक भाषा को η कहा जाता है - स्टोचैस्टिक अगर और केवल अगर वहाँ कुछ पीए मौजूद है जो निश्चित रूप से भाषा को पहचानता है $\eta$. एक भाषा को स्टोकेस्टिक कहा जाता है अगर और केवल अगर कुछ है $0\leq \eta <1$ जिसके लिए $L_{\eta }$ η-स्टोकेस्टिक है।

एक कट-प्वाइंट को 'पृथक कट-पॉइंट' कहा जाता है अगर और केवल अगर मौजूद हो $\delta >0$ ऐसा है कि

$\vert vP(s)Q_{\text{accept}}-\eta \vert \geq \delta$

सभी के लिए $s\in \Sigma ^{*}$

गुण

हर नियमित भाषा स्टोचैस्टिक है, और अधिक दृढ़ता से, हर नियमित भाषा η-स्टोकेस्टिक है। एक कमजोर आक्षेप यह है कि प्रत्येक 0-स्टोकेस्टिक भाषा नियमित है; हालाँकि, सामान्य बातचीत पकड़ में नहीं आती है: ऐसी स्टोकेस्टिक भाषाएँ हैं जो नियमित नहीं हैं।

प्रत्येक η-स्टोकेस्टिक भाषा कुछ के लिए स्टोकेस्टिक है $0<\eta <1$.

प्रत्येक स्टोकेस्टिक भाषा को राबिन ऑटोमेटन द्वारा प्रदर्शित किया जा सकता है।

अगर $\eta$ एक पृथक कट-पॉइंट है, फिर $L_{\eta }$ नियमित भाषा है।

p-adic भाषाएँ

पी-एडिक | पी-एडिक भाषाएं एक स्टोकास्टिक भाषा का उदाहरण प्रदान करती हैं जो नियमित नहीं है, और यह भी दिखाती है कि स्टोकेस्टिक भाषाओं की संख्या बेशुमार है। एक पी-एडिक भाषा को स्ट्रिंग्स के सेट के रूप में परिभाषित किया गया है

$L_{\eta }(p)=\{n_{1}n_{2}n_{3}\ldots \vert 0\leq n_{k}<p{\text{ and }}0.n_{1}n_{2}n_{3}\ldots >\eta \}$

पत्रों में $0,1,2,\ldots ,(p-1)$.

अर्थात्, एक p-adic भाषा केवल [0, 1] में वास्तविक संख्याओं का समुच्चय है, जिसे आधार-p में लिखा गया है, जैसे कि वे इससे अधिक हैं $\eta$. यह दिखाना सीधा है कि सभी पी-एडिक भाषाएँ स्टोकेस्टिक हैं। विशेष रूप से, इसका तात्पर्य है कि स्टोकेस्टिक भाषाओं की संख्या बेशुमार है। एक पी-एडिक भाषा नियमित है अगर और केवल अगर $\eta$ तर्कसंगत है।

सामान्यीकरण

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

ऐसे सामान्यीकरण का एक उदाहरण क्वांटम परिमित ऑटोमेटन है; यहां, ऑटोमेटन राज्य को जटिल प्रक्षेप्य स्थान में एक बिंदु द्वारा दर्शाया गया है, जबकि संक्रमण मेट्रिसेस एकात्मक समूह से चुना गया एक निश्चित सेट है। कट-प्वाइंट को क्वांटम कोण के अधिकतम मान की सीमा के रूप में समझा जाता है।

संदर्भ

• Salomaa, Arto (1969). "Finite nondeterministic and probabilistic automata". Theory of Automata. Oxford: Pergamon Press.