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

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

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

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

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

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

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

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

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

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

यहाँ, $\wp (Q)$, $Q$ के पावर समुच्चय को दर्शाता है।

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

$\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 }$ की अनुमति है या नहीं है। इस तरह के संक्रमण आव्यूह को सदैव गैर-नियतात्मक परिमित ऑटोमेटन के लिए परिभाषित किया जाता है।

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

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

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

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

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

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

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

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

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

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

प्रसंभाव्य भाषाएँ

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

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

$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 }$ नियमित भाषा है।

पी-एडिक भाषाएँ

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

$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)$।

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

सामान्यीकरण

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

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

संदर्भ

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