नियमित भाषा: Difference between revisions

From Vigyanwiki
No edit summary
 
(9 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Short description|Formal language that can be expressed using a regular expression}}
{{Short description|Formal language that can be expressed using a regular expression}}
{{For|natural language that is regulated|List of language regulators}}
[[सैद्धांतिक कंप्यूटर विज्ञान]] और [[औपचारिक भाषा सिद्धांत]] में, एक नियमित भाषा (तर्कसंगत भाषा भी कहा जाता है)<ref name="Mitkov2003"/><ref name="Lawson2003"/>एक [[औपचारिक भाषा]] है जिसे एक [[नियमित अभिव्यक्ति]] द्वारा परिभाषित किया जा सकता है, सैद्धांतिक कंप्यूटर विज्ञान में सख्त अर्थ में (विपरीत रूप से) कई आधुनिक रेगुलर एक्सप्रेशन इंजन, जो उन विशेषताओं से संवर्धित हैं जो गैर-नियमित भाषाओं की पहचान की अनुमति देते हैं)।
{{Redirect|Kleene's theorem|his theorems for recursive functions|Kleene's recursion theorem}}
[[सैद्धांतिक कंप्यूटर विज्ञान]] और [[औपचारिक भाषा सिद्धांत]] में, एक नियमित भाषा (तर्कसंगत भाषा भी कहा जाता है)<ref name="Mitkov2003"/><ref name="Lawson2003"/>एक [[औपचारिक भाषा]] है जिसे एक [[नियमित अभिव्यक्ति]] द्वारा परिभाषित किया जा सकता है, सैद्धांतिक कंप्यूटर विज्ञान में सख्त अर्थ में (कई आधुनिक नियमित अभिव्यक्ति इंजनों के विपरीत, जो नियमित अभिव्यक्ति हैं # गैर-नियमित भाषाओं के लिए पैटर्न जो गैर-नियमित भाषाओं की पहचान की अनुमति देते हैं ).


वैकल्पिक रूप से, एक नियमित भाषा को [[परिमित automaton]] द्वारा मान्यता प्राप्त भाषा के रूप में परिभाषित किया जा सकता है। रेगुलर एक्सप्रेशंस और परिमित ऑटोमेटा की समानता को क्लेन के प्रमेय के रूप में जाना जाता है<ref name="RozenbergSalomaa1997">{{cite book|editor1=Grzegorz Rozenberg |editor2=Arto Salomaa |title=Handbook of Formal Languages: Volume 1. Word, Language, Grammar|chapter-url=https://books.google.com/books?id=yQ59ojndUt4C&pg=PA41|year=1997|publisher=Springer|isbn=978-3-540-60420-4|page=41|author=Sheng Yu|chapter=Regular languages}}</ref> (अमेरिकी गणितज्ञ [[स्टीफन कोल क्लेन]] के बाद)। [[चॉम्स्की पदानुक्रम]] में, नियमित भाषाएं [[नियमित व्याकरण]] द्वारा उत्पन्न भाषाएं होती हैं | टाइप -3 व्याकरण।
वैकल्पिक रूप से, एक नियमित भाषा को [[परिमित automaton|परिमित ऑटोमेशन]] द्वारा मान्यता प्राप्त भाषा के रूप में परिभाषित किया जा सकता है। रेगुलर एक्सप्रेशंस और परिमित ऑटोमेटा की समानता को क्लेन के प्रमेय के रूप में जाना जाता है<ref name="RozenbergSalomaa1997">{{cite book|editor1=Grzegorz Rozenberg |editor2=Arto Salomaa |title=Handbook of Formal Languages: Volume 1. Word, Language, Grammar|chapter-url=https://books.google.com/books?id=yQ59ojndUt4C&pg=PA41|year=1997|publisher=Springer|isbn=978-3-540-60420-4|page=41|author=Sheng Yu|chapter=Regular languages}}</ref> (अमेरिकी गणितज्ञ [[स्टीफन कोल क्लेन]] के बाद)। [[चॉम्स्की पदानुक्रम]] में, नियमित भाषाएं टाइप -3 व्याकरण [[नियमित व्याकरण]] द्वारा उत्पन्न भाषाएं होती हैं |


== औपचारिक परिभाषा ==
== औपचारिक परिभाषा ==
Line 19: Line 17:
सभी परिमित भाषाएँ नियमित हैं; विशेष रूप से [[खाली स्ट्रिंग]] भाषा {ε} = Ø* नियमित है। अन्य विशिष्ट उदाहरणों में वर्णमाला {a, b} पर सभी स्ट्रिंग्स वाली भाषा शामिल है, जिसमें a की संख्या भी शामिल है, या भाषा में सभी स्ट्रिंग्स शामिल हैं: कई a के बाद कई b हैं।
सभी परिमित भाषाएँ नियमित हैं; विशेष रूप से [[खाली स्ट्रिंग]] भाषा {ε} = Ø* नियमित है। अन्य विशिष्ट उदाहरणों में वर्णमाला {a, b} पर सभी स्ट्रिंग्स वाली भाषा शामिल है, जिसमें a की संख्या भी शामिल है, या भाषा में सभी स्ट्रिंग्स शामिल हैं: कई a के बाद कई b हैं।


एक भाषा का एक सरल उदाहरण जो नियमित नहीं है, स्ट्रिंग्स का सेट है {ए<sup>एन</sup>बी<sup>एन</sup> | एन ≥ 0}।<ref>Eilenberg (1974), p. 16 (Example II, 2.8) and p. 25 (Example II, 5.2).</ref> सहज रूप से, इसे परिमित automaton के साथ पहचाना नहीं जा सकता है, क्योंकि एक परिमित automaton में परिमित स्मृति होती है और यह a की सटीक संख्या को याद नहीं रख सकती है। इस तथ्य को कठोरता से सिद्ध करने की तकनीकों को चॉम्स्की पदानुक्रम में #स्थान दिया गया है।
एक भाषा का एक सरल उदाहरण जो नियमित नहीं है, स्ट्रिंग्स का सेट है {a<sup>n</sup>b<sup>n</sup> | n ≥ 0}।<ref>Eilenberg (1974), p. 16 (Example II, 2.8) and p. 25 (Example II, 5.2).</ref> सहज रूप से, इसे परिमित ऑटोमेशन के साथ पहचाना नहीं जा सकता है, क्योंकि एक परिमित ऑटोमेशन में परिमित स्मृति होती है और यह a की सटीक संख्या को याद नहीं रख सकती है। इस तथ्य को कठोरता से सिद्ध करने की तकनीकों को चॉम्स्की पदानुक्रम में # स्थान दिया गया है।


== समकक्ष औपचारिकताएं ==
== समकक्ष औपचारिकताएं ==
Line 25: Line 23:
# यह एक नियमित अभिव्यक्ति की भाषा है (उपरोक्त परिभाषा के अनुसार)
# यह एक नियमित अभिव्यक्ति की भाषा है (उपरोक्त परिभाषा के अनुसार)
# यह एक गैर-नियतात्मक परिमित ऑटोमेटन (NFA) द्वारा स्वीकृत भाषा है<ref group=note>1. ⇒ 2. by [[Thompson's construction algorithm]]</ref><ref group=note>2. ⇒ 1. by [[Kleene's algorithm]] or using [[Arden's lemma]]</ref>
# यह एक गैर-नियतात्मक परिमित ऑटोमेटन (NFA) द्वारा स्वीकृत भाषा है<ref group=note>1. ⇒ 2. by [[Thompson's construction algorithm]]</ref><ref group=note>2. ⇒ 1. by [[Kleene's algorithm]] or using [[Arden's lemma]]</ref>
# यह [[नियतात्मक परिमित automaton]] (DFA) द्वारा स्वीकृत भाषा है<ref group=note>2. ⇒ 3. by the [[powerset construction]]</ref><ref group=note>3. ⇒ 2. since the former [[deterministic finite automaton#Formal definition|definition]] is stronger than the [[nondeterministic finite automaton#Formal definition|latter]]</ref>
# यह [[नियतात्मक परिमित automaton|नियतात्मक परिमित ऑटोमेशन]] (DFA) द्वारा स्वीकृत भाषा है<ref group=note>2. ⇒ 3. by the [[powerset construction]]</ref><ref group=note>3. ⇒ 2. since the former [[deterministic finite automaton#Formal definition|definition]] is stronger than the [[nondeterministic finite automaton#Formal definition|latter]]</ref>
# इसे एक नियमित व्याकरण द्वारा उत्पन्न किया जा सकता है<ref group=note>2. ⇒ 4. see Hopcroft, Ullman (1979), Theorem 9.2, p.219</ref><ref group=note>4. ⇒ 2. see Hopcroft, Ullman (1979), Theorem 9.1, p.218</ref>
# इसे एक नियमित व्याकरण द्वारा उत्पन्न किया जा सकता है<ref group=note>2. ⇒ 4. see Hopcroft, Ullman (1979), Theorem 9.2, p.219</ref><ref group=note>4. ⇒ 2. see Hopcroft, Ullman (1979), Theorem 9.1, p.218</ref>
# यह [[वैकल्पिक परिमित automaton]] द्वारा स्वीकृत भाषा है
# यह [[वैकल्पिक परिमित automaton|वैकल्पिक परिमित ऑटोमेशन]] द्वारा स्वीकृत भाषा है
# यह दो तरफा परिमित automaton द्वारा स्वीकृत भाषा है
# यह दो तरफा परिमित ऑटोमेशन द्वारा स्वीकृत भाषा है
# यह एक [[उपसर्ग व्याकरण]] द्वारा उत्पन्न किया जा सकता है
# यह एक [[उपसर्ग व्याकरण]] द्वारा उत्पन्न किया जा सकता है
# इसे रीड-ओनली [[ट्यूरिंग मशीन]] द्वारा स्वीकार किया जा सकता है
# इसे रीड-ओनली [[ट्यूरिंग मशीन]] द्वारा स्वीकार किया जा सकता है
# इसे [[मोनाडिक प्रेडिकेट कैलकुलस]] [[दूसरे क्रम का तर्क]] (बुची-एल्गोट-ट्रेखटेनब्रॉट प्रमेय) में परिभाषित किया जा सकता है।<ref>M. Weyer: Chapter 12 - Decidability of S1S and S2S, p. 219, Theorem 12.26. In: Erich Grädel, Wolfgang Thomas, Thomas Wilke (Eds.): Automata, Logics, and Infinite Games: A Guide to Current Research. [[Lecture Notes in Computer Science]] 2500, Springer 2002.</ref>
# इसे [[मोनाडिक प्रेडिकेट कैलकुलस]] [[दूसरे क्रम का तर्क]] (बुची-एल्गोट-ट्रेखटेनब्रॉट प्रमेय) में परिभाषित किया जा सकता है।<ref>M. Weyer: Chapter 12 - Decidability of S1S and S2S, p. 219, Theorem 12.26. In: Erich Grädel, Wolfgang Thomas, Thomas Wilke (Eds.): Automata, Logics, and Infinite Games: A Guide to Current Research. [[Lecture Notes in Computer Science]] 2500, Springer 2002.</ref>
# यह कुछ परिमित [[सिंटैक्टिक मोनोइड]] एम द्वारा पहचाने जाने योग्य सेट है, जिसका अर्थ है कि यह [[preimage]] है {w ∈ Σ<sup>*</सुप> | f(w) ∈ S } एक मोनॉइड समरूपता f: Σ के तहत एक परिमित मोनॉइड M के एक उपसमुच्चय का<sup>*</sup> → M इसके वर्णमाला पर [[मुक्त मोनोइड]] से<ref group=note>3. ⇔ 10. by the [[Myhill–Nerode theorem]]</ref>
# यह कुछ परिमित [[सिंटैक्टिक मोनोइड]] एम द्वारा पहचाने जाने योग्य सेट है, जिसका अर्थ है कि यह [[preimage]] है, {w ∈ Σ* f(w) ∈ S } एक मोनॉइड समरूपता f: Σ के तहत एक परिमित मोनॉइड M के एक उपसमुच्चय का<sup>* → M इसके वर्णमाला पर [[मुक्त मोनोइड]]<ref group="note">3. ⇔ 10. by the [[Myhill–Nerode theorem]]</ref>
# इसके वाक्यगत सर्वांगसमता के तुल्यता वर्गों की संख्या परिमित है।<ref group=note>''u''~''v'' is defined as: ''uw''∈''L'' if and only if ''vw''∈''L'' for all ''w''∈Σ<sup>*</sup></ref><ref group=note>3. ⇔ 11. see the proof in the ''[[Syntactic monoid#Syntactic equivalence|Syntactic monoid]]'' article, and see p.160 in {{cite book | last=Holcombe | first=W.M.L. | title=Algebraic automata theory | zbl=0489.68046 | series=Cambridge Studies in Advanced Mathematics | volume=1 | publisher=[[Cambridge University Press]] | year=1982 | isbn=0-521-60492-3 }}</ref> (यह संख्या एल को स्वीकार करने वाले [[डीएफए न्यूनीकरण]] के राज्यों की संख्या के बराबर है।)
# इसके वाक्यगत सर्वांगसमता के तुल्यता वर्गों की संख्या परिमित है।<ref group=note>''u''~''v'' is defined as: ''uw''∈''L'' if and only if ''vw''∈''L'' for all ''w''∈Σ<sup>*</sup></ref><ref group=note>3. ⇔ 11. see the proof in the ''[[Syntactic monoid#Syntactic equivalence|Syntactic monoid]]'' article, and see p.160 in {{cite book | last=Holcombe | first=W.M.L. | title=Algebraic automata theory | zbl=0489.68046 | series=Cambridge Studies in Advanced Mathematics | volume=1 | publisher=[[Cambridge University Press]] | year=1982 | isbn=0-521-60492-3 }}</ref> (यह संख्या एल को स्वीकार करने वाले [[डीएफए न्यूनीकरण]] के राज्यों की संख्या के बराबर है।)


गुण 10. और 11. नियमित भाषाओं को परिभाषित करने के लिए विशुद्ध रूप से बीजगणितीय दृष्टिकोण हैं; एक मोनोइड एम ⊆ Σ के लिए बयानों का एक समान सेट तैयार किया जा सकता है<sup>*</सुप>. इस मामले में, एम पर समानता पहचानने योग्य भाषा की अवधारणा की ओर ले जाती है।
गुण 10. और 11. नियमित भाषाओं को परिभाषित करने के लिए विशुद्ध रूप से बीजगणितीय दृष्टिकोण हैं; एक मोनोइड एम ⊆ Σ के लिए बयानों का एक समान सेट तैयार किया जा सकता है, इस मामले में, एम पर समानता पहचानने योग्य भाषा की अवधारणा की ओर ले जाती है।


कुछ लेखक उपरोक्त गुणों में से एक का उपयोग नियमित भाषाओं की वैकल्पिक परिभाषा के रूप में 1. से भिन्न करते हैं।
कुछ लेखक उपरोक्त गुणों में से एक का उपयोग नियमित भाषाओं की वैकल्पिक परिभाषा के रूप में 1. से भिन्न करते हैं।
Line 50: Line 48:
* नियमित संचालन: {{math|''K'' ∪ ''L''}}, संयोजन {{tmath|K \circ L}}, और क्लेन स्टार {{math|''L''<sup>*</sup>}}.<ref name=Sal27>Salomaa (1981) p.27</ref>
* नियमित संचालन: {{math|''K'' ∪ ''L''}}, संयोजन {{tmath|K \circ L}}, और क्लेन स्टार {{math|''L''<sup>*</sup>}}.<ref name=Sal27>Salomaa (1981) p.27</ref>
* भाषाओं के संचालन का अमूर्त परिवार: [[स्ट्रिंग समरूपता]], उलटा स्ट्रिंग समरूपता, और नियमित भाषाओं के साथ प्रतिच्छेदन। एक परिणाम के रूप में वे मनमाने ढंग से [[परिमित राज्य ट्रांसड्यूसर]] के तहत बंद हो जाते हैं, जैसे नियमित भाषा के साथ [[सही भागफल]] K / L। इससे भी अधिक, नियमित भाषाओं को मनमाने ढंग से भाषाओं के साथ बंद कर दिया जाता है: यदि L नियमित है तो L / K किसी भी K के लिए नियमित है।{{citation needed|date=January 2016}}
* भाषाओं के संचालन का अमूर्त परिवार: [[स्ट्रिंग समरूपता]], उलटा स्ट्रिंग समरूपता, और नियमित भाषाओं के साथ प्रतिच्छेदन। एक परिणाम के रूप में वे मनमाने ढंग से [[परिमित राज्य ट्रांसड्यूसर]] के तहत बंद हो जाते हैं, जैसे नियमित भाषा के साथ [[सही भागफल]] K / L। इससे भी अधिक, नियमित भाषाओं को मनमाने ढंग से भाषाओं के साथ बंद कर दिया जाता है: यदि L नियमित है तो L / K किसी भी K के लिए नियमित है।{{citation needed|date=January 2016}}
* रिवर्स (या मिरर इमेज) एल<sup>आर</सुप>.<ref>Hopcroft, Ullman (1979), Chapter 3, Exercise 3.4g, p. 72</ref> एल को पहचानने के लिए एक गैर-नियतात्मक परिमित automaton दिया गया, एल के लिए एक ऑटोमेटन<sup>R</sup> सभी संक्रमणों को उलट कर और आरंभिक और अंतिम अवस्थाओं को आपस में बदलकर प्राप्त किया जा सकता है। इसके परिणामस्वरूप कई प्रारंभिक अवस्थाएँ हो सकती हैं; उन्हें जोड़ने के लिए ε-संक्रमण का उपयोग किया जा सकता है।
* रिवर्स (या मिरर इमेज) एलआर<sup>R<ref>Hopcroft, Ullman (1979), Chapter 3, Exercise 3.4g, p. 72</ref> एल को पहचानने के लिए एक गैर-नियतात्मक परिमित ऑटोमेशन दिया गया, एल के लिए एक ऑटोमेटन सभी संक्रमणों को उलट कर और आरंभिक और अंतिम अवस्थाओं को आपस में बदलकर प्राप्त किया जा सकता है। इसके परिणामस्वरूप कई प्रारंभिक अवस्थाएँ हो सकती हैं; उन्हें जोड़ने के लिए ε-संक्रमण का उपयोग किया जा सकता है।


== निर्णायकता गुण ==
== निर्णायकता गुण ==
दो नियतात्मक परिमित ऑटोमेटा ए और बी को देखते हुए, यह निर्णायक है कि क्या वे एक ही भाषा को स्वीकार करते हैं।<ref>Hopcroft, Ullman (1979), Theorem 3.8, p.64; see also Theorem 3.10, p.67</ref>
दो निर्धारक परिमित ऑटोमेटा ए और बी को देखते हुए, यह तय किया जा सकता है कि वे एक ही भाषा को स्वीकार करते हैं या नहीं।<ref>Hopcroft, Ullman (1979), Theorem 3.8, p.64; see also Theorem 3.10, p.67</ref>
नतीजतन, # क्लोजर प्रॉपर्टीज क्लोजर प्रॉपर्टीज का उपयोग करते हुए, निम्नलिखित समस्याएं भी मनमाने ढंग से दिए गए नियतात्मक परिमित ऑटोमेटा ए और बी के लिए स्वीकृत भाषाओं एल के साथ निर्णायक हैं<sub>''A''</sub> और मैं<sub>''B''</sub>, क्रमश:<!---avoiding "L(A)" which hasn't been defined so far, and might be confused with the language variable "L" above--->
एक परिणाम के रूप में, उपरोक्त क्लोजर गुणों का उपयोग करते हुए, निम्नलिखित समस्याएं भी मनमाने ढंग से दिए गए नियतात्मक परिमित ऑटोमेटा ए और बी के लिए क्रमशः स्वीकृत भाषाओं एलए और एलबी के साथ निर्णायक हैं <sub>''A''</sub> और <sub>''B''</sub>, क्रमश:<!---avoiding "L(A)" which hasn't been defined so far, and might be confused with the language variable "L" above--->
* रोकथाम: एल है<sub>''A''</sub> ⊆ एल<sub>''B''</sub> ?<ref group=note>Check if ''L''<sub>''A''</sub> ∩ ''L''<sub>''B''</sub> = ''L''<sub>''A''</sub>. Deciding this property is [[NP-hard]] in general; see [[:File:RegSubsetNP.pdf]] for an illustration of the proof idea.</ref>
* रोकथाम: एल है<sub>''A''</sub> ⊆ एल<sub>''B''</sub> ?<ref group=note>Check if ''L''<sub>''A''</sub> ∩ ''L''<sub>''B''</sub> = ''L''<sub>''A''</sub>. Deciding this property is [[NP-hard]] in general; see [[:File:RegSubsetNP.pdf]] for an illustration of the proof idea.</ref>
* वियोग: एल है<sub>''A''</sub> ∩ एल<sub>''B''</sub> = {} ?
* वियोग: एल है<sub>''A''</sub> ∩ एल<sub>''B''</sub> = {} ?
Line 61: Line 59:
* सदस्यता: एक ∈ Σ दिया<sup>*</sup>, एक ∈ एल है<sub>''B''</sub> ?
* सदस्यता: एक ∈ Σ दिया<sup>*</sup>, एक ∈ एल है<sub>''B''</sub> ?
<!---todo: give complexity for each problem, discuss other formalisms than just DFA--->
<!---todo: give complexity for each problem, discuss other formalisms than just DFA--->
नियमित अभिव्यक्तियों के लिए, सार्वभौमिकता समस्या पहले से ही एक सिंगलटन वर्णमाला के लिए एनपी-पूर्ण है।<ref>Aho, Hopcroft, Ullman (1974), Exercise 10.14, p.401</ref>
नियमित अभिव्यक्तियों के लिए, सिंगलटन वर्णमाला के लिए सार्वभौमिकता समस्या पहले से ही एनपी-पूर्ण है।<ref>Aho, Hopcroft, Ullman (1974), Exercise 10.14, p.401</ref>
बड़े अक्षरों के लिए, वह समस्या PSPACE-पूर्ण # रेगुलर एक्सप्रेशन और ऑटोमेटा|PSPACE-पूर्ण है।<ref>Aho, Hopcroft, Ullman (1974), Theorem 10.14, p399</ref> यदि रेगुलर एक्सप्रेशंस को ए के साथ एक स्क्वेरिंग ऑपरेटर की अनुमति देने के लिए विस्तारित किया जाता है<sup>2</sup> एए के समान, अभी भी नियमित भाषाओं का वर्णन किया जा सकता है, लेकिन सार्वभौमिकता की समस्या में एक घातीय स्थान निचली सीमा है,<ref>Hopcroft, Ullman (1979), Theorem 13.15, p.351</ref><ref>{{cite book | url=https://people.csail.mit.edu/meyer/rsq.pdf |author1=A.R. Meyer  |author2=L.J. Stockmeyer  |name-list-style=amp | title=The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space | work=13th Annual IEEE Symp. on Switching and Automata Theory | pages=125–129 | date=Oct 1972 }}</ref><ref>{{cite book | url=https://esp.mit.edu/download/827dcf47cbc9cf4a3b04dbf773ea54fb/M3175_meyer-stockmeyer-word-probs.pdf |author1=L.J. Stockmeyer  |author2=A.R. Meyer  |name-list-style=amp | title=Word Problems Requiring Exponential Time | work=Proc. 5th ann. symp. on Theory of computing (STOC) | publisher=ACM | pages=1–9 | year=1973 }}</ref> और वास्तव में बहुपद-समय में कमी के संबंध में घातीय स्थान के लिए पूर्ण है।<ref>Hopcroft, Ullman (1979), Corollary p.353</ref>
बड़े अक्षरों के लिए, वह समस्या PSPACE-पूर्ण है। यदि रेगुलर एक्सप्रेशन और ऑटोमेटा|PSPACE-पूर्ण है।<ref>Aho, Hopcroft, Ullman (1974), Theorem 10.14, p399</ref> यदि रेगुलर एक्सप्रेशंस को एक स्क्वेरिंग ऑपरेटर की अनुमति देने के लिए विस्तारित किया जाता है, जिसमें "A2" को "AA" के रूप में दर्शाया जाता है, तो भी केवल नियमित भाषाओं का वर्णन किया जा सकता है, लेकिन सार्वभौमिकता की समस्या में एक घातीय स्थान निचली सीमा होती है,<ref>Hopcroft, Ullman (1979), Theorem 13.15, p.351</ref><ref>{{cite book | url=https://people.csail.mit.edu/meyer/rsq.pdf |author1=A.R. Meyer  |author2=L.J. Stockmeyer  |name-list-style=amp | title=The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space | work=13th Annual IEEE Symp. on Switching and Automata Theory | pages=125–129 | date=Oct 1972 }}</ref><ref>{{cite book | url=https://esp.mit.edu/download/827dcf47cbc9cf4a3b04dbf773ea54fb/M3175_meyer-stockmeyer-word-probs.pdf |author1=L.J. Stockmeyer  |author2=A.R. Meyer  |name-list-style=amp | title=Word Problems Requiring Exponential Time | work=Proc. 5th ann. symp. on Theory of computing (STOC) | publisher=ACM | pages=1–9 | year=1973 }}</ref> और वास्तव में बहुपद-समय में कमी के संबंध में घातांकी स्थान के लिए पूर्ण है।<ref>Hopcroft, Ullman (1979), Corollary p.353</ref>
एक निश्चित परिमित वर्णमाला के लिए, सभी भाषाओं के समुच्चय का सिद्धांत - एक साथ तार के साथ, एक भाषा में एक स्ट्रिंग की सदस्यता, और प्रत्येक वर्ण के लिए, वर्ण को एक स्ट्रिंग में जोड़ने के लिए एक फ़ंक्शन (और कोई अन्य संचालन नहीं) - निर्णायक है , और इसकी न्यूनतम प्रारंभिक तुल्यता में निश्चित रूप से नियमित भाषाएं शामिल हैं। बाइनरी वर्णमाला के लिए, सिद्धांत को [[S2S (गणित)]] कहा जाता है।<ref>{{cite book | last=Weyer | first=Mark | date=2002 | title=Automata, Logics, and Infinite Games |chapter=Decidability of S1S and S2S | series=Lecture Notes in Computer Science | volume=2500 | pages=207–230 |chapter-url=https://link.springer.com/chapter/10.1007/3-540-36387-4_12 | doi=10.1007/3-540-36387-4_12 | publisher=Springer| isbn=978-3-540-00388-5 }}</ref>
एक निश्चित परिमित वर्णमाला के लिए, सभी भाषाओं के समुच्चय का सिद्धांत - एक साथ तार के साथ, एक भाषा में एक स्ट्रिंग की सदस्यता, और प्रत्येक वर्ण के लिए, वर्ण को एक स्ट्रिंग (और कोई अन्य संचालन नहीं)में जोड़ने के लिए एक फ़ंक्शन - निर्णायक है , औरइसकी न्यूनतम प्राथमिक उपसंरचना में निश्चित रूप से नियमित भाषाएं शामिल हैं। एक द्विआधारी वर्णमाला के लिए, सिद्धांत को [[S2S (गणित)]] कहा जाता है।<ref>{{cite book | last=Weyer | first=Mark | date=2002 | title=Automata, Logics, and Infinite Games |chapter=Decidability of S1S and S2S | series=Lecture Notes in Computer Science | volume=2500 | pages=207–230 |chapter-url=https://link.springer.com/chapter/10.1007/3-540-36387-4_12 | doi=10.1007/3-540-36387-4_12 | publisher=Springer| isbn=978-3-540-00388-5 }}</ref>




== जटिलता परिणाम ==
== जटिलता परिणाम ==
 
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, सभी नियमित भाषाओं की [[जटिलता वर्ग]] को कभी-कभी REGULAR या REG के रूप में संदर्भित किया जाता है और [[DSPACE]](O(1)) के बराबर होता है, निर्णय की समस्या जिसे निरंतर स्थान में हल किया जा सकता है (उपयोग किया गया स्थान इनपुट आकार से स्वतंत्र है) ). नियमित ≠ AC0, क्योंकि इसमें (तुच्छ रूप से) यह निर्धारित करने की समता समस्या है कि इनपुट में 1 बिट की संख्या सम है या विषम है और यह समस्या AC0 में नहीं है।<sup><ref>{{cite journal | last1 = Furst | first1 = Merrick | last2 = Saxe | first2 = James B. | author2-link = James B. Saxe | last3 = Sipser | first3 = Michael | author3-link = Michael Sipser | doi = 10.1007/BF01744431 | issue = 1 | journal = Mathematical Systems Theory | mr = 738749 | pages = 13–27 | title = Parity, circuits, and the polynomial-time hierarchy | volume = 17 | year = 1984| s2cid = 14677270 }}</ref>दूसरी ओर, REGULAR में AC0 शामिल नहीं है, क्योंकि विलोमपदों की अनियमित भाषा, या अनियमित भाषा<math>\{0^n 1^n : n \in \mathbb N\}</math> दोनों को AC0 में पहचाना जा सकता है।<sup><ref>{{cite book|last1=Cook|first1=Stephen|last2=Nguyen|first2=Phuong|title=Logical foundations of proof complexity|year=2010|publisher=Association for Symbolic Logic|location=Ithaca, NY|isbn=978-0-521-51729-4|pages=75|edition=1. publ.}}</ref>  
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, सभी नियमित भाषाओं की [[जटिलता वर्ग]] को कभी-कभी REGULAR या REG के रूप में संदर्भित किया जाता है और [[DSPACE]](O(1)) के बराबर होता है, निर्णय की समस्या जिसे निरंतर स्थान में हल किया जा सकता है (उपयोग किया गया स्थान इनपुट आकार से स्वतंत्र है) ). नियमित ≠ AC0 | एसी<sup>0</sup>, चूंकि इसमें (तुच्छ रूप से) यह निर्धारित करने की समता समस्या है कि इनपुट में 1 बिट की संख्या सम है या विषम है और यह समस्या एसी में नहीं है<sup>0</उप>।<ref>{{cite journal | last1 = Furst | first1 = Merrick | last2 = Saxe | first2 = James B. | author2-link = James B. Saxe | last3 = Sipser | first3 = Michael | author3-link = Michael Sipser | doi = 10.1007/BF01744431 | issue = 1 | journal = Mathematical Systems Theory | mr = 738749 | pages = 13–27 | title = Parity, circuits, and the polynomial-time hierarchy | volume = 17 | year = 1984| s2cid = 14677270 }}</ref> दूसरी ओर, रेगुलर में एसी नहीं होता है<sup>0</sup>, क्योंकि [[विलोमपद]] की अनियमित भाषा, या अनियमित भाषा <math>\{0^n 1^n : n \in \mathbb N\}</math> क्या दोनों को एसी में पहचाना जा सकता है<sup>0</उप>।<ref>{{cite book|last1=Cook|first1=Stephen|last2=Nguyen|first2=Phuong|title=Logical foundations of proof complexity|year=2010|publisher=Association for Symbolic Logic|location=Ithaca, NY|isbn=978-0-521-51729-4|pages=75|edition=1. publ.}}</ref>
यदि कोई भाषा नियमित नहीं है, तो उसे पहचानने के लिए कम से कम बिग ओ नोटेशन |Ω(लॉग लॉग एन) स्थान वाली मशीन की आवश्यकता होती है (जहां एन इनपुट आकार है)।<ref>J. Hartmanis, P. L. Lewis II, and R. E. Stearns. Hierarchies of memory-limited computations. ''Proceedings of the 6th Annual IEEE Symposium on Switching Circuit Theory and Logic Design'', pp. 179–190. 1965.</ref> दूसरे शब्दों में, डीएसपीएसीई ([[बिग ओ नोटेशन]] (लॉग लॉग एन)) नियमित भाषाओं की कक्षा के बराबर है। व्यवहार में, कम से कम [[लघुगणकीय स्थान]] लेने वाली मशीनों द्वारा अधिकांश अनियमित समस्याओं का समाधान किया जाता है।
यदि कोई भाषा नियमित नहीं है, तो उसे पहचानने के लिए कम से कम बिग ओ नोटेशन |Ω(लॉग लॉग एन) स्पेस वाली मशीन की आवश्यकता होती है (जहां एन इनपुट आकार है)।<ref>J. Hartmanis, P. L. Lewis II, and R. E. Stearns. Hierarchies of memory-limited computations. ''Proceedings of the 6th Annual IEEE Symposium on Switching Circuit Theory and Logic Design'', pp. 179–190. 1965.</ref> दूसरे शब्दों में, डीएसपीएसीई ([[बिग ओ नोटेशन]] (लॉग लॉग एन)) नियमित भाषाओं की कक्षा के बराबर है। व्यवहार में, कम से कम [[लघुगणकीय स्थान]] लेने वाली मशीनों द्वारा अधिकांश अनियमित समस्याओं का समाधान किया जाता है।


== चॉम्स्की पदानुक्रम में स्थान{{anchor|Subclasses}}==
== चॉम्स्की पदानुक्रम में स्थान{{anchor|Subclasses}}==
[[Image:Chomsky-hierarchy.svg|thumb|250px|चॉम्स्की पदानुक्रम की कक्षाओं में नियमित भाषा।]]चॉम्स्की पदानुक्रम में नियमित भाषाओं का पता लगाने के लिए, एक नोटिस है कि प्रत्येक नियमित भाषा संदर्भ मुक्त भाषा है। संदर्भ-मुक्त। इसका विलोम सत्य नहीं है: उदाहरण के लिए a<nowiki>'</nowiki>s की संख्या b<nowiki>'</nowiki>s की समान संख्या वाली सभी स्ट्रिंग्स वाली भाषा संदर्भ-मुक्त है लेकिन नियमित नहीं है। यह साबित करने के लिए कि कोई भाषा नियमित नहीं है, अक्सर माइहिल-नेरोड प्रमेय और नियमित भाषाओं के लिए पम्पिंग लेम्मा का उपयोग किया जाता है। अन्य दृष्टिकोणों में नियमित भाषा का उपयोग करना शामिल है # नियमित भाषाओं के क्लोजर गुण<ref>{{cite web|title=How to prove that a language is not regular?|url=https://cs.stackexchange.com/q/1031|access-date=10 April 2018|website=cs.stackexchange.com}}</ref> या कोल्मोगोरोव जटिलता को मापना।<ref>{{Cite book|last=Hromkovič|first=Juraj|url=https://www.worldcat.org/oclc/53007120|title=Theoretical computer science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography|date=2004|publisher=Springer|isbn=3-540-14015-8|pages=76–77|oclc=53007120}}</ref>
[[Image:Chomsky-hierarchy.svg|thumb|250px|चॉम्स्की पदानुक्रम की कक्षाओं में नियमित भाषा।]]चॉम्स्की पदानुक्रम में नियमित भाषाओं का पता लगाने के लिए, एक नोटिस है कि प्रत्येक नियमित भाषा संदर्भ मुक्त भाषा है। इसका विलोम सत्य नहीं है: उदाहरण के लिए a की संख्या b के समान संख्या वाली सभी स्ट्रिंग्स वाली भाषा संदर्भ-मुक्त है लेकिन नियमित नहीं है। यह साबित करने के लिए कि कोई भाषा नियमित नहीं है, अक्सर माईहिल-नेरोड प्रमेय और पंपिंग लेम्मा का उपयोग किया जाता है। अन्य दृष्टिकोणों में नियमित भाषाओं के समापन गुणों का उपयोग करना शामिल है<ref>{{cite web|title=How to prove that a language is not regular?|url=https://cs.stackexchange.com/q/1031|access-date=10 April 2018|website=cs.stackexchange.com}}</ref> या कोल्मोगोरोव जटिलता को मापना शामिल है।<ref>{{Cite book|last=Hromkovič|first=Juraj|url=https://www.worldcat.org/oclc/53007120|title=Theoretical computer science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography|date=2004|publisher=Springer|isbn=3-540-14015-8|pages=76–77|oclc=53007120}}</ref> एक नियम को उसके बायीं ओर के प्रतीकों की घटना को उसके दायीं ओर दिखाई देने वाले प्रतीकों से बदलकर लागू किया जा सकता है।
नियमित भाषाओं के महत्वपूर्ण उपवर्गों में शामिल हैं
नियमित भाषाओं के महत्वपूर्ण उपवर्गों में शामिल हैं:
* परिमित भाषाएँ, जिनमें शब्दों की सीमित संख्या होती है।<ref>A finite language shouldn't be confused with a (usually infinite) language generated by a finite automaton.</ref> ये नियमित भाषाएं हैं, क्योंकि कोई एक नियमित अभिव्यक्ति बना सकता है जो कि भाषा में प्रत्येक शब्द का संघ (सेट सिद्धांत) है।
* परिमित भाषाएं, जिनमें केवल सीमित संख्या में शब्द होते हैं।<ref>A finite language shouldn't be confused with a (usually infinite) language generated by a finite automaton.</ref> ये नियमित भाषाएं हैं, क्योंकि कोई एक नियमित अभिव्यक्ति बना सकता है जो कि भाषा में प्रत्येक शब्द का संघ (सेट सिद्धांत) है।
* [[स्टार-मुक्त भाषा]]एं, जिन्हें खाली प्रतीक, अक्षरों, संघटन और सभी बूलियन ऑपरेटरों (सेट के बीजगणित देखें) से निर्मित एक नियमित अभिव्यक्ति द्वारा वर्णित किया जा सकता है, जिसमें पूरक (सेट सिद्धांत) शामिल है, लेकिन क्लेन स्टार नहीं: इस वर्ग में सभी शामिल हैं परिमित भाषाएँ।<ref>{{cite book|editor1=Jörg Flum |editor2=Erich Grädel |editor3=Thomas Wilke |title=Logic and automata: history and perspectives|year=2008|publisher=Amsterdam University Press|isbn=978-90-5356-576-6|chapter-url=http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/DG-WT08.pdf|chapter=First-order definable languages|author1=Volker Diekert |author2=Paul Gastin }}</ref>
* [[स्टार-मुक्त भाषा]]एं, जिन्हें खाली प्रतीक, अक्षरों, संघटन और सभी बूलियन ऑपरेटरों (सेट के बीजगणित देखें) से निर्मित एक नियमित अभिव्यक्ति द्वारा वर्णित किया जा सकता है, जिसमें पूरक (सेट सिद्धांत) शामिल है, लेकिन क्लेन स्टार नहीं:इस वर्ग में सभी परिमित भाषाएं शामिल हैं । <ref>{{cite book|editor1=Jörg Flum |editor2=Erich Grädel |editor3=Thomas Wilke |title=Logic and automata: history and perspectives|year=2008|publisher=Amsterdam University Press|isbn=978-90-5356-576-6|chapter-url=http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/DG-WT08.pdf|chapter=First-order definable languages|author1=Volker Diekert |author2=Paul Gastin }}</ref>
*नियम अनुप्रयोगों के अनुक्रम को व्युत्पत्ति कहते हैं। इस तरह का व्याकरण औपचारिक भाषा को परिभाषित करता है: सभी शब्द केवल टर्मिनल प्रतीकों से युक्त होते हैं, जो प्रारंभ प्रतीक से व्युत्पत्ति द्वारा पहुंचा जा सकता है।




== एक नियमित भाषा में शब्दों की संख्या ==
== एक नियमित भाषा में शब्दों की संख्या ==
होने देना <math>s_L(n)</math> लंबाई के शब्दों की संख्या को निरूपित करें <math>n</math> में <math>L</math>. एल के लिए [[सामान्य जनरेटिंग फ़ंक्शन]] [[औपचारिक शक्ति श्रृंखला]] है
<math>s_L(n)</math> लंबाई के शब्दों की संख्या को निरूपित करता है, <math>n</math> में <math>L</math>. एल के लिए [[सामान्य जनरेटिंग फ़ंक्शन]] [[औपचारिक शक्ति श्रृंखला]] है


:<math>S_L(z) = \sum_{n \ge 0} s_L(n) z^n \ . </math>
:<math>S_L(z) = \sum_{n \ge 0} s_L(n) z^n \ . </math>
यदि L नियमित है तो भाषा L का जनरेटिंग फ़ंक्शन एक तर्कसंगत फ़ंक्शन है।<ref name=Honkala>{{cite journal | zbl=0675.68034 | last=Honkala | first=Juha | title=A necessary condition for the rationality of the zeta function of a regular language | journal=Theor. Comput. Sci. | volume=66 | issue=3 | pages=341–347 | year=1989 | doi=10.1016/0304-3975(89)90159-x | doi-access=free }}</ref> इसलिए हर नियमित भाषा के लिए <math>L</math> क्रम <math>s_L(n)_{n \geq 0}</math> स्थिर-पुनरावर्ती क्रम है|निरंतर-पुनरावर्ती; अर्थात्, एक पूर्णांक स्थिरांक मौजूद है <math>n_0</math>, जटिल स्थिरांक <math>\lambda_1,\,\ldots,\,\lambda_k</math> और जटिल बहुपद <math>p_1(x),\,\ldots,\,p_k(x)</math>
यदि L नियमित है तो भाषा L का जनक कार्य एक तर्कसंगत कार्य है।<ref name=Honkala>{{cite journal | zbl=0675.68034 | last=Honkala | first=Juha | title=A necessary condition for the rationality of the zeta function of a regular language | journal=Theor. Comput. Sci. | volume=66 | issue=3 | pages=341–347 | year=1989 | doi=10.1016/0304-3975(89)90159-x | doi-access=free }}</ref> इसलिए हर नियमित भाषा के लिए <math>L</math> क्रम <math>s_L(n)_{n \geq 0}</math> स्थिर-पुनरावर्ती क्रम है|निरंतर-पुनरावर्ती; अर्थात्, एक पूर्णांक स्थिरांक मौजूद है <math>n_0</math>, जटिल स्थिरांक <math>\lambda_1,\,\ldots,\,\lambda_k</math> और जटिल बहुपद <math>p_1(x),\,\ldots,\,p_k(x)</math>
ऐसा कि प्रत्येक के लिए <math>n \geq n_0</math> जो नंबर <math>s_L(n)</math> लंबाई के शब्दों की <math>n</math> में <math>L</math> है
ऐसा कि प्रत्येक के लिए <math>n \geq n_0</math> जो नंबर <math>s_L(n)</math> लंबाई के शब्दों की <math>n</math> में <math>L</math> है
<math>s_L(n)=p_1(n)\lambda_1^n+\dotsb+p_k(n)\lambda_k^n</math>.<ref>Flajolet & Sedgweick, section V.3.1, equation (13).</ref><ref>{{cite web|url=https://cs.stackexchange.com/q/1048 |title=Number of words in the regular language $(00)^*$|website=cs.stackexchange.com|access-date=10 April 2018}}</ref><ref>{{cite web| url = https://cs.stackexchange.com/q/11333| title = Proof of theorem for arbitrary DFAs}}</ref><ref>{{cite web|url=https://cs.stackexchange.com/q/1045 |title=Number of words of a given length in a regular language|website=cs.stackexchange.com|access-date=10 April 2018}}</ref>
<math>s_L(n)=p_1(n)\lambda_1^n+\dotsb+p_k(n)\lambda_k^n</math>.<ref>Flajolet & Sedgweick, section V.3.1, equation (13).</ref><ref>{{cite web|url=https://cs.stackexchange.com/q/1048 |title=Number of words in the regular language $(00)^*$|website=cs.stackexchange.com|access-date=10 April 2018}}</ref><ref>{{cite web| url = https://cs.stackexchange.com/q/11333| title = Proof of theorem for arbitrary DFAs}}</ref><ref>{{cite web|url=https://cs.stackexchange.com/q/1045 |title=Number of words of a given length in a regular language|website=cs.stackexchange.com|access-date=10 April 2018}}</ref>
Line 96: Line 94:


== सामान्यीकरण ==
== सामान्यीकरण ==
एक नियमित भाषा की धारणा को अनंत शब्दों (देखें ω-automata) और पेड़ों ([[पेड़ automaton]] देखें) के लिए सामान्यीकृत किया गया है।।
एक नियमित भाषा की धारणा को अनंत शब्दों (देखें ω-automata) और पेड़ों ([[पेड़ automaton|पेड़ ऑटोमेशन]] देखें) के लिए सामान्यीकृत किया गया है।।


[[तर्कसंगत सेट]] मोनोइड्स के लिए धारणा (नियमित/तर्कसंगत भाषा) को सामान्यीकृत करता है जो आवश्यक रूप से मुक्त नहीं हैं। इसी तरह, एक पहचानने योग्य भाषा की धारणा (एक परिमित automaton द्वारा) एक मोनोइड पर पहचानने योग्य सेट के रूप में नामित है जो कि जरूरी नहीं है। हावर्ड स्ट्रॉबिंग इन तथ्यों के संबंध में टिप्पणी करते हैं कि "नियमित भाषा" शब्द थोड़ा दुर्भाग्यपूर्ण है। [[सैमुअल एलेनबर्ग]] के मोनोग्राफ से प्रभावित कागजात<ref name="Eilenberg1974">{{cite book|author=Samuel Eilenberg|title=Automata, languages, and machines|publisher=Academic Press}} in two volumes "A" (1974, {{isbn|9780080873749}}) and "B" (1976, {{isbn|9780080873756}}), the latter with two chapters by Bret Tilson.</ref> अक्सर या तो "पहचानने योग्य भाषा" शब्द का उपयोग करते हैं, जो ऑटोमेटा के व्यवहार को संदर्भित करता है, या "तर्कसंगत भाषा", जो नियमित अभिव्यक्तियों और तर्कसंगत शक्ति श्रृंखला के बीच महत्वपूर्ण समानता को संदर्भित करता है। (वास्तव में, ईलेनबर्ग मनमाने मोनोइड्स के तर्कसंगत और पहचानने योग्य उपसमुच्चय को परिभाषित करता है; दो धारणाएं सामान्य रूप से मेल नहीं खाती हैं।) यह शब्दावली, जबकि बेहतर प्रेरित है, वास्तव में कभी भी पकड़ में नहीं आती है, और "नियमित भाषा" का उपयोग लगभग सार्वभौमिक रूप से किया जाता है।<ref>{{cite book | last=Straubing | first=Howard | title=Finite automata, formal logic, and circuit complexity | url=https://archive.org/details/finiteautomatafo0000stra | url-access=registration | series=Progress in Theoretical Computer Science | location=Basel | publisher=Birkhäuser | year=1994 | isbn=3-7643-3719-2 | zbl=0816.68086 | page= [https://archive.org/details/finiteautomatafo0000stra/page/8 8] }}</ref>
[[तर्कसंगत सेट]] मोनोइड्स के लिए धारणा (नियमित/तर्कसंगत भाषा) को सामान्यीकृत करता है जो आवश्यक रूप से मुक्त नहीं हैं। इसी तरह, एक पहचानने योग्य भाषा की धारणा (एक परिमित ऑटोमेशन द्वारा) एक मोनोइड पर पहचानने योग्य सेट के रूप में नामित है जो कि जरूरी नहीं है। हावर्ड स्ट्रॉबिंग इन तथ्यों के संबंध में टिप्पणी करते हैं कि "नियमित भाषा" शब्द थोड़ा दुर्भाग्यपूर्ण है। [[सैमुअल एलेनबर्ग]] के मोनोग्राफ से प्रभावित कागजात<ref name="Eilenberg1974">{{cite book|author=Samuel Eilenberg|title=Automata, languages, and machines|publisher=Academic Press}} in two volumes "A" (1974, {{isbn|9780080873749}}) and "B" (1976, {{isbn|9780080873756}}), the latter with two chapters by Bret Tilson.</ref> अक्सर या तो "पहचानने योग्य भाषा" शब्द का उपयोग करते हैं, जो ऑटोमेटा के व्यवहार को संदर्भित करता है, या "तर्कसंगत भाषा", जो नियमित अभिव्यक्तियों और तर्कसंगत शक्ति श्रृंखला के बीच महत्वपूर्ण समानता को संदर्भित करता है। (वास्तव में, ईलेनबर्ग मनमाने मोनोइड्स के तर्कसंगत और पहचानने योग्य उपसमुच्चय को परिभाषित करता है; दो धारणाएं सामान्य रूप से मेल नहीं खाती हैं।) यह शब्दावली, जबकि बेहतर प्रेरित है, वास्तव में कभी भी पकड़ में नहीं आती है, और "नियमित भाषा" का उपयोग लगभग सार्वभौमिक रूप से किया जाता है।<ref>{{cite book | last=Straubing | first=Howard | title=Finite automata, formal logic, and circuit complexity | url=https://archive.org/details/finiteautomatafo0000stra | url-access=registration | series=Progress in Theoretical Computer Science | location=Basel | publisher=Birkhäuser | year=1994 | isbn=3-7643-3719-2 | zbl=0816.68086 | page= [https://archive.org/details/finiteautomatafo0000stra/page/8 8] }}</ref>
[[तर्कसंगत श्रृंखला]] एक और सामान्यीकरण है, इस बार एक सेमीरिंग पर एक औपचारिक शक्ति श्रृंखला के संदर्भ में है। यह दृष्टिकोण [[भारित तर्कसंगत अभिव्यक्ति]]यों और [[भारित ऑटोमेटा]] को जन्म देता है। इस बीजगणितीय संदर्भ में, नियमित भाषाओं ([[बूलियन सेमिरिंग]] तर्कसंगत अभिव्यक्तियों के अनुरूप) को सामान्य रूप से तर्कसंगत भाषा कहा जाता है।<ref>Berstel & Reutenauer (2011) p.47</ref><ref>{{cite book | last=Sakarovitch | first=Jacques | title=Elements of automata theory | others=Translated from the French by Reuben Thomas | location=Cambridge | publisher=[[Cambridge University Press]] | year=2009 | isbn=978-0-521-84425-3 | zbl=1188.68177 | page = 86 }}</ref> इसके अलावा इस संदर्भ में, क्लेन के प्रमेय को क्लेन-शुत्ज़ेनबर्गर प्रमेय नामक एक सामान्यीकरण मिलता है।
[[तर्कसंगत श्रृंखला]] एक और सामान्यीकरण है, इस बार एक सेमीरिंग पर एक औपचारिक शक्ति श्रृंखला के संदर्भ में है। यह दृष्टिकोण [[भारित तर्कसंगत अभिव्यक्ति]]यों और [[भारित ऑटोमेटा]] को जन्म देता है। इस बीजगणितीय संदर्भ में, नियमित भाषाओं ([[बूलियन सेमिरिंग]] तर्कसंगत अभिव्यक्तियों के अनुरूप) को सामान्य रूप से तर्कसंगत भाषा कहा जाता है।<ref>Berstel & Reutenauer (2011) p.47</ref><ref>{{cite book | last=Sakarovitch | first=Jacques | title=Elements of automata theory | others=Translated from the French by Reuben Thomas | location=Cambridge | publisher=[[Cambridge University Press]] | year=2009 | isbn=978-0-521-84425-3 | zbl=1188.68177 | page = 86 }}</ref> इसके अलावा इस संदर्भ में, क्लेन के प्रमेय को क्लेन-शुत्ज़ेनबर्गर प्रमेय नामक एक सामान्यीकरण मिलता है।


== उदाहरणों से सीखना ==
== उदाहरणों से सीखना ==
{{main|Induction of regular languages}}
{{main|नियमित भाषाओं का समावेश}}




Line 136: Line 134:
*{{CZoo|Class REG|R#reg}}
*{{CZoo|Class REG|R#reg}}


{{Formal languages and grammars}}
[[Category:All articles with unsourced statements]]
[[Category: औपचारिक भाषाएँ]] [[Category: स्वतः समाप्त हो गया]]  
[[Category:Articles with hatnote templates targeting a nonexistent page]]
 
[[Category:Articles with unsourced statements from January 2016]]
 
 
[[Category: Machine Translated Page]]
[[Category:Created On 17/02/2023]]
[[Category:Created On 17/02/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:औपचारिक भाषाएँ]]
[[Category:स्वतः समाप्त हो गया]]

Latest revision as of 16:32, 2 March 2023

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

वैकल्पिक रूप से, एक नियमित भाषा को परिमित ऑटोमेशन द्वारा मान्यता प्राप्त भाषा के रूप में परिभाषित किया जा सकता है। रेगुलर एक्सप्रेशंस और परिमित ऑटोमेटा की समानता को क्लेन के प्रमेय के रूप में जाना जाता है[3] (अमेरिकी गणितज्ञ स्टीफन कोल क्लेन के बाद)। चॉम्स्की पदानुक्रम में, नियमित भाषाएं टाइप -3 व्याकरण नियमित व्याकरण द्वारा उत्पन्न भाषाएं होती हैं |

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

एक वर्णमाला (औपचारिक भाषाओं) पर नियमित भाषाओं का संग्रह Σ को पुनरावर्ती रूप से निम्नानुसार परिभाषित किया गया है:

  • खाली भाषा Ø एक नियमित भाषा है।
  • प्रत्येक के लिए ∈ Σ (a Σ से संबंधित है), सिंगलटन (गणित) भाषा {a} एक नियमित भाषा है।
  • यदि A एक नियमित भाषा है, तो A* (क्लेन स्टार) एक नियमित भाषा है। इसके कारण, रिक्त स्ट्रिंग भाषा {ε} भी नियमित है।
  • यदि ए और बी नियमित भाषाएं हैं, तो ए ∪ बी (यूनियन) और ए • बी (संयोजन) नियमित भाषाएं हैं।
  • Σ से अधिक कोई अन्य भाषा नियमित नहीं है।

नियमित अभिव्यक्ति के सिंटैक्स और शब्दार्थ के लिए नियमित अभिव्यक्ति # औपचारिक भाषा सिद्धांत देखें।

उदाहरण

सभी परिमित भाषाएँ नियमित हैं; विशेष रूप से खाली स्ट्रिंग भाषा {ε} = Ø* नियमित है। अन्य विशिष्ट उदाहरणों में वर्णमाला {a, b} पर सभी स्ट्रिंग्स वाली भाषा शामिल है, जिसमें a की संख्या भी शामिल है, या भाषा में सभी स्ट्रिंग्स शामिल हैं: कई a के बाद कई b हैं।

एक भाषा का एक सरल उदाहरण जो नियमित नहीं है, स्ट्रिंग्स का सेट है {anbn | n ≥ 0}।[4] सहज रूप से, इसे परिमित ऑटोमेशन के साथ पहचाना नहीं जा सकता है, क्योंकि एक परिमित ऑटोमेशन में परिमित स्मृति होती है और यह a की सटीक संख्या को याद नहीं रख सकती है। इस तथ्य को कठोरता से सिद्ध करने की तकनीकों को चॉम्स्की पदानुक्रम में # स्थान दिया गया है।

समकक्ष औपचारिकताएं

एक नियमित भाषा निम्नलिखित समकक्ष गुणों को संतुष्ट करती है:

  1. यह एक नियमित अभिव्यक्ति की भाषा है (उपरोक्त परिभाषा के अनुसार)
  2. यह एक गैर-नियतात्मक परिमित ऑटोमेटन (NFA) द्वारा स्वीकृत भाषा है[note 1][note 2]
  3. यह नियतात्मक परिमित ऑटोमेशन (DFA) द्वारा स्वीकृत भाषा है[note 3][note 4]
  4. इसे एक नियमित व्याकरण द्वारा उत्पन्न किया जा सकता है[note 5][note 6]
  5. यह वैकल्पिक परिमित ऑटोमेशन द्वारा स्वीकृत भाषा है
  6. यह दो तरफा परिमित ऑटोमेशन द्वारा स्वीकृत भाषा है
  7. यह एक उपसर्ग व्याकरण द्वारा उत्पन्न किया जा सकता है
  8. इसे रीड-ओनली ट्यूरिंग मशीन द्वारा स्वीकार किया जा सकता है
  9. इसे मोनाडिक प्रेडिकेट कैलकुलस दूसरे क्रम का तर्क (बुची-एल्गोट-ट्रेखटेनब्रॉट प्रमेय) में परिभाषित किया जा सकता है।[5]
  10. यह कुछ परिमित सिंटैक्टिक मोनोइड एम द्वारा पहचाने जाने योग्य सेट है, जिसका अर्थ है कि यह preimage है, {w ∈ Σ* f(w) ∈ S } एक मोनॉइड समरूपता f: Σ के तहत एक परिमित मोनॉइड M के एक उपसमुच्चय का* → M इसके वर्णमाला पर मुक्त मोनोइड[note 7]
  11. इसके वाक्यगत सर्वांगसमता के तुल्यता वर्गों की संख्या परिमित है।[note 8][note 9] (यह संख्या एल को स्वीकार करने वाले डीएफए न्यूनीकरण के राज्यों की संख्या के बराबर है।)

गुण 10. और 11. नियमित भाषाओं को परिभाषित करने के लिए विशुद्ध रूप से बीजगणितीय दृष्टिकोण हैं; एक मोनोइड एम ⊆ Σ के लिए बयानों का एक समान सेट तैयार किया जा सकता है, इस मामले में, एम पर समानता पहचानने योग्य भाषा की अवधारणा की ओर ले जाती है।

कुछ लेखक उपरोक्त गुणों में से एक का उपयोग नियमित भाषाओं की वैकल्पिक परिभाषा के रूप में 1. से भिन्न करते हैं।

उपरोक्त कुछ तुल्यताओं, विशेष रूप से पहले चार औपचारिकताओं में से, को पाठ्यपुस्तकों में क्लेन की प्रमेय कहा जाता है। सटीक रूप से कौन सा (या कौन सा सबसेट) ऐसा कहा जाता है लेखकों के बीच भिन्न होता है। एक पाठ्यपुस्तक रेगुलर एक्सप्रेशंस और एनएफए (1. और 2. ऊपर) क्लेन की प्रमेय की समानता कहती है।[6] एक अन्य पाठ्यपुस्तक रेगुलर एक्सप्रेशंस और DFAs (1. और 3. ऊपर) क्लेन की प्रमेय की समानता कहती है।[7] दो अन्य पाठ्यपुस्तकें पहले एनएफए और डीएफए (2. और 3.) की अभिव्यंजक समानता को साबित करती हैं और फिर क्लेन के प्रमेय को नियमित अभिव्यक्ति और परिमित ऑटोमेटा के बीच समानता के रूप में बताती हैं (बाद वाले ने पहचानने योग्य भाषाओं का वर्णन करने के लिए कहा)।[2][8] एक भाषाई रूप से उन्मुख पाठ पहले डीएफए और एनएफए के साथ नियमित व्याकरण (4. ऊपर) को समान करता है, इन नियमित (इनमें से किसी भी) द्वारा उत्पन्न भाषाओं को कॉल करता है, जिसके बाद यह नियमित अभिव्यक्तियों का परिचय देता है जो तर्कसंगत भाषाओं का वर्णन करने के लिए शब्द है, और अंत में क्लेन के प्रमेय को बताता है नियमित और तर्कसंगत भाषाओं का संयोग।[9] अन्य लेखक केवल तर्कसंगत अभिव्यक्ति और नियमित अभिव्यक्ति को पर्यायवाची के रूप में परिभाषित करते हैं और तर्कसंगत भाषाओं और नियमित भाषाओं के साथ भी ऐसा ही करते हैं।[1][2]

जाहिर तौर पर, नियमित शब्द की उत्पत्ति 1951 की एक तकनीकी रिपोर्ट से हुई है, जहां क्लेन ने नियमित घटनाओं की शुरुआत की और अधिक वर्णनात्मक शब्द के रूप में किसी भी सुझाव का स्पष्ट रूप से स्वागत किया।[10] नोम चौमस्की ने अपने 1959 के मौलिक लेख में, नियमित रूप से पहले एक अलग अर्थ में शब्द का इस्तेमाल किया था (जिसे आज चॉम्स्की सामान्य रूप कहा जाता है)[11] लेकिन उन्होंने देखा कि उनकी परिमित राज्य भाषाएं क्लेन की नियमित घटनाओं के बराबर थीं।[12]


क्लोजर प्रॉपर्टीज

विभिन्न संक्रियाओं के तहत नियमित भाषाएं क्लोजर (गणित) हैं, अर्थात, यदि भाषा K और L नियमित हैं, तो निम्न संक्रियाओं का परिणाम भी है:

  • सेट-सैद्धांतिक संचालन | सेट-सैद्धांतिक बूलियन संचालन: संघ (सेट सिद्धांत) K ∪ L, चौराहा (सेट सिद्धांत) K ∩ L, और पूरक (सेट सिद्धांत) L, इसलिए सापेक्ष पूरक भी K − L.[13]
  • नियमित संचालन: K ∪ L, संयोजन , और क्लेन स्टार L*.[14]
  • भाषाओं के संचालन का अमूर्त परिवार: स्ट्रिंग समरूपता, उलटा स्ट्रिंग समरूपता, और नियमित भाषाओं के साथ प्रतिच्छेदन। एक परिणाम के रूप में वे मनमाने ढंग से परिमित राज्य ट्रांसड्यूसर के तहत बंद हो जाते हैं, जैसे नियमित भाषा के साथ सही भागफल K / L। इससे भी अधिक, नियमित भाषाओं को मनमाने ढंग से भाषाओं के साथ बंद कर दिया जाता है: यदि L नियमित है तो L / K किसी भी K के लिए नियमित है।[citation needed]
  • रिवर्स (या मिरर इमेज) एलआरR[15] एल को पहचानने के लिए एक गैर-नियतात्मक परिमित ऑटोमेशन दिया गया, एल के लिए एक ऑटोमेटन सभी संक्रमणों को उलट कर और आरंभिक और अंतिम अवस्थाओं को आपस में बदलकर प्राप्त किया जा सकता है। इसके परिणामस्वरूप कई प्रारंभिक अवस्थाएँ हो सकती हैं; उन्हें जोड़ने के लिए ε-संक्रमण का उपयोग किया जा सकता है।

निर्णायकता गुण

दो निर्धारक परिमित ऑटोमेटा ए और बी को देखते हुए, यह तय किया जा सकता है कि वे एक ही भाषा को स्वीकार करते हैं या नहीं।[16] एक परिणाम के रूप में, उपरोक्त क्लोजर गुणों का उपयोग करते हुए, निम्नलिखित समस्याएं भी मनमाने ढंग से दिए गए नियतात्मक परिमित ऑटोमेटा ए और बी के लिए क्रमशः स्वीकृत भाषाओं एलए और एलबी के साथ निर्णायक हैं A और B, क्रमश:

  • रोकथाम: एल हैA ⊆ एलB ?[note 10]
  • वियोग: एल हैA ∩ एलB = {} ?
  • खालीपन: है एलA = {} ?
  • सार्वभौमिकता: एल हैA = एस*</सुप> ?
  • सदस्यता: एक ∈ Σ दिया*, एक ∈ एल हैB ?

नियमित अभिव्यक्तियों के लिए, सिंगलटन वर्णमाला के लिए सार्वभौमिकता समस्या पहले से ही एनपी-पूर्ण है।[17] बड़े अक्षरों के लिए, वह समस्या PSPACE-पूर्ण है। यदि रेगुलर एक्सप्रेशन और ऑटोमेटा|PSPACE-पूर्ण है।[18] यदि रेगुलर एक्सप्रेशंस को एक स्क्वेरिंग ऑपरेटर की अनुमति देने के लिए विस्तारित किया जाता है, जिसमें "A2" को "AA" के रूप में दर्शाया जाता है, तो भी केवल नियमित भाषाओं का वर्णन किया जा सकता है, लेकिन सार्वभौमिकता की समस्या में एक घातीय स्थान निचली सीमा होती है,[19][20][21] और वास्तव में बहुपद-समय में कमी के संबंध में घातांकी स्थान के लिए पूर्ण है।[22] एक निश्चित परिमित वर्णमाला के लिए, सभी भाषाओं के समुच्चय का सिद्धांत - एक साथ तार के साथ, एक भाषा में एक स्ट्रिंग की सदस्यता, और प्रत्येक वर्ण के लिए, वर्ण को एक स्ट्रिंग (और कोई अन्य संचालन नहीं)में जोड़ने के लिए एक फ़ंक्शन - निर्णायक है , औरइसकी न्यूनतम प्राथमिक उपसंरचना में निश्चित रूप से नियमित भाषाएं शामिल हैं। एक द्विआधारी वर्णमाला के लिए, सिद्धांत को S2S (गणित) कहा जाता है।[23]


जटिलता परिणाम

कम्प्यूटेशनल जटिलता सिद्धांत में, सभी नियमित भाषाओं की जटिलता वर्ग को कभी-कभी REGULAR या REG के रूप में संदर्भित किया जाता है और DSPACE(O(1)) के बराबर होता है, निर्णय की समस्या जिसे निरंतर स्थान में हल किया जा सकता है (उपयोग किया गया स्थान इनपुट आकार से स्वतंत्र है) ). नियमित ≠ AC0, क्योंकि इसमें (तुच्छ रूप से) यह निर्धारित करने की समता समस्या है कि इनपुट में 1 बिट की संख्या सम है या विषम है और यह समस्या AC0 में नहीं है।[24]दूसरी ओर, REGULAR में AC0 शामिल नहीं है, क्योंकि विलोमपदों की अनियमित भाषा, या अनियमित भाषा दोनों को AC0 में पहचाना जा सकता है।[25] यदि कोई भाषा नियमित नहीं है, तो उसे पहचानने के लिए कम से कम बिग ओ नोटेशन |Ω(लॉग लॉग एन) स्थान वाली मशीन की आवश्यकता होती है (जहां एन इनपुट आकार है)।[26] दूसरे शब्दों में, डीएसपीएसीई (बिग ओ नोटेशन (लॉग लॉग एन)) नियमित भाषाओं की कक्षा के बराबर है। व्यवहार में, कम से कम लघुगणकीय स्थान लेने वाली मशीनों द्वारा अधिकांश अनियमित समस्याओं का समाधान किया जाता है।

चॉम्स्की पदानुक्रम में स्थान

चॉम्स्की पदानुक्रम की कक्षाओं में नियमित भाषा।

चॉम्स्की पदानुक्रम में नियमित भाषाओं का पता लगाने के लिए, एक नोटिस है कि प्रत्येक नियमित भाषा संदर्भ मुक्त भाषा है। इसका विलोम सत्य नहीं है: उदाहरण के लिए a की संख्या b के समान संख्या वाली सभी स्ट्रिंग्स वाली भाषा संदर्भ-मुक्त है लेकिन नियमित नहीं है। यह साबित करने के लिए कि कोई भाषा नियमित नहीं है, अक्सर माईहिल-नेरोड प्रमेय और पंपिंग लेम्मा का उपयोग किया जाता है। अन्य दृष्टिकोणों में नियमित भाषाओं के समापन गुणों का उपयोग करना शामिल है[27] या कोल्मोगोरोव जटिलता को मापना शामिल है।[28] एक नियम को उसके बायीं ओर के प्रतीकों की घटना को उसके दायीं ओर दिखाई देने वाले प्रतीकों से बदलकर लागू किया जा सकता है।

नियमित भाषाओं के महत्वपूर्ण उपवर्गों में शामिल हैं:

  • परिमित भाषाएं, जिनमें केवल सीमित संख्या में शब्द होते हैं।[29] ये नियमित भाषाएं हैं, क्योंकि कोई एक नियमित अभिव्यक्ति बना सकता है जो कि भाषा में प्रत्येक शब्द का संघ (सेट सिद्धांत) है।
  • स्टार-मुक्त भाषाएं, जिन्हें खाली प्रतीक, अक्षरों, संघटन और सभी बूलियन ऑपरेटरों (सेट के बीजगणित देखें) से निर्मित एक नियमित अभिव्यक्ति द्वारा वर्णित किया जा सकता है, जिसमें पूरक (सेट सिद्धांत) शामिल है, लेकिन क्लेन स्टार नहीं:इस वर्ग में सभी परिमित भाषाएं शामिल हैं । [30]
  • नियम अनुप्रयोगों के अनुक्रम को व्युत्पत्ति कहते हैं। इस तरह का व्याकरण औपचारिक भाषा को परिभाषित करता है: सभी शब्द केवल टर्मिनल प्रतीकों से युक्त होते हैं, जो प्रारंभ प्रतीक से व्युत्पत्ति द्वारा पहुंचा जा सकता है।


एक नियमित भाषा में शब्दों की संख्या

लंबाई के शब्दों की संख्या को निरूपित करता है, में . एल के लिए सामान्य जनरेटिंग फ़ंक्शन औपचारिक शक्ति श्रृंखला है

यदि L नियमित है तो भाषा L का जनक कार्य एक तर्कसंगत कार्य है।[31] इसलिए हर नियमित भाषा के लिए क्रम स्थिर-पुनरावर्ती क्रम है|निरंतर-पुनरावर्ती; अर्थात्, एक पूर्णांक स्थिरांक मौजूद है , जटिल स्थिरांक और जटिल बहुपद ऐसा कि प्रत्येक के लिए जो नंबर लंबाई के शब्दों की में है .[32][33][34][35] इस प्रकार, कुछ भाषाओं की गैर-नियमितता दी गई लम्बाई के शब्दों को गिनकर सिद्ध किया जा सकता है . उदाहरण के लिए, संतुलित कोष्ठकों के तार की डाइक भाषा पर विचार करें। लंबाई के शब्दों की संख्या डाइक भाषा में कैटलन संख्या के बराबर है , जो स्वरूप का न हो , डाइक भाषा की गैर-नियमितता का साक्षी। कुछ eigenvalues ​​​​के बाद से देखभाल की जानी चाहिए समान परिमाण हो सकता है। उदाहरण के लिए, लंबाई के शब्दों की संख्या सबकी भाषा में द्विअर्थी शब्द भी रूप का नहीं है , लेकिन सम या विषम लंबाई के शब्दों की संख्या इस रूप की है; संबंधित eigenvalues ​​​​हैं . सामान्य तौर पर, प्रत्येक नियमित भाषा के लिए एक स्थिरांक मौजूद होता है ऐसा कि सभी के लिए , लंबाई के शब्दों की संख्या असम्बद्ध रूप से है .[36] किसी भाषा L का जीटा फलन है[31]

एक नियमित भाषा का जीटा कार्य सामान्य रूप से तर्कसंगत नहीं है, लेकिन एक मनमाना चक्रीय भाषा है।[37][38]


सामान्यीकरण

एक नियमित भाषा की धारणा को अनंत शब्दों (देखें ω-automata) और पेड़ों (पेड़ ऑटोमेशन देखें) के लिए सामान्यीकृत किया गया है।।

तर्कसंगत सेट मोनोइड्स के लिए धारणा (नियमित/तर्कसंगत भाषा) को सामान्यीकृत करता है जो आवश्यक रूप से मुक्त नहीं हैं। इसी तरह, एक पहचानने योग्य भाषा की धारणा (एक परिमित ऑटोमेशन द्वारा) एक मोनोइड पर पहचानने योग्य सेट के रूप में नामित है जो कि जरूरी नहीं है। हावर्ड स्ट्रॉबिंग इन तथ्यों के संबंध में टिप्पणी करते हैं कि "नियमित भाषा" शब्द थोड़ा दुर्भाग्यपूर्ण है। सैमुअल एलेनबर्ग के मोनोग्राफ से प्रभावित कागजात[39] अक्सर या तो "पहचानने योग्य भाषा" शब्द का उपयोग करते हैं, जो ऑटोमेटा के व्यवहार को संदर्भित करता है, या "तर्कसंगत भाषा", जो नियमित अभिव्यक्तियों और तर्कसंगत शक्ति श्रृंखला के बीच महत्वपूर्ण समानता को संदर्भित करता है। (वास्तव में, ईलेनबर्ग मनमाने मोनोइड्स के तर्कसंगत और पहचानने योग्य उपसमुच्चय को परिभाषित करता है; दो धारणाएं सामान्य रूप से मेल नहीं खाती हैं।) यह शब्दावली, जबकि बेहतर प्रेरित है, वास्तव में कभी भी पकड़ में नहीं आती है, और "नियमित भाषा" का उपयोग लगभग सार्वभौमिक रूप से किया जाता है।[40] तर्कसंगत श्रृंखला एक और सामान्यीकरण है, इस बार एक सेमीरिंग पर एक औपचारिक शक्ति श्रृंखला के संदर्भ में है। यह दृष्टिकोण भारित तर्कसंगत अभिव्यक्तियों और भारित ऑटोमेटा को जन्म देता है। इस बीजगणितीय संदर्भ में, नियमित भाषाओं (बूलियन सेमिरिंग तर्कसंगत अभिव्यक्तियों के अनुरूप) को सामान्य रूप से तर्कसंगत भाषा कहा जाता है।[41][42] इसके अलावा इस संदर्भ में, क्लेन के प्रमेय को क्लेन-शुत्ज़ेनबर्गर प्रमेय नामक एक सामान्यीकरण मिलता है।

उदाहरणों से सीखना

Main article: नियमित भाषाओं का समावेश


टिप्पणियाँ

  1. ↑ 1. ⇒ 2. by Thompson's construction algorithm
  2. ↑ 2. ⇒ 1. by Kleene's algorithm or using Arden's lemma
  3. ↑ 2. ⇒ 3. by the powerset construction
  4. ↑ 3. ⇒ 2. since the former definition is stronger than the latter
  5. ↑ 2. ⇒ 4. see Hopcroft, Ullman (1979), Theorem 9.2, p.219
  6. ↑ 4. ⇒ 2. see Hopcroft, Ullman (1979), Theorem 9.1, p.218
  7. ↑ 3. ⇔ 10. by the Myhill–Nerode theorem
  8. ↑ u~v is defined as: uw∈L if and only if vw∈L for all w∈Σ*
  9. ↑ 3. ⇔ 11. see the proof in the Syntactic monoid article, and see p.160 in Holcombe, W.M.L. (1982). Algebraic automata theory. Cambridge Studies in Advanced Mathematics. Vol. 1. Cambridge University Press. ISBN 0-521-60492-3. Zbl 0489.68046.
  10. ↑ Check if LA ∩ LB = LA. Deciding this property is NP-hard in general; see File:RegSubsetNP.pdf for an illustration of the proof idea.


संदर्भ

  1. ↑ 1.0 1.1 Ruslan Mitkov (2003). The Oxford Handbook of Computational Linguistics. Oxford University Press. p. 754. ISBN 978-0-19-927634-9.
  2. ↑ 2.0 2.1 2.2 Mark V. Lawson (2003). Finite Automata. CRC Press. pp. 98–103. ISBN 978-1-58488-255-8.
  3. ↑ Sheng Yu (1997). "Regular languages". In Grzegorz Rozenberg; Arto Salomaa (eds.). Handbook of Formal Languages: Volume 1. Word, Language, Grammar. Springer. p. 41. ISBN 978-3-540-60420-4.
  4. ↑ Eilenberg (1974), p. 16 (Example II, 2.8) and p. 25 (Example II, 5.2).
  5. ↑ M. Weyer: Chapter 12 - Decidability of S1S and S2S, p. 219, Theorem 12.26. In: Erich Grädel, Wolfgang Thomas, Thomas Wilke (Eds.): Automata, Logics, and Infinite Games: A Guide to Current Research. Lecture Notes in Computer Science 2500, Springer 2002.
  6. ↑ Robert Sedgewick; Kevin Daniel Wayne (2011). एल्गोरिदम. Addison-Wesley Professional. p. 794. ISBN 978-0-321-57351-3.
  7. ↑ Jean-Paul Allouche; Jeffrey Shallit (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. p. 129. ISBN 978-0-521-82332-6.
  8. ↑ Kenneth Rosen (2011). Discrete Mathematics and Its Applications 7th edition. McGraw-Hill Science. pp. 873–880.
  9. ↑ Horst Bunke; Alberto Sanfeliu (January 1990). Syntactic and Structural Pattern Recognition: Theory and Applications. World Scientific. p. 248. ISBN 978-9971-5-0566-0.
  10. ↑ Stephen Cole Kleene (Dec 1951). Representation of Events in Nerve Nets and Finite Automate (PDF) (Research Memorandum). U.S. Air Force / RAND Corporation. Here: p.46
  11. ↑ Noam Chomsky (1959). "On Certain Formal Properties of Grammars" (PDF). Information and Control. 2 (2): 137–167. doi:10.1016/S0019-9958(59)90362-6. Here: Definition 8, p.149
  12. ↑ Chomsky 1959, Footnote 10, p.150
  13. ↑ Salomaa (1981) p.28
  14. ↑ Salomaa (1981) p.27
  15. ↑ Hopcroft, Ullman (1979), Chapter 3, Exercise 3.4g, p. 72
  16. ↑ Hopcroft, Ullman (1979), Theorem 3.8, p.64; see also Theorem 3.10, p.67
  17. ↑ Aho, Hopcroft, Ullman (1974), Exercise 10.14, p.401
  18. ↑ Aho, Hopcroft, Ullman (1974), Theorem 10.14, p399
  19. ↑ Hopcroft, Ullman (1979), Theorem 13.15, p.351
  20. ↑ A.R. Meyer & L.J. Stockmeyer (Oct 1972). The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space (PDF). pp. 125–129. {{cite book}}: |work= ignored (help)
  21. ↑ L.J. Stockmeyer & A.R. Meyer (1973). Word Problems Requiring Exponential Time (PDF). pp. 1–9. {{cite book}}: |work= ignored (help)
  22. ↑ Hopcroft, Ullman (1979), Corollary p.353
  23. ↑ Weyer, Mark (2002). "Decidability of S1S and S2S". Automata, Logics, and Infinite Games. Lecture Notes in Computer Science. Vol. 2500. Springer. pp. 207–230. doi:10.1007/3-540-36387-4_12. ISBN 978-3-540-00388-5.
  24. ↑ Furst, Merrick; Saxe, James B.; Sipser, Michael (1984). "Parity, circuits, and the polynomial-time hierarchy". Mathematical Systems Theory. 17 (1): 13–27. doi:10.1007/BF01744431. MR 0738749. S2CID 14677270.
  25. ↑ Cook, Stephen; Nguyen, Phuong (2010). Logical foundations of proof complexity (1. publ. ed.). Ithaca, NY: Association for Symbolic Logic. p. 75. ISBN 978-0-521-51729-4.
  26. ↑ J. Hartmanis, P. L. Lewis II, and R. E. Stearns. Hierarchies of memory-limited computations. Proceedings of the 6th Annual IEEE Symposium on Switching Circuit Theory and Logic Design, pp. 179–190. 1965.
  27. ↑ "How to prove that a language is not regular?". cs.stackexchange.com. Retrieved 10 April 2018.
  28. ↑ Hromkovič, Juraj (2004). Theoretical computer science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography. Springer. pp. 76–77. ISBN 3-540-14015-8. OCLC 53007120.
  29. ↑ A finite language shouldn't be confused with a (usually infinite) language generated by a finite automaton.
  30. ↑ Volker Diekert; Paul Gastin (2008). "First-order definable languages" (PDF). In Jörg Flum; Erich Grädel; Thomas Wilke (eds.). Logic and automata: history and perspectives. Amsterdam University Press. ISBN 978-90-5356-576-6.
  31. ↑ 31.0 31.1 Honkala, Juha (1989). "A necessary condition for the rationality of the zeta function of a regular language". Theor. Comput. Sci. 66 (3): 341–347. doi:10.1016/0304-3975(89)90159-x. Zbl 0675.68034.
  32. ↑ Flajolet & Sedgweick, section V.3.1, equation (13).
  33. ↑ "Number of words in the regular language $(00)^*$". cs.stackexchange.com. Retrieved 10 April 2018.
  34. ↑ "Proof of theorem for arbitrary DFAs".
  35. ↑ "Number of words of a given length in a regular language". cs.stackexchange.com. Retrieved 10 April 2018.
  36. ↑ Flajolet & Sedgewick (2002) Theorem V.3
  37. ↑ Berstel, Jean; Reutenauer, Christophe (1990). "Zeta functions of formal languages". Trans. Am. Math. Soc. 321 (2): 533–546. CiteSeerX 10.1.1.309.3005. doi:10.1090/s0002-9947-1990-0998123-x. Zbl 0797.68092.
  38. ↑ Berstel & Reutenauer (2011) p.222
  39. ↑ Samuel Eilenberg. Automata, languages, and machines. Academic Press. in two volumes "A" (1974, ISBN 9780080873749) and "B" (1976, ISBN 9780080873756), the latter with two chapters by Bret Tilson.
  40. ↑ Straubing, Howard (1994). Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Basel: Birkhäuser. p. 8. ISBN 3-7643-3719-2. Zbl 0816.68086.
  41. ↑ Berstel & Reutenauer (2011) p.47
  42. ↑ Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press. p. 86. ISBN 978-0-521-84425-3. Zbl 1188.68177.


अग्रिम पठन

  • Kleene, S.C.: Representation of events in nerve nets and finite automata. In: Shannon, C.E., McCarthy, J. (eds.) Automata Studies, pp. 3–41. Princeton University Press, Princeton (1956); it is a slightly modified version of his 1951 RAND Corporation report of the same title, RM704.
  • Sakarovitch, J (1987). "Kleene's theorem revisited". Trends, Techniques, and Problems in Theoretical Computer Science. Lecture Notes in Computer Science. Vol. 1987. pp. 39–50. doi:10.1007/3540185356_29. ISBN 978-3-540-18535-2.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=नियमित_भाषा&oldid=99284’