संभाव्य ऑटोमेटन: Difference between revisions

Latest revision as of 15:21, 15 June 2023

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

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

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

किसी दिए गए प्रारंभिक अवस्था और इनपुट चरित्र के लिए, नियतात्मक परिमित ऑटोमेटन (डीएफए) में ठीक अगली अवस्था होती है, और गैर नियतात्मक परिमित ऑटोमेटन (एनएफए) में अगली अवस्थाओं का समुच्चय होता है। इसके अतिरिक्त संभाव्य ऑटोमेटन (पीए) में अगली अवस्थाओं का भारित समुच्चय (या पंक्ति और स्तंभ वैक्टर) होता है, जहाँ वज़न 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$ इससे अधिक हैं। यह दिखाना सीधा है कि सभी पी-एडिक भाषाएँ प्रसंभाव्य हैं।^[3] विशेष रूप से, इसका तात्पर्य है कि प्रसंभाव्य भाषाओं की संख्या अनगिनत है। पी-एडिक भाषा नियमित है यदि और केवल यदि $\eta$ तर्कसंगत है।

सामान्यीकरण

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

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

↑ Paz, Azaria (2014). संभाव्य ऑटोमेटा का परिचय।. ISBN 9781483244655. OCLC 1027002902.
↑ ^2.0 ^2.1 Michael O. Rabin (1963). "संभाव्य ऑटोमेटा". Information and Control. 6 (3): 230–245. doi:10.1016/s0019-9958(63)90290-0.
↑ Merve Nur Cakir; Saleemi, Mehwish; Zimmermann, Karl-Heinz (2021). "स्टोकेस्टिक ऑटोमेटा के सिद्धांत पर". arXiv:2103.14423 [cs.FL].

संदर्भ

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

[1] Paz, Azaria (2014). संभाव्य ऑटोमेटा का परिचय।. ISBN 9781483244655. OCLC 1027002902.

[:0-2] 2.0 ^2.1 Michael O. Rabin (1963). "संभाव्य ऑटोमेटा". Information and Control. 6 (3): 230–245. doi:10.1016/s0019-9958(63)90290-0.

[3] Merve Nur Cakir; Saleemi, Mehwish; Zimmermann, Karl-Heinz (2021). "स्टोकेस्टिक ऑटोमेटा के सिद्धांत पर". arXiv:2103.14423 [cs.FL].

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
-{{technical|date=January 2021}}
+गणित और [[कंप्यूटर विज्ञान]] में, संभाव्य ऑटोमेटन (पीए) गैर-नियतात्मक परिमित ऑटोमेटन का सामान्यीकरण है; इसमें ट्रांज़िशन फलन में दिए गए ट्रांज़िशन की प्रायिकता सम्मिलित है, इसे [[स्टोकेस्टिक मैट्रिक्स|ट्रांज़िशन आव्यूह]] में परिवर्तित कर दिया गया है।<ref>{{Cite book |last=Paz |first=Azaria |url=https://www.worldcat.org/oclc/1027002902 |title=संभाव्य ऑटोमेटा का परिचय।|date=2014 |others= |isbn=9781483244655 |oclc=1027002902}}</ref><ref name=":0">{{cite journal |last=Michael O. Rabin |author-link=Michael O. Rabin |date=1963 |title=संभाव्य ऑटोमेटा|journal=Information and Control |volume=6 |issue=3 |pages=230–245 |doi= 10.1016/s0019-9958(63)90290-0|doi-access=free }}</ref> इस प्रकार, संभाव्य ऑटोमेटन भी [[मार्कोव श्रृंखला]] की अवधारणाओं और परिमित प्रकार के सबशिफ्ट का सामान्यीकरण करता है। संभाव्य ऑटोमेटन द्वारा मान्यता प्राप्त [[औपचारिक भाषा]] को प्रसंभाव्य भाषा कहा जाता है; इनमें उपसमुच्चय के रूप में [[नियमित भाषा|नियमित भाषाएं]] सम्मिलित हैं। प्रसंभाव्य भाषाओं की संख्या [[बेशुमार|अनगिनत]] है।
-गणित और [[कंप्यूटर विज्ञान]] में, संभाव्य automaton (PA) गैर-नियतात्मक परिमित automaton का एक सामान्यीकरण है; इसमें परिमित राज्य मशीन में दिए गए संक्रमण की संभावना शामिल है, इसे [[स्टोकेस्टिक मैट्रिक्स]] में बदलना।<ref>{{Cite book |last=Paz |first=Azaria |url=https://www.worldcat.org/oclc/1027002902 |title=संभाव्य ऑटोमेटा का परिचय।|date=2014 |others= |isbn=9781483244655 |oclc=1027002902}}</ref><ref name=":0" />इस प्रकार, संभाव्य automaton भी एक [[मार्कोव श्रृंखला]] की अवधारणाओं और परिमित प्रकार के एक सबशिफ्ट का सामान्यीकरण करता है। संभाव्य ऑटोमेटा द्वारा मान्यता प्राप्त [[औपचारिक भाषा]] को स्टोकेस्टिक भाषा कहा जाता है; इनमें उपसमुच्चय के रूप में [[नियमित भाषा]]एं शामिल हैं। स्टोकेस्टिक भाषाओं की संख्या [[बेशुमार]] है।
-में माइकल ओ राबिन द्वारा अवधारणा पेश की गई थी;<ref name=":0">{{cite journal |last=Michael O. Rabin |author-link=Michael O. Rabin |date=1963 |title=संभाव्य ऑटोमेटा|journal=Information and Control |volume=6 |issue=3 |pages=230–245 |doi= 10.1016/s0019-9958(63)90290-0|doi-access=free }}</ref> एक निश्चित विशेष मामले को कभी-कभी राबिन ऑटोमेटन के रूप में जाना जाता है (ω-automaton#स्वीकृति की शर्तों के उपवर्ग के साथ भ्रमित नहीं होना चाहिए। ω-automata को राबिन ऑटोमेटा भी कहा जाता है)। हाल के वर्षों में, क्वांटम संभावनाओं, क्वांटम परिमित automaton के संदर्भ में एक संस्करण तैयार किया गया है।
+यह अवधारणा 1963 में माइकल ओ. राबिन द्वारा प्रस्तुत की गई थी;<ref name=":0" /> विशेष अवस्था को कभी-कभी राबिन ऑटोमेटन के रूप में जाना जाता है (ω-ऑटोमेटन के उपवर्ग के साथ भ्रमित नहीं होना चाहिए जिसे राबिन ऑटोमेटन भी कहा जाता है)। हाल के वर्षों में, क्वांटम प्रायिकताओं, क्वांटम परिमित ऑटोमेटन के संदर्भ में संस्करण तैयार किया गया है।
 == अनौपचारिक विवरण ==
-किसी दिए गए प्रारंभिक राज्य और इनपुट चरित्र के लिए, एक [[नियतात्मक परिमित automaton]] (DFA) में ठीक एक अगला राज्य होता है, और एक nondeterministic परिमित automaton (NFA) में अगले राज्यों का एक सेट होता है। इसके बजाय एक संभाव्य automaton (PA) में अगले राज्यों का एक भारित सेट (या [[पंक्ति और स्तंभ वैक्टर]]) होता है, जहाँ वज़न 1 होना चाहिए और इसलिए इसे संभावनाओं के रूप में व्याख्या किया जा सकता है (इसे एक [[स्टोकेस्टिक वेक्टर]] बनाते हुए)। इन भारों के परिचय को प्रतिबिंबित करने के लिए धारणाएं बताती हैं और स्वीकृति को भी संशोधित किया जाना चाहिए। दिए गए कदम के रूप में मशीन की स्थिति को अब राज्यों के एक स्टोचैस्टिक वेक्टर द्वारा भी दर्शाया जाना चाहिए, और एक राज्य को स्वीकार किया जाता है यदि इसकी स्वीकृति स्थिति में होने की कुल संभावना कुछ कट-ऑफ से अधिक हो जाती है।
+किसी दिए गए प्रारंभिक अवस्था और इनपुट चरित्र के लिए, [[नियतात्मक परिमित automaton|नियतात्मक परिमित ऑटोमेटन]] (डीएफए) में ठीक अगली अवस्था होती है, और गैर नियतात्मक परिमित ऑटोमेटन (एनएफए) में अगली अवस्थाओं का समुच्चय होता है। इसके अतिरिक्त संभाव्य ऑटोमेटन (पीए) में अगली अवस्थाओं का भारित समुच्चय (या [[पंक्ति और स्तंभ वैक्टर]]) होता है, जहाँ वज़न 1 होना चाहिए और इसलिए इसे प्रायिकताओं के रूप में व्याख्या किया जा सकता है (इसे [[स्टोकेस्टिक वेक्टर|प्रसंभाव्य सदिश]] बनाते हुए)। इन भारों के परिचय को प्रतिबिंबित करने के लिए धारणाएं बताती हैं कि स्वीकृति को भी संशोधित किया जाना चाहिए। दिए गए चरण के रूप में मशीन की अवस्था को अब अवस्थाओं के स्टोचैस्टिक सदिश द्वारा भी दर्शाया जाना चाहिए, और अवस्था को स्वीकार किया जाता है यदि इसकी स्वीकृति अवस्था में होने की कुल प्रायिकता कुछ कट-ऑफ से अधिक हो जाती है।
-एक पीए कुछ अर्थों में नियतात्मक से गैर-नियतात्मक तक एक आधा-अधूरा कदम है, क्योंकि यह अगले राज्यों के एक सेट की अनुमति देता है लेकिन उनके वजन पर प्रतिबंध के साथ। हालांकि, यह कुछ हद तक भ्रामक है, क्योंकि पीए वजन को परिभाषित करने के लिए वास्तविक संख्या की धारणा का उपयोग करता है, जो डीएफए और एनएफए दोनों की परिभाषा में अनुपस्थित है। यह अतिरिक्त स्वतंत्रता उन्हें उन भाषाओं को तय करने में सक्षम बनाती है जो नियमित नहीं हैं, जैसे कि अपरिमेय मापदंडों वाली पी-एडिक भाषाएँ। जैसे, पीए डीएफए और एनएफए दोनों (जो समान रूप से प्रसिद्ध हैं) की तुलना में अधिक शक्तिशाली हैं।
+पीए कुछ अर्थों में नियतात्मक से गैर-नियतात्मक तक आधा-अधूरा चरण है, क्योंकि यह अगली अवस्थाओं के समुच्चय की अनुमति उनके वजन पर प्रतिबंध के साथ देता है। चूँकि, यह कुछ सीमा तक भ्रामक है, क्योंकि पीए वजन को परिभाषित करने के लिए वास्तविक संख्या की धारणा का उपयोग करता है, जो डीएफए और एनएफए दोनों की परिभाषा में अनुपस्थित है। यह अतिरिक्त स्वतंत्रता उन्हें उन भाषाओं को तय करने में सक्षम बनाती है जो नियमित नहीं हैं, जैसे कि अपरिमेय मापदंडों वाली पी-एडिक भाषाएँ; जैसे, पीए डीएफए और एनएफए दोनों (जो समान रूप से प्रसिद्ध हैं) की तुलना में अधिक शक्तिशाली हैं।
 == औपचारिक परिभाषा ==
-संभाव्य automaton को एक nondeterministic परिमित automaton के विस्तार के रूप में परिभाषित किया जा सकता है <math>(Q,\Sigma,\delta,q_0,F)</math>, दो संभावनाओं के साथ: संभावना <math>P</math> एक विशेष राज्य संक्रमण हो रहा है, और प्रारंभिक अवस्था के साथ <math>q_0</math> एक दिए गए प्रारंभिक अवस्था में ऑटोमेटन की संभावना देने वाले स्टोचैस्टिक वेक्टर द्वारा प्रतिस्थापित किया गया।
+संभाव्य ऑटोमेटन को गैर नियतात्मक परिमित ऑटोमेटन <math>(Q,\Sigma,\delta,q_0,F)</math> के विस्तार के रूप में परिभाषित किया जा सकता है, दो प्रायिकताओं के साथ: विशेष अवस्था संक्रमण की प्रायिकता <math>P</math> है, और प्रारंभिक अवस्था <math>q_0</math> के साथ दिए गए प्रारंभिक अवस्था में ऑटोमेटन की प्रायिकता देने वाले स्टोचैस्टिक सदिश द्वारा प्रतिस्थापित किया गया।
-साधारण गैर-नियतात्मक परिमित automaton के लिए, किसी के पास है
+साधारण गैर-नियतात्मक परिमित ऑटोमेटन के लिए, किसी के पास है:
-* राज्यों का एक परिमित [[सेट (गणित)]]। <math>Q</math>
+* अवस्थाओं का परिमित [[सेट (गणित)|समुच्चय]] <math>Q</math>।
-* [[इनपुट प्रतीक]]ों का एक परिमित सेट <math>\Sigma</math>
+* [[इनपुट प्रतीक|इनपुट प्रतीकों]] का परिमित समुच्चय <math>\Sigma</math>
-* एक संक्रमण समारोह <math>\delta:Q\times\Sigma \to \wp(Q)</math>
+*संक्रमण फलन <math>\delta:Q\times\Sigma \to \wp(Q)</math>
-* राज्यों का एक समूह <math>F</math> स्वीकृत (या अंतिम) राज्यों के रूप में प्रतिष्ठित <math>F\subseteq Q</math>.
+* अवस्थाओं का समूह <math>F</math> स्वीकृत (या अंतिम) अवस्थाओं के रूप में प्रतिष्ठित <math>F\subseteq Q</math>।
-यहाँ, <math>\wp(Q)</math> के [[ सत्ता स्थापित ]] को दर्शाता है <math>Q</math>.
+यहाँ, <math>\wp(Q)</math>, <math>Q</math> के [[ सत्ता स्थापित |पावर समुच्चय]] को दर्शाता है।
-[[करी]]ंग के उपयोग से, संक्रमण समारोह <math>\delta:Q\times\Sigma \to \wp(Q)</math> एक गैर-नियतात्मक परिमित automaton को [[सदस्यता समारोह]] के रूप में लिखा जा सकता है
+[[करी|करींग]] के उपयोग से, संक्रमण फलन <math>\delta:Q\times\Sigma \to \wp(Q)</math> गैर-नियतात्मक परिमित ऑटोमेटन को [[सदस्यता समारोह|सदस्यता फलन]] के रूप में लिखा जा सकता है:
 :<math>\delta:Q\times\Sigma \times Q\to \{0,1\}</math>
-ताकि <math>\delta(q,a,q^\prime)=1</math> अगर <math>q^\prime\in \delta(q,a)</math> और <math>0</math> अन्यथा। करी ट्रांज़िशन फ़ंक्शन को मैट्रिक्स प्रविष्टियों के साथ मैट्रिक्स के रूप में समझा जा सकता है
+जिससे <math>\delta(q,a,q^\prime)=1</math> यदि <math>q^\prime\in \delta(q,a)</math> और अन्यथा <math>0</math>। करी ट्रांज़िशन फलन को आव्यूह प्रविष्टियों के साथ आव्यूह के रूप में समझा जा सकता है:
 :<math>\left[\theta_a\right]_{qq^\prime}=\delta(q,a,q^\prime)</math>
-गणित का सवाल <math>\theta_a</math> तब एक वर्ग मैट्रिक्स है, जिसकी प्रविष्टियाँ शून्य या एक हैं, यह दर्शाता है कि संक्रमण है या नहीं <math>q\stackrel{a}{\rightarrow} q^\prime</math> एनएफए द्वारा अनुमति दी जाती है। इस तरह के एक संक्रमण मैट्रिक्स को हमेशा एक गैर-नियतात्मक परिमित automaton के लिए परिभाषित किया जाता है।
+आव्यूह <math>\theta_a</math> तब वर्ग आव्यूह है, जिसकी प्रविष्टियाँ शून्य या एक हैं, यह दर्शाता है कि एनएफए द्वारा संक्रमण <math>q\stackrel{a}{\rightarrow} q^\prime</math> की अनुमति है या नहीं है। इस तरह के संक्रमण आव्यूह को सदैव गैर-नियतात्मक परिमित ऑटोमेटन के लिए परिभाषित किया जाता है।
-संभाव्य automaton इन matrices को स्टोकास्टिक मैट्रिक्स के परिवार द्वारा प्रतिस्थापित करता है <math>P_a</math>, वर्णमाला में प्रत्येक प्रतीक a के लिए <math>\Sigma</math> ताकि एक संक्रमण की संभावना द्वारा दिया जाता है
+संभाव्य ऑटोमेटन इन आव्यूह को स्टोकास्टिक आव्यूह <math>P_a</math> के परिवार द्वारा प्रतिस्थापित करता है, वर्णमाला में प्रत्येक प्रतीक ''a'' के लिए <math>\Sigma</math> जिससे संक्रमण की प्रायिकता द्वारा दिया जाता है:
 :<math>\left[P_a\right]_{qq^\prime}</math>
-किसी राज्य से किसी भी राज्य में एक राज्य परिवर्तन निश्चित रूप से प्रायिकता के साथ होना चाहिए, और इसलिए किसी के पास होना चाहिए
+किसी अवस्था से किसी भी अवस्था में अवस्था परिवर्तन निश्चित रूप से प्रायिकता के साथ होना चाहिए, और इसलिए किसी के पास होना चाहिए
 :<math>\sum_{q^\prime}\left[P_a\right]_{qq^\prime}=1</math>
-सभी इनपुट पत्रों के लिए <math>a</math> और आंतरिक राज्य <math>q</math>. एक संभाव्य automaton की प्रारंभिक स्थिति एक [[पंक्ति वेक्टर]] द्वारा दी गई है <math>v</math>, जिनके घटक व्यक्तिगत प्रारंभिक अवस्थाओं की संभावनाएँ हैं <math>q</math>, जो 1 में जोड़ें:
+सभी इनपुट अक्षरों के लिए <math>a</math> और आंतरिक अवस्था <math>q</math>। संभाव्य ऑटोमेटन की प्रारंभिक अवस्था [[पंक्ति वेक्टर|पंक्ति सदिश]] <math>v</math> द्वारा दी गई है, जिनके घटक व्यक्तिगत प्रारंभिक अवस्थाओं <math>q</math> की प्रायिकताएँ हैं, जो 1 में जोड़ते हैं:
 :<math>\sum_{q}\left[v\right]_{q}=1</math>
-संक्रमण मैट्रिक्स दाईं ओर कार्य करता है, ताकि इनपुट स्ट्रिंग का उपभोग करने के बाद, संभाव्य automaton की स्थिति <math>abc</math>, होगा
+संक्रमण आव्यूह दाईं ओर कार्य करता है, जिससे इनपुट स्ट्रिंग का उपभोग करने के बाद, संभाव्य ऑटोमेटन <math>abc</math> की अवस्था, होगी
 :<math>v P_a P_b P_c</math>
-विशेष रूप से, एक संभाव्य automaton की स्थिति हमेशा एक स्टोकास्टिक वेक्टर होती है, क्योंकि किसी भी दो स्टोकास्टिक मैट्रिक्स का उत्पाद एक स्टोकास्टिक मैट्रिक्स होता है, और एक स्टोकास्टिक वेक्टर और स्टोकास्टिक मैट्रिक्स का उत्पाद फिर से एक स्टोकास्टिक वेक्टर होता है। इस सदिश को कभी-कभी राज्यों का वितरण कहा जाता है, यह बल देते हुए कि यह एक [[असतत संभाव्यता वितरण]] है।
+विशेष रूप से, संभाव्य ऑटोमेटन की अवस्था सदैव स्टोकास्टिक सदिश रहती है, क्योंकि किसी भी दो स्टोकास्टिक आव्यूह का गुणनफल स्टोकास्टिक आव्यूह होता है, और स्टोकास्टिक सदिश और स्टोकास्टिक आव्यूह का गुणनफल फिर से स्टोकास्टिक सदिश होता है। इस सदिश को कभी-कभी अवस्थाओं का वितरण कहा जाता है, यह ध्यान देते हुए कि यह [[असतत संभाव्यता वितरण|असतत प्रायिकता वितरण]] है।
-औपचारिक रूप से, एक संभाव्य ऑटोमेटन की परिभाषा के लिए गैर-नियतात्मक ऑटोमेटन के यांत्रिकी की आवश्यकता नहीं होती है, जिसके साथ विवाद हो सकता है। औपचारिक रूप से, एक संभाव्य automaton ''PA'' को tuple के रूप में परिभाषित किया गया है <math>(Q,\Sigma,P, v, F)</math>. एक राबिन automaton वह है जिसके लिए प्रारंभिक वितरण होता है <math>v</math> एक [[समन्वय वेक्टर]] है; अर्थात्, एक प्रविष्टि को छोड़कर सभी के लिए शून्य है, और शेष प्रविष्टि एक है।
+औपचारिक रूप से, संभाव्य ऑटोमेटन की परिभाषा के लिए गैर-नियतात्मक ऑटोमेटन के यांत्रिकी की आवश्यकता नहीं होती है, जिसके साथ विवाद हो सकता है। औपचारिक रूप से, संभाव्य ऑटोमेटन ''पीए'' को टपल <math>(Q,\Sigma,P, v, F)</math> के रूप में परिभाषित किया गया है। राबिन ऑटोमेटन वह है, जिसके लिए प्रारंभिक वितरण <math>v</math> [[समन्वय वेक्टर|समन्वय सदिश]] है; अर्थात्, प्रविष्टि को छोड़कर सभी के लिए शून्य है, और शेष प्रविष्टि 1 है।
-== स्टोकेस्टिक भाषाएँ ==
+== प्रसंभाव्य भाषाएँ ==
-संभाव्य ऑटोमेटा द्वारा मान्यता प्राप्त औपचारिक भाषा के सेट को स्टोकेस्टिक भाषा कहा जाता है। वे एक उपसमुच्चय के रूप में नियमित भाषाओं को शामिल करते हैं।
+संभाव्य ऑटोमेटन द्वारा मान्यता प्राप्त औपचारिक भाषा के समुच्चय को प्रसंभाव्य भाषा कहा जाता है। वे उपसमुच्चय के रूप में नियमित भाषाओं को सम्मिलित करते हैं।
-होने देना <math>F=Q_\text{accept}\subseteq Q</math> ऑटोमेटन की स्वीकृति या अंतिम अवस्थाओं का सेट हो। अंकन के दुरुपयोग से, <math>Q_\text{accept}</math> कॉलम वेक्टर के रूप में भी समझा जा सकता है जो कि सदस्यता कार्य है <math>Q_\text{accept}</math>; अर्थात्, इसमें तत्वों के संगत स्थानों पर 1 है  <math>Q_\text{accept}</math>, और एक शून्य अन्यथा। इस वेक्टर को एक स्केलर (गणित) बनाने के लिए आंतरिक स्थिति संभावना के साथ अनुबंधित किया जा सकता है। एक विशिष्ट automaton द्वारा मान्यता प्राप्त भाषा को तब परिभाषित किया जाता है
+माना <math>F=Q_\text{accept}\subseteq Q</math> ऑटोमेटन की स्वीकृति या अंतिम अवस्थाओं का समुच्चय है। अंकन के दुरुपयोग से, <math>Q_\text{accept}</math> कॉलम सदिश के रूप में भी समझा जा सकता है, जो कि सदस्यता फलन <math>Q_\text{accept}</math> है; अर्थात्, इसमें <math>Q_\text{accept}</math> तत्वों के संगत स्थानों पर 1 है, और अन्यथा शून्य है। इस सदिश को स्केलर (गणित) बनाने के लिए आंतरिक अवस्था प्रायिकता के साथ अनुबंधित किया जा सकता है। विशिष्ट ऑटोमेटन द्वारा मान्यता प्राप्त भाषा को तब परिभाषित किया जाता है
 :<math>L_\eta = \{s\in\Sigma^* \vert vP_s Q_\text{accept} > \eta\}</math>
-कहाँ <math>\Sigma^*</math> [[वर्णमाला (कंप्यूटर विज्ञान)]] में सभी [[स्ट्रिंग (कंप्यूटर विज्ञान)]] का सेट है <math>\Sigma</math> (ताकि * [[क्लेन स्टार]] हो)। भाषा कट-पॉइंट के मान पर निर्भर करती है <math>\eta</math>, आमतौर पर सीमा में होने के लिए लिया जाता है <math>0\le \eta<1</math>.
+जहाँ <math>\Sigma^*</math> [[वर्णमाला (कंप्यूटर विज्ञान)]] में सभी [[स्ट्रिंग (कंप्यूटर विज्ञान)]] का समुच्चय <math>\Sigma</math> (जिससे * [[क्लेन स्टार]] हो) है। भाषा कट-पॉइंट <math>\eta</math> के मान पर निर्भर करती है, सामान्यतः <math>0\le \eta<1</math> की श्रेणी में लिया जाता है।
-एक भाषा को ''η'' कहा जाता है - स्टोचैस्टिक अगर और केवल अगर वहाँ कुछ पीए मौजूद है जो निश्चित रूप से भाषा को पहचानता है <math>\eta</math>. एक भाषा को स्टोकेस्टिक कहा जाता है अगर और केवल अगर कुछ है  <math>0\le \eta<1</math> जिसके लिए <math>L_\eta</math> η-स्टोकेस्टिक है।
+भाषा को ''η'' कहा जाता है - स्टोचैस्टिक यदि और केवल यदि वहाँ कुछ पीए उपस्थित है, जो निश्चित रूप से <math>\eta</math> भाषा को पहचानता है। भाषा को प्रसंभाव्य कहा जाता है यदि और केवल यदि कुछ <math>0\le \eta<1</math> है, जिसके लिए <math>L_\eta</math> η-प्रसंभाव्य है।
-एक कट-प्वाइंट को 'पृथक कट-पॉइंट' कहा जाता है अगर और केवल अगर मौजूद हो <math>\delta>0</math> ऐसा है कि
+कट-बिंदु को 'पृथक कट-पॉइंट' कहा जाता है यदि और केवल यदि <math>\delta>0</math> उपस्थित हो, जैसे कि
 :<math>\vert vP(s)Q_\text{accept} - \eta \vert \ge \delta</math>
@@ Line 61: / Line 60: @@
 == गुण ==
-हर नियमित भाषा स्टोचैस्टिक है, और अधिक दृढ़ता से, हर नियमित भाषा η-स्टोकेस्टिक है। एक कमजोर आक्षेप यह है कि प्रत्येक 0-स्टोकेस्टिक भाषा नियमित है; हालाँकि, सामान्य बातचीत पकड़ में नहीं आती है: ऐसी स्टोकेस्टिक भाषाएँ हैं जो नियमित नहीं हैं।
+हर नियमित भाषा स्टोचैस्टिक है, और अधिक दृढ़ता से, हर नियमित भाषा η-प्रसंभाव्य है। अशक्त आक्षेप यह है कि प्रत्येक 0-प्रसंभाव्य भाषा नियमित है; चूँकि, सामान्य वार्तालाप पकड़ में नहीं आती है: ऐसी प्रसंभाव्य भाषाएँ हैं, जो नियमित नहीं हैं।
-प्रत्येक η-स्टोकेस्टिक भाषा कुछ के लिए स्टोकेस्टिक है <math>0<\eta<1</math>.
+प्रत्येक η-प्रसंभाव्य भाषा कुछ <math>0<\eta<1</math> के लिए प्रसंभाव्य है।
-प्रत्येक स्टोकेस्टिक भाषा को राबिन ऑटोमेटन द्वारा प्रदर्शित किया जा सकता है।
+प्रत्येक प्रसंभाव्य भाषा को राबिन ऑटोमेटन द्वारा प्रदर्शित किया जा सकता है।
-अगर <math>\eta</math> एक पृथक कट-पॉइंट है, फिर <math>L_\eta</math> नियमित भाषा है।
+यदि <math>\eta</math> पृथक कट-पॉइंट है, फिर <math>L_\eta</math> नियमित भाषा है।
-==p-adic भाषाएँ==
+==पी-एडिक भाषाएँ==
-पी-एडिक | पी-एडिक भाषाएं एक स्टोकास्टिक भाषा का उदाहरण प्रदान करती हैं जो नियमित नहीं है, और यह भी दिखाती है कि स्टोकेस्टिक भाषाओं की संख्या बेशुमार है। एक पी-एडिक भाषा को स्ट्रिंग्स के सेट के रूप में परिभाषित किया गया है
+पी-एडिक भाषाएं स्टोकास्टिक भाषा का उदाहरण प्रदान करती हैं जो नियमित नहीं है, और यह भी दिखाती है कि प्रसंभाव्य भाषाओं की संख्या अनगिनत है। पी-एडिक भाषा को स्ट्रिंग्स के समुच्चय के रूप में परिभाषित किया गया है
 :<math>L_{\eta}(p)=\{n_1n_2n_3 \ldots \vert 0\le n_k<p \text{ and }
 .n_1n_2n_3\ldots > \eta \}</math>
-पत्रों में <math>0,1,2,\ldots,(p-1)</math>.
+अक्षरों में <math>0,1,2,\ldots,(p-1)</math>।
-अर्थात्, एक p-adic भाषा केवल [0, 1] में वास्तविक संख्याओं का समुच्चय है, जिसे आधार-p में लिखा गया है, जैसे कि वे इससे अधिक हैं <math>\eta</math>. यह दिखाना सीधा है कि सभी पी-एडिक भाषाएँ स्टोकेस्टिक हैं।<ref>{{cite arXiv |eprint=2103.14423|author1=Merve Nur Cakir|last2=Saleemi|first2=Mehwish|last3=Zimmermann|first3=Karl-Heinz|title=स्टोकेस्टिक ऑटोमेटा के सिद्धांत पर|year=2021|class=cs.FL}}</ref> विशेष रूप से, इसका तात्पर्य है कि स्टोकेस्टिक भाषाओं की संख्या बेशुमार है। एक पी-एडिक भाषा नियमित है अगर और केवल अगर <math>\eta</math> तर्कसंगत है।
+अर्थात्, पी-एडिक भाषा केवल [0, 1] में वास्तविक संख्याओं का समुच्चय है, जिसे आधार-p में लिखा गया है, जैसे कि वे <math>\eta</math> इससे अधिक हैं। यह दिखाना सीधा है कि सभी पी-एडिक भाषाएँ प्रसंभाव्य हैं।<ref>{{cite arXiv |eprint=2103.14423|author1=Merve Nur Cakir|last2=Saleemi|first2=Mehwish|last3=Zimmermann|first3=Karl-Heinz|title=स्टोकेस्टिक ऑटोमेटा के सिद्धांत पर|year=2021|class=cs.FL}}</ref> विशेष रूप से, इसका तात्पर्य है कि प्रसंभाव्य भाषाओं की संख्या अनगिनत है। पी-एडिक भाषा नियमित है यदि और केवल यदि <math>\eta</math> तर्कसंगत है।
 == सामान्यीकरण ==
-संभाव्य automaton की एक ज्यामितीय व्याख्या है: राज्य वेक्टर को एक बिंदु के रूप में समझा जा सकता है जो ऑर्थोगोनल कोने के विपरीत मानक [[संकेतन]] के चेहरे पर रहता है। ट्रांज़िशन मेट्रिसेस बिंदु पर अभिनय करते हुए एक [[मोनोइड]] बनाते हैं। यह बिंदु कुछ सामान्य [[टोपोलॉजिकल स्पेस]] से होने के कारण सामान्यीकृत हो सकता है, जबकि ट्रांज़िशन मेट्रिसेस को टोपोलॉजिकल स्पेस पर काम करने वाले ऑपरेटरों के एक संग्रह से चुना जाता है, इस प्रकार एक सेमीऑटोमेटन का निर्माण होता है। जब कट-पॉइंट को उपयुक्त रूप से सामान्यीकृत किया जाता है, तो एक [[टोपोलॉजिकल ऑटोमेटन]] होता है।
+संभाव्य ऑटोमेटन की ज्यामितीय व्याख्या है: अवस्था सदिश को बिंदु के रूप में समझा जा सकता है, जो ऑर्थोगोनल कोने के विपरीत मानक [[संकेतन]] के चेहरे पर रहता है। ट्रांज़िशन आव्यूह बिंदु पर अभिनय करते हुए [[मोनोइड]] बनाते हैं। यह बिंदु कुछ सामान्य [[टोपोलॉजिकल स्पेस]] से होने के कारण सामान्यीकृत हो सकता है, जबकि ट्रांज़िशन आव्यूह को टोपोलॉजिकल स्पेस पर काम करने वाले ऑपरेटरों के संग्रह से चुना जाता है, इस प्रकार सेमीऑटोमेटन का निर्माण होता है। जब कट-पॉइंट को उपयुक्त रूप से सामान्यीकृत किया जाता है, तो [[टोपोलॉजिकल ऑटोमेटन]] होता है।
-ऐसे सामान्यीकरण का एक उदाहरण क्वांटम परिमित ऑटोमेटन है; यहां, ऑटोमेटन राज्य को [[जटिल प्रक्षेप्य स्थान]] में एक बिंदु द्वारा दर्शाया गया है, जबकि संक्रमण मेट्रिसेस [[एकात्मक समूह]] से चुना गया एक निश्चित सेट है। कट-प्वाइंट को [[क्वांटम कोण]] के अधिकतम मान की सीमा के रूप में समझा जाता है।
+ऐसे सामान्यीकरण का उदाहरण क्वांटम परिमित ऑटोमेटन है; यहां, ऑटोमेटन अवस्था को [[जटिल प्रक्षेप्य स्थान]] में बिंदु द्वारा दर्शाया गया है, जबकि संक्रमण आव्यूह [[एकात्मक समूह]] से चुना गया निश्चित समुच्चय है। कट-बिंदु को [[क्वांटम कोण]] के अधिकतम मान की सीमा के रूप में समझा जाता है।
 ==टिप्पणियाँ==
@@ Line 89: / Line 88: @@
 ==संदर्भ==
 *{{ cite book | last1 = Salomaa | first1 = Arto |author-link = Arto Salomaa| title = Theory of Automata | location = Oxford | publisher = [[Pergamon Press]] | year = 1969 | chapter = Finite nondeterministic and probabilistic automata }}
-[[Category: स्वतः समाप्त हो गया]] [[Category: संभाव्य मॉडल]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 29/05/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:संभाव्य मॉडल]]
+[[Category:स्वतः समाप्त हो गया]]

Anonymous

Search

संभाव्य ऑटोमेटन: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 15:21, 15 June 2023

Contents

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

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

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

गुण

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

सामान्यीकरण

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

संभाव्य ऑटोमेटन: Difference between revisions

Latest revision as of 15:21, 15 June 2023

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

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

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

गुण

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

सामान्यीकरण

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories