सामान्य रूप (सार पुनर्लेखन): Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(5 intermediate revisions by 3 users not shown)
Line 2: Line 2:
[[सार पुनर्लेखन]] में<ref>{{cite book |author=[[Franz Baader]] |author2=[[Tobias Nipkow]] |title=टर्म पुनर्लेखन और वह सब|year=1998 |publisher=[[Cambridge University Press]] |isbn=9780521779203 |url=https://books.google.com/books?id=N7BvXVUCQk8C&q=%22normal+form%22}}</ref> एक वस्तु सामान्य रूप में होती है यदि इसे आगे फिर से नहीं लिखा जा सकता है अर्थात यह अप्रासंगिक है। पुनर्लेखन प्रणाली के आधार पर एक वस्तु कई सामान्य रूपों में फिर से लिख सकती है या पूर्ण रूप से भी नहीं पुनर्लेखन प्रणालियों के कई गुण सामान्य रूपों से संबंधित हैं।
[[सार पुनर्लेखन]] में<ref>{{cite book |author=[[Franz Baader]] |author2=[[Tobias Nipkow]] |title=टर्म पुनर्लेखन और वह सब|year=1998 |publisher=[[Cambridge University Press]] |isbn=9780521779203 |url=https://books.google.com/books?id=N7BvXVUCQk8C&q=%22normal+form%22}}</ref> एक वस्तु सामान्य रूप में होती है यदि इसे आगे फिर से नहीं लिखा जा सकता है अर्थात यह अप्रासंगिक है। पुनर्लेखन प्रणाली के आधार पर एक वस्तु कई सामान्य रूपों में फिर से लिख सकती है या पूर्ण रूप से भी नहीं पुनर्लेखन प्रणालियों के कई गुण सामान्य रूपों से संबंधित हैं।


== परिभाषाएँ '''<अवधि वर्ग = एंकर आईडी = परिभाषा>'''==
== परिभाषाएँ ==
औपचारिक रूप से कहा गया है, यदि (A,→) एक अमूर्त पुनर्लेखन प्रणाली या परिभाषा है, x∈A 'सामान्य रूप' में है यदि कोई y∈A उपस्थित नहीं है जैसे कि x→y, यानी x एक अप्रासंगिक शब्द है।
औपचारिक रूप से कहा गया है, यदि (A,→) एक अमूर्त पुनर्लेखन प्रणाली या परिभाषा है, x∈A 'सामान्य रूप' में है यदि कोई y∈A उपस्थित नहीं है जैसे कि x→y, यानी x एक अप्रासंगिक शब्द है।


एक वस्तु a 'अशक्त रूप से सामान्यीकरण' है यदि वहाँ से प्रारंभ होने वाले पुनर्लेखन का कम से कम एक विशेष क्रम उपस्थित है जो अंततः एक सामान्य रूप देता है। एक पुनर्लेखन प्रणाली में 'अशक्त सामान्यीकरण गुण' होता है या (अशक्त ) सामान्यीकरण (डब्ल्यू एन) होता है यदि प्रत्येक वस्तु अशक्त रूप से सामान्य हो रही हो। एक वस्तु a 'दृढ़ता से सामान्य' होती है यदि a से प्रारंभ होने वाले पुनर्लेखन का प्रत्येक क्रम अंततः सामान्य रूप से समाप्त हो जाता है। एक सार पुनर्लेखन प्रणाली जोरदार सामान्यीकरण समाप्ति नोथेरियन है, या '(शसक्त) सामान्यीकरण संपत्ति' (एसएन) है यदि इसकी प्रत्येक वस्तु दृढ़ता से सामान्य हो रही है।<ref>{{cite journal |last1=Ohlebusch |first1=Enno |title=एब्स्ट्रैक्ट रिडक्शन मोडुलो ए इक्वैलेंस रिलेशन के लिए चर्च-रॉसर प्रमेय|journal=Rewriting Techniques and Applications |series=Lecture Notes in Computer Science |date=1998 |volume=1379 |page=18 |doi=10.1007/BFb0052358 |isbn=978-3-540-64301-2 |url=https://books.google.com/books?id=ESr6CAAAQBAJ&pg=PA18}}</ref>
एक वस्तु a 'अशक्त रूप से सामान्यीकरण' है यदि वहाँ से प्रारंभ होने वाले पुनर्लेखन का कम से कम एक विशेष क्रम उपस्थित है जो अंततः एक सामान्य रूप देता है। एक पुनर्लेखन प्रणाली में 'अशक्त सामान्यीकरण गुण' होता है या (अशक्त ) सामान्यीकरण (डब्ल्यू एन) होता है यदि प्रत्येक वस्तु अशक्त रूप से सामान्य हो रही हो। एक वस्तु a 'दृढ़ता से सामान्य' होती है यदि a से प्रारंभ होने वाले पुनर्लेखन का प्रत्येक क्रम अंततः सामान्य रूप से समाप्त हो जाता है। एक सार पुनर्लेखन प्रणाली जोरदार सामान्यीकरण समाप्ति नोथेरियन है, या '(शसक्त) सामान्यीकरण संपत्ति' (एसएन) है यदि इसकी प्रत्येक वस्तु दृढ़ता से सामान्य हो रही है।<ref>{{cite journal |last1=Ohlebusch |first1=Enno |title=एब्स्ट्रैक्ट रिडक्शन मोडुलो ए इक्वैलेंस रिलेशन के लिए चर्च-रॉसर प्रमेय|journal=Rewriting Techniques and Applications |series=Lecture Notes in Computer Science |date=1998 |volume=1379 |page=18 |doi=10.1007/BFb0052358 |isbn=978-3-540-64301-2 |url=https://books.google.com/books?id=ESr6CAAAQBAJ&pg=PA18}}</ref>


एक पुनर्लेखन प्रणाली में सामान्य रूप गुण (एनएफ) होता है यदि सभी वस्तुओं के लिए a और सामान्य रूप b, b को पुनर्लेखन की एक श्रृंखला द्वारा a से पहुँचा जा सकता है और व्युत्क्रम पुनर्लेखन केवल तभी होता है जब a b तक कम हो जाता है। एक पुनर्लेखन प्रणाली में अद्वितीय सामान्य रूप गुण (यूएन) होता है यदि सभी सामान्य रूपों के लिए a, b ∈ S, a तक b से पुनर्लेखन की श्रृंखला द्वारा पहुँचा जा सकता है और व्युत्क्रम पुनर्लेखन केवल तभी होता है जब a, b के समान हो एक पुनर्लेखन प्रणाली में कमी के संबंध में विशिष्ट सामान्य रूप की संपत्ति होती है (UN<sup>→</sup>) यदि प्रत्येक पद को सामान्य रूपों a और b में कम करने के लिए, a, b के समान है।<ref name="NF">{{cite journal |last1=Klop |first1=J.W. |last2=de Vrijer |first2=R.C. |title=विशेषण जोड़ी के साथ लैम्ब्डा कैलकुलस के लिए अद्वितीय सामान्य रूप|journal=Information and Computation |date=February 1989 |volume=80 |issue=2 |pages=97–113 |doi=10.1016/0890-5401(89)90014-X |doi-access=free }}</ref>
एक पुनर्लेखन प्रणाली में सामान्य रूप गुण (एनएफ) होता है यदि सभी वस्तुओं के लिए a और सामान्य रूप b, b को पुनर्लेखन की एक श्रृंखला द्वारा a से पहुँचा जा सकता है और व्युत्क्रम पुनर्लेखन केवल तभी होता है जब a b तक कम हो जाता है। एक पुनर्लेखन प्रणाली में अद्वितीय सामान्य रूप गुण (यूएन) होता है यदि सभी सामान्य रूपों के लिए a, b ∈ S, a तक b से पुनर्लेखन की श्रृंखला द्वारा पहुँचा जा सकता है और व्युत्क्रम पुनर्लेखन केवल तभी होता है जब a, b के समान हो एक पुनर्लेखन प्रणाली में कमी के संबंध में विशिष्ट सामान्य रूप की संपत्ति होती है (UN<sup>→</sup>) यदि प्रत्येक पद को सामान्य रूपों a और b में कम करने के लिए, a, b के समान है।<ref name="NF">{{cite journal |last1=Klop |first1=J.W. |last2=de Vrijer |first2=R.C. |title=विशेषण जोड़ी के साथ लैम्ब्डा कैलकुलस के लिए अद्वितीय सामान्य रूप|journal=Information and Computation |date=February 1989 |volume=80 |issue=2 |pages=97–113 |doi=10.1016/0890-5401(89)90014-X |doi-access=free }}</ref>
Line 15: Line 15:
यह खंड कुछ प्रसिद्ध परिणाम प्रस्तुत करता है। सबसे पहले, SN का अर्थ WN है।<ref>{{cite web |title=logic - What is the difference between strong normalization and weak normalization in the context of rewrite systems? |url=https://cs.stackexchange.com/questions/68080/what-is-the-difference-between-strong-normalization-and-weak-normalization-in-th |website=Computer Science Stack Exchange |access-date=12 September 2021}}</ref>
यह खंड कुछ प्रसिद्ध परिणाम प्रस्तुत करता है। सबसे पहले, SN का अर्थ WN है।<ref>{{cite web |title=logic - What is the difference between strong normalization and weak normalization in the context of rewrite systems? |url=https://cs.stackexchange.com/questions/68080/what-is-the-difference-between-strong-normalization-and-weak-normalization-in-th |website=Computer Science Stack Exchange |access-date=12 September 2021}}</ref>


संगम (संक्षिप्त CR) का अर्थ है NF का अर्थ है UN का अर्थ है UN<sup>→</sup> उत्क्रम निहितार्थ सामान्यतः पकड़ में नहीं आते हैं।<sup><ref name="NF" /> {a→b,a→c,c→c,d→c,d→e} UN<sup>→</sup> है किंतु UN नहीं क्योंकि b=e और b,e सामान्य रूप हैं।{a→b,a→c,b→b} UN है किंतु NF नहीं है क्योंकि b=c, c एक सामान्य रूप है, और बी सी को कम नहीं करता है। {a→b,a→c,b→b,c→c} NF है क्योंकि कोई सामान्य रूप नहीं है किंतु CR नहीं है क्योंकि b और c को कम करता है, और b,c में कोई सामान्य कमी नहीं है।WN और UN<sup>→</sup> अर्थ संगम इसलिए CR, NF , UN और UN<sup>→</sup> यदि WN धारण करता है तो मेल खाता है।<ref>{{cite book |last1=Ohlebusch |first1=Enno |title=टर्म पुनर्लेखन में उन्नत विषय|date=17 April 2013 |publisher=Springer Science & Business Media |isbn=978-1-4757-3661-8 |pages=13–14 |url=https://books.google.com/books?id=jSHaBwAAQBAJ&pg=PA13 |language=en}}</ref>
संगम (संक्षिप्त CR) का अर्थ है NF का अर्थ है UN का अर्थ है UN<sup>→</sup> उत्क्रम निहितार्थ सामान्यतः पकड़ में नहीं आते हैं।<sup><ref name="NF" /> {a→b,a→c,c→c,d→c,d→e} UN<sup>→ है किंतु UN नहीं क्योंकि b=e और b,e सामान्य रूप हैं।{a→b,a→c,b→b} UN है किंतु NF नहीं है क्योंकि b=c, c एक सामान्य रूप है, और बी सी को कम नहीं करता है। {a→b,a→c,b→b,c→c} NF है क्योंकि कोई सामान्य रूप नहीं है किंतु CR नहीं है क्योंकि b और c को कम करता है, और b,c में कोई सामान्य कमी नहीं है।WN और UN<sup>→ अर्थ संगम इसलिए CR, NF , UN और UN<sup>→ यदि WN धारण करता है तो मेल खाता है।<ref>{{cite book |last1=Ohlebusch |first1=Enno |title=टर्म पुनर्लेखन में उन्नत विषय|date=17 April 2013 |publisher=Springer Science & Business Media |isbn=978-1-4757-3661-8 |pages=13–14 |url=https://books.google.com/books?id=jSHaBwAAQBAJ&pg=PA13 |language=en}}</ref>
== उदाहरण ==
== उदाहरण ==


एक उदाहरण यह है कि अंकगणितीय व्यंजकों को सरल बनाने से एक संख्या उत्पन्न होती है - अंकगणित में सभी संख्याएँ सामान्य रूप होती हैं। एक उल्लेखनीय तथ्य यह है कि सभी अंकगणितीय अभिव्यक्तियों का एक अद्वितीय मान है इसलिए पुनर्लेखन प्रणाली दृढ़ता से सामान्यीकृत और संगम है:<ref>{{cite book |author1=Terese |title=टर्म पुनर्लेखन प्रणाली|date=2003 |publisher=Cambridge University Press |location=Cambridge, UK |isbn=0-521-39115-6 |page=1}}</ref>
एक उदाहरण यह है कि अंकगणितीय व्यंजकों को सरल बनाने से एक संख्या उत्पन्न होती है - अंकगणित में सभी संख्याएँ सामान्य रूप होती हैं। एक उल्लेखनीय तथ्य यह है कि सभी अंकगणितीय अभिव्यक्तियों का एक अद्वितीय मान है इसलिए पुनर्लेखन प्रणाली दृढ़ता से सामान्यीकृत और संगम है:<ref>{{cite book |author1=Terese |title=टर्म पुनर्लेखन प्रणाली|date=2003 |publisher=Cambridge University Press |location=Cambridge, UK |isbn=0-521-39115-6 |page=1}}</ref>
:(3 + 5) * (1 + 2) ⇒ 8 * (1 + 2) ⇒ 8 * 3 ⇒ 24
:(3 + 5) * (1 + 2) ⇒ 8 * (1 + 2) ⇒ 8 * 3 ⇒ 24
:(3 + 5) * (1 + 2) ⇒ (3 + 5) * 3 ⇒ 3*3 + 5*3 ⇒ 9 + 5*3 ⇒ 9 + 15 ⇒ 24
:(3 + 5) * (1 + 2) ⇒ (3 + 5) * 3 ⇒ 3*3 + 5*3 ⇒ 9 + 5*3 ⇒ 9 + 15 ⇒ 24


गैर-सामान्यीकृत प्रणालियों के उदाहरणों (अशक्त या दृढ़ता से नहीं) में अनंत तक गिनती (1 ⇒ 2 ⇒ 3 ⇒ ...) और लूप जैसे [[Collatz अनुमान|कोलात्ज़ अनुमान]] के परिवर्तन कार्य (1 ⇒ 2 ⇒ 4 ⇒ 1 ⇒ ...) सम्मिलित हैं। यदि कोलात्ज़ रूपांतरण के कोई अन्य लूप हैं तो यह एक विवर्त समस्या है)।<ref>{{cite book |author1=Terese |title=टर्म पुनर्लेखन प्रणाली|date=2003 |publisher=Cambridge University Press |location=Cambridge, UK |isbn=0-521-39115-6 |page=2}}</ref> एक अन्य उदाहरण एकल-नियम प्रणाली है { { ''r''(''x'',''y'') → ''r''(''y'',''x'') }, जिसमें किसी भी शब्द से कोई सामान्य गुण नहीं है, उदा। r(4,2) एक एकल पुनर्लेखन क्रम प्रारंभ होता है, अर्थात ''r''(4,2) → ''r''(2,4) → ''r''(4,2) → ''r''(2,4) → ..., जो असीम रूप से लंबा है। यह मोडुलो [[ क्रमविनिमेयता | क्रमविनिमेयता]] को फिर से लिखने के विचार की ओर ले जाता है जहां कोई नियम सामान्य रूप में होता है यदि कोई नियम नहीं है किंतु कम्यूटेटिविटी प्रयुक्त होती है।<ref>{{cite book| first1=Nachum|last1=Dershowitz|first2=Jean-Pierre|last2=Jouannaud| chapter=6. Rewrite Systems|title=सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका| year=1990| volume=B| publisher=Elsevier| editor=Jan van Leeuwen| editor-link=Jan van Leeuwen| series=सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका|citeseerx=10.1.1.64.3114|isbn=0-444-88074-7|pages=9–10}}</ref>
गैर-सामान्यीकृत प्रणालियों के उदाहरणों (अशक्त या दृढ़ता से नहीं) में अनंत तक गिनती (1 ⇒ 2 ⇒ 3 ⇒ ...) और लूप जैसे [[Collatz अनुमान|कोलात्ज़ अनुमान]] के परिवर्तन कार्य (1 ⇒ 2 ⇒ 4 ⇒ 1 ⇒ ...) सम्मिलित हैं। यदि कोलात्ज़ रूपांतरण के कोई अन्य लूप हैं तो यह एक विवर्त समस्या है)।<ref>{{cite book |author1=Terese |title=टर्म पुनर्लेखन प्रणाली|date=2003 |publisher=Cambridge University Press |location=Cambridge, UK |isbn=0-521-39115-6 |page=2}}</ref> एक अन्य उदाहरण एकल-नियम प्रणाली है { { ''r''(''x'',''y'') → ''r''(''y'',''x'') }, जिसमें किसी भी शब्द से कोई सामान्य गुण नहीं है, उदा। r(4,2) एक एकल पुनर्लेखन क्रम प्रारंभ होता है, अर्थात ''r''(4,2) → ''r''(2,4) → ''r''(4,2) → ''r''(2,4) → ..., जो असीम रूप से लंबा है। यह मोडुलो [[ क्रमविनिमेयता |क्रमविनिमेयता]] को फिर से लिखने के विचार की ओर ले जाता है जहां कोई नियम सामान्य रूप में होता है यदि कोई नियम नहीं है किंतु कम्यूटेटिविटी प्रयुक्त होती है।<ref>{{cite book| first1=Nachum|last1=Dershowitz|first2=Jean-Pierre|last2=Jouannaud| chapter=6. Rewrite Systems|title=सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका| year=1990| volume=B| publisher=Elsevier| editor=Jan van Leeuwen| editor-link=Jan van Leeuwen| series=सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका|citeseerx=10.1.1.64.3114|isbn=0-444-88074-7|pages=9–10}}</ref>


[[File:Cyclic_locally,_but_not_globally_confluent_rewrite_system.png|thumb|अशक्त किंतु दृढ़ता से पुनर्लेखन प्रणाली को सामान्य नहीं कर रहा है<ref name="Dershowitz.Jouannaud.1990.Fig2">{{cite book | isbn=0-444-88074-7 | editor=Jan van Leeuwen | title=औपचारिक मॉडल और शब्दार्थ| publisher=Elsevier | series=Handbook of Theoretical Computer Science | volume=B | year=1990 | author=N. Dershowitz and J.-P. Jouannaud | contribution=Rewrite Systems | page=268}}</ref>]]
[[File:Cyclic_locally,_but_not_globally_confluent_rewrite_system.png|thumb|अशक्त किंतु दृढ़ता से पुनर्लेखन प्रणाली को सामान्य नहीं कर रहा है<ref name="Dershowitz.Jouannaud.1990.Fig2">{{cite book | isbn=0-444-88074-7 | editor=Jan van Leeuwen | title=औपचारिक मॉडल और शब्दार्थ| publisher=Elsevier | series=Handbook of Theoretical Computer Science | volume=B | year=1990 | author=N. Dershowitz and J.-P. Jouannaud | contribution=Rewrite Systems | page=268}}</ref>]]


 
प्रणाली {''b'' → ''a'', ''b'' → ''c'', ''c'' → ''b'', ''c'' → ''d''} (चित्रित) अशक्त सामान्यीकरण का एक उदाहरण है, किंतु दृढ़ता से सामान्यीकरण प्रणाली नहीं है। ''a'' और ''d'' सामान्य रूप हैं, और ''b'' और ''c'' को ''a'' या ''d'' में घटाया जा सकता है, किंतु अनंत कमी ''b'' → ''c'' → ''b'' → ''c'' → ... का अर्थ है कि न तो ''b'' और न ही ''c'' दृढ़ता से सामान्यीकरण कर रहा है।
प्रणाली {''b'' → ''a'', ''b'' → ''c'', ''c'' → ''b'', ''c'' → ''d''} (चित्रित) अशक्त सामान्यीकरण का एक उदाहरण है, किंतु दृढ़ता से सामान्यीकरण प्रणाली नहीं है। ''a'' और ''d'' सामान्य रूप हैं, और ''b'' और ''c'' को ''a'' या ''d'' में घटाया जा सकता है, किंतु अनंत कमी ''b'' → ''c'' → ''b'' → ''c'' → ... का अर्थ है कि न तो ''b'' और न ही ''c'' दृढ़ता से सामान्यीकरण कर रहा है।


=== अनटाइप्ड [[लैम्ब्डा कैलकुलस]] ===
=== अनटाइप्ड [[लैम्ब्डा कैलकुलस]] ===
Line 33: Line 32:


: <math>(\mathbf{\lambda} x . x x x) t \rightarrow t t t</math>
: <math>(\mathbf{\lambda} x . x x x) t \rightarrow t t t</math>
किंतु विचार करें कि जब हम <math>\lambda x . x x x</math> प्रयुक्त करते हैं तो क्या होता है खुद के लिए:
किंतु विचार करें कि जब हम <math>\lambda x . x x x</math> प्रयुक्त करते हैं तो क्या होता है खुद के लिए:


: <math>\begin{align}
: <math>\begin{align}
Line 53: Line 52:


सामान्यीकरण संपत्ति के साथ एक लैम्ब्डा कैलकुलस प्रणाली को एक प्रोग्रामिंग भाषा के रूप में देखा जा सकता है, जिसमें संपत्ति का प्रत्येक कार्यक्रम [[समाप्ति विश्लेषण]] होता है। चूँकि यह एक बहुत ही उपयोगी संपत्ति है इसमें एक खामी है: सामान्यीकरण संपत्ति के साथ एक प्रोग्रामिंग भाषा [[ट्यूरिंग पूर्ण]] नहीं हो सकती है, अन्यथा कोई प्रोग्राम के प्रकार की जांच करके हॉल्टिंग समस्या को हल कर सकता है। इसका अर्थ यह है कि ऐसे संगणनीय कार्य हैं जिन्हें केवल टाइप किए गए लैम्ब्डा कैलकुलस में परिभाषित नहीं किया जा सकता है, और इसी तरह निर्माण और प्रणाली एफ के कैलकुलस के लिए एक विशिष्ट उदाहरण कुल प्रोग्रामिंग भाषा में एक स्व-दुभाषिया का है।<ref>{{cite book |last1=Riolo |first1=Rick |last2=Worzel |first2=William P. |last3=Kotanchek |first3=Mark |title=जेनेटिक प्रोग्रामिंग सिद्धांत और अभ्यास बारहवीं|date=4 June 2015 |publisher=Springer |isbn=978-3-319-16030-6|page=59 |url=https://books.google.com/books?id=rfDLCQAAQBAJ&pg=PA59 |access-date=8 September 2021 |language=en}}</ref>
सामान्यीकरण संपत्ति के साथ एक लैम्ब्डा कैलकुलस प्रणाली को एक प्रोग्रामिंग भाषा के रूप में देखा जा सकता है, जिसमें संपत्ति का प्रत्येक कार्यक्रम [[समाप्ति विश्लेषण]] होता है। चूँकि यह एक बहुत ही उपयोगी संपत्ति है इसमें एक खामी है: सामान्यीकरण संपत्ति के साथ एक प्रोग्रामिंग भाषा [[ट्यूरिंग पूर्ण]] नहीं हो सकती है, अन्यथा कोई प्रोग्राम के प्रकार की जांच करके हॉल्टिंग समस्या को हल कर सकता है। इसका अर्थ यह है कि ऐसे संगणनीय कार्य हैं जिन्हें केवल टाइप किए गए लैम्ब्डा कैलकुलस में परिभाषित नहीं किया जा सकता है, और इसी तरह निर्माण और प्रणाली एफ के कैलकुलस के लिए एक विशिष्ट उदाहरण कुल प्रोग्रामिंग भाषा में एक स्व-दुभाषिया का है।<ref>{{cite book |last1=Riolo |first1=Rick |last2=Worzel |first2=William P. |last3=Kotanchek |first3=Mark |title=जेनेटिक प्रोग्रामिंग सिद्धांत और अभ्यास बारहवीं|date=4 June 2015 |publisher=Springer |isbn=978-3-319-16030-6|page=59 |url=https://books.google.com/books?id=rfDLCQAAQBAJ&pg=PA59 |access-date=8 September 2021 |language=en}}</ref>
 
== यह भी देखें                                                                                                                                   ==
'''यह एक बहुत ही उपयोगी संपत्ति है इसमें एक खामी है: सामान्यीकरण संपत्ति के साथ एक प्रोग्रामिंग भाषा [[ट्यूरिंग पूर्ण]] नहीं हो सकती है, अन्यथा कोई प्रोग्राम के प्रकार की जांच करके हॉल्टिंग सम'''
== यह भी देखें                       ==
* [[कानूनी फॉर्म]]
* [[कानूनी फॉर्म]]
* टाइप लैम्ब्डा कैलकुस
* टाइप लैम्ब्डा कैलकुस
Line 71: Line 68:
{{reflist}}
{{reflist}}


{{DEFAULTSORT:Normal Form (Term Rewriting)}}[[Category: संगणनीयता सिद्धांत]] [[Category: औपचारिक भाषाएँ]] [[Category: पुनर्लेखन प्रणाली]] [[Category: लैम्ब्डा कैलकुलस]] [[Category: कंप्यूटर विज्ञान में तर्क]]
{{DEFAULTSORT:Normal Form (Term Rewriting)}}
 
 


[[Category: Machine Translated Page]]
[[Category:CS1 English-language sources (en)]]
[[Category:Created On 18/05/2023]]
[[Category:Created On 18/05/2023|Normal Form (Term Rewriting)]]
[[Category:Lua-based templates|Normal Form (Term Rewriting)]]
[[Category:Machine Translated Page|Normal Form (Term Rewriting)]]
[[Category:Pages with script errors|Normal Form (Term Rewriting)]]
[[Category:Templates Vigyan Ready|Normal Form (Term Rewriting)]]
[[Category:Templates that add a tracking category|Normal Form (Term Rewriting)]]
[[Category:Templates that generate short descriptions|Normal Form (Term Rewriting)]]
[[Category:Templates using TemplateData|Normal Form (Term Rewriting)]]
[[Category:औपचारिक भाषाएँ|Normal Form (Term Rewriting)]]
[[Category:कंप्यूटर विज्ञान में तर्क|Normal Form (Term Rewriting)]]
[[Category:पुनर्लेखन प्रणाली|Normal Form (Term Rewriting)]]
[[Category:लैम्ब्डा कैलकुलस|Normal Form (Term Rewriting)]]
[[Category:संगणनीयता सिद्धांत|Normal Form (Term Rewriting)]]

Latest revision as of 14:53, 12 June 2023

सार पुनर्लेखन में[1] एक वस्तु सामान्य रूप में होती है यदि इसे आगे फिर से नहीं लिखा जा सकता है अर्थात यह अप्रासंगिक है। पुनर्लेखन प्रणाली के आधार पर एक वस्तु कई सामान्य रूपों में फिर से लिख सकती है या पूर्ण रूप से भी नहीं पुनर्लेखन प्रणालियों के कई गुण सामान्य रूपों से संबंधित हैं।

परिभाषाएँ

औपचारिक रूप से कहा गया है, यदि (A,→) एक अमूर्त पुनर्लेखन प्रणाली या परिभाषा है, x∈A 'सामान्य रूप' में है यदि कोई y∈A उपस्थित नहीं है जैसे कि x→y, यानी x एक अप्रासंगिक शब्द है।

एक वस्तु a 'अशक्त रूप से सामान्यीकरण' है यदि वहाँ से प्रारंभ होने वाले पुनर्लेखन का कम से कम एक विशेष क्रम उपस्थित है जो अंततः एक सामान्य रूप देता है। एक पुनर्लेखन प्रणाली में 'अशक्त सामान्यीकरण गुण' होता है या (अशक्त ) सामान्यीकरण (डब्ल्यू एन) होता है यदि प्रत्येक वस्तु अशक्त रूप से सामान्य हो रही हो। एक वस्तु a 'दृढ़ता से सामान्य' होती है यदि a से प्रारंभ होने वाले पुनर्लेखन का प्रत्येक क्रम अंततः सामान्य रूप से समाप्त हो जाता है। एक सार पुनर्लेखन प्रणाली जोरदार सामान्यीकरण समाप्ति नोथेरियन है, या '(शसक्त) सामान्यीकरण संपत्ति' (एसएन) है यदि इसकी प्रत्येक वस्तु दृढ़ता से सामान्य हो रही है।[2]

एक पुनर्लेखन प्रणाली में सामान्य रूप गुण (एनएफ) होता है यदि सभी वस्तुओं के लिए a और सामान्य रूप b, b को पुनर्लेखन की एक श्रृंखला द्वारा a से पहुँचा जा सकता है और व्युत्क्रम पुनर्लेखन केवल तभी होता है जब a b तक कम हो जाता है। एक पुनर्लेखन प्रणाली में अद्वितीय सामान्य रूप गुण (यूएन) होता है यदि सभी सामान्य रूपों के लिए a, b ∈ S, a तक b से पुनर्लेखन की श्रृंखला द्वारा पहुँचा जा सकता है और व्युत्क्रम पुनर्लेखन केवल तभी होता है जब a, b के समान हो एक पुनर्लेखन प्रणाली में कमी के संबंध में विशिष्ट सामान्य रूप की संपत्ति होती है (UN→) यदि प्रत्येक पद को सामान्य रूपों a और b में कम करने के लिए, a, b के समान है।[3]


परिणाम

यह खंड कुछ प्रसिद्ध परिणाम प्रस्तुत करता है। सबसे पहले, SN का अर्थ WN है।[4]

संगम (संक्षिप्त CR) का अर्थ है NF का अर्थ है UN का अर्थ है UN→ उत्क्रम निहितार्थ सामान्यतः पकड़ में नहीं आते हैं।[3] {a→b,a→c,c→c,d→c,d→e} UN→ है किंतु UN नहीं क्योंकि b=e और b,e सामान्य रूप हैं।{a→b,a→c,b→b} UN है किंतु NF नहीं है क्योंकि b=c, c एक सामान्य रूप है, और बी सी को कम नहीं करता है। {a→b,a→c,b→b,c→c} NF है क्योंकि कोई सामान्य रूप नहीं है किंतु CR नहीं है क्योंकि b और c को कम करता है, और b,c में कोई सामान्य कमी नहीं है।WN और UN→ अर्थ संगम इसलिए CR, NF , UN और UN→ यदि WN धारण करता है तो मेल खाता है।[5]

उदाहरण

एक उदाहरण यह है कि अंकगणितीय व्यंजकों को सरल बनाने से एक संख्या उत्पन्न होती है - अंकगणित में सभी संख्याएँ सामान्य रूप होती हैं। एक उल्लेखनीय तथ्य यह है कि सभी अंकगणितीय अभिव्यक्तियों का एक अद्वितीय मान है इसलिए पुनर्लेखन प्रणाली दृढ़ता से सामान्यीकृत और संगम है:[6]

(3 + 5) * (1 + 2) ⇒ 8 * (1 + 2) ⇒ 8 * 3 ⇒ 24
(3 + 5) * (1 + 2) ⇒ (3 + 5) * 3 ⇒ 3*3 + 5*3 ⇒ 9 + 5*3 ⇒ 9 + 15 ⇒ 24

गैर-सामान्यीकृत प्रणालियों के उदाहरणों (अशक्त या दृढ़ता से नहीं) में अनंत तक गिनती (1 ⇒ 2 ⇒ 3 ⇒ ...) और लूप जैसे कोलात्ज़ अनुमान के परिवर्तन कार्य (1 ⇒ 2 ⇒ 4 ⇒ 1 ⇒ ...) सम्मिलित हैं। यदि कोलात्ज़ रूपांतरण के कोई अन्य लूप हैं तो यह एक विवर्त समस्या है)।[7] एक अन्य उदाहरण एकल-नियम प्रणाली है { { r(x,y) → r(y,x) }, जिसमें किसी भी शब्द से कोई सामान्य गुण नहीं है, उदा। r(4,2) एक एकल पुनर्लेखन क्रम प्रारंभ होता है, अर्थात r(4,2) → r(2,4) → r(4,2) → r(2,4) → ..., जो असीम रूप से लंबा है। यह मोडुलो क्रमविनिमेयता को फिर से लिखने के विचार की ओर ले जाता है जहां कोई नियम सामान्य रूप में होता है यदि कोई नियम नहीं है किंतु कम्यूटेटिविटी प्रयुक्त होती है।[8]

अशक्त किंतु दृढ़ता से पुनर्लेखन प्रणाली को सामान्य नहीं कर रहा है[9]

प्रणाली {b → a, b → c, c → b, c → d} (चित्रित) अशक्त सामान्यीकरण का एक उदाहरण है, किंतु दृढ़ता से सामान्यीकरण प्रणाली नहीं है। a और d सामान्य रूप हैं, और b और c को a या d में घटाया जा सकता है, किंतु अनंत कमी b → c → b → c → ... का अर्थ है कि न तो b और न ही c दृढ़ता से सामान्यीकरण कर रहा है।

अनटाइप्ड लैम्ब्डा कैलकुलस

शुद्ध अप्रकाशित लैम्ब्डा कैलकुलस शसक्त सामान्यीकरण संपत्ति को संतुष्ट नहीं करता है, और अशक्त सामान्यीकरण संपत्ति को भी नहीं शब्द पर विचार करें। (अनुप्रयोग बाएं साहचर्य है) इसका निम्नलिखित पुनर्लेखन नियम है: किसी भी पद के लिए,

किंतु विचार करें कि जब हम प्रयुक्त करते हैं तो क्या होता है खुद के लिए:

इसलिए शब्द दृढ़ता से सामान्यीकरण नहीं कर रहा है। और यह केवल कमी का क्रम है इसलिए यह अशक्त रूप से सामान्यीकरण भी नहीं कर रहा है।

लैम्ब्डा कैलकुलस टाइप किया

टाइप किए गए लैम्ब्डा कैलकुलस की विभिन्न प्रणालियाँ जिनमें सामान्य रूप से टाइप किए गए लैम्ब्डा कैलकुलस जीन-यवेस गिरार्ड के प्रणाली एफ और थिएरी कोक्वांड के निर्माण के कैलकुलस सम्मिलित हैं दृढ़ता से सामान्यीकरण कर रहे हैं।

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

यह भी देखें

टिप्पणियाँ


संदर्भ

  1. ↑ Franz Baader; Tobias Nipkow (1998). टर्म पुनर्लेखन और वह सब. Cambridge University Press. ISBN 9780521779203.
  2. ↑ Ohlebusch, Enno (1998). "एब्स्ट्रैक्ट रिडक्शन मोडुलो ए इक्वैलेंस रिलेशन के लिए चर्च-रॉसर प्रमेय". Rewriting Techniques and Applications. Lecture Notes in Computer Science. 1379: 18. doi:10.1007/BFb0052358. ISBN 978-3-540-64301-2.
  3. ↑ 3.0 3.1 Klop, J.W.; de Vrijer, R.C. (February 1989). "विशेषण जोड़ी के साथ लैम्ब्डा कैलकुलस के लिए अद्वितीय सामान्य रूप". Information and Computation. 80 (2): 97–113. doi:10.1016/0890-5401(89)90014-X.
  4. ↑ "logic - What is the difference between strong normalization and weak normalization in the context of rewrite systems?". Computer Science Stack Exchange. Retrieved 12 September 2021.
  5. ↑ Ohlebusch, Enno (17 April 2013). टर्म पुनर्लेखन में उन्नत विषय (in English). Springer Science & Business Media. pp. 13–14. ISBN 978-1-4757-3661-8.
  6. ↑ Terese (2003). टर्म पुनर्लेखन प्रणाली. Cambridge, UK: Cambridge University Press. p. 1. ISBN 0-521-39115-6.
  7. ↑ Terese (2003). टर्म पुनर्लेखन प्रणाली. Cambridge, UK: Cambridge University Press. p. 2. ISBN 0-521-39115-6.
  8. ↑ Dershowitz, Nachum; Jouannaud, Jean-Pierre (1990). "6. Rewrite Systems". In Jan van Leeuwen (ed.). सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका. सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका. Vol. B. Elsevier. pp. 9–10. CiteSeerX 10.1.1.64.3114. ISBN 0-444-88074-7.
  9. ↑ N. Dershowitz and J.-P. Jouannaud (1990). "Rewrite Systems". In Jan van Leeuwen (ed.). औपचारिक मॉडल और शब्दार्थ. Handbook of Theoretical Computer Science. Vol. B. Elsevier. p. 268. ISBN 0-444-88074-7.
  10. ↑ Riolo, Rick; Worzel, William P.; Kotanchek, Mark (4 June 2015). जेनेटिक प्रोग्रामिंग सिद्धांत और अभ्यास बारहवीं (in English). Springer. p. 59. ISBN 978-3-319-16030-6. Retrieved 8 September 2021.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=सामान्य_रूप_(सार_पुनर्लेखन)&oldid=184648’