नियमित भाषा

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

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

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

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

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

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

उदाहरण

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

कम्प्यूटेशनल जटिलता सिद्धांत में, सभी नियमित भाषाओं की जटिलता वर्ग को कभी-कभी REGULAR या REG के रूप में संदर्भित किया जाता है और DSPACE(O(1)) के बराबर होता है, निर्णय की समस्या जिसे निरंतर स्थान में हल किया जा सकता है (उपयोग किया गया स्थान इनपुट आकार से स्वतंत्र है) ). नियमित ≠ AC0, क्योंकि इसमें (तुच्छ रूप से) यह निर्धारित करने की समता समस्या है कि इनपुट में 1 बिट की संख्या सम है या विषम है और यह समस्या AC0 में नहीं है।^{दूसरी ओर, REGULAR में AC0 शामिल नहीं है, क्योंकि विलोमपदों की अनियमित भाषा, या अनियमित भाषा$\{0^{n}1^{n}:n\in \mathbb {N} \}$ दोनों को AC0 में पहचाना जा सकता है। यदि कोई भाषा नियमित नहीं है, तो उसे पहचानने के लिए कम से कम बिग ओ नोटेशन |Ω(लॉग लॉग एन) स्थान वाली मशीन की आवश्यकता होती है (जहां एन इनपुट आकार है)। दूसरे शब्दों में, डीएसपीएसीई (बिग ओ नोटेशन (लॉग लॉग एन)) नियमित भाषाओं की कक्षा के बराबर है। व्यवहार में, कम से कम लघुगणकीय स्थान लेने वाली मशीनों द्वारा अधिकांश अनियमित समस्याओं का समाधान किया जाता है।}

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

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

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

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

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

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

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

$S_{L}(z)=\sum _{n\geq 0}s_{L}(n)z^{n}\ .$

यदि L नियमित है तो भाषा L का जनक कार्य एक तर्कसंगत कार्य है। इसलिए हर नियमित भाषा के लिए $L$ क्रम $s_{L}(n)_{n\geq 0}$ स्थिर-पुनरावर्ती क्रम है|निरंतर-पुनरावर्ती; अर्थात्, एक पूर्णांक स्थिरांक मौजूद है $n_{0}$, जटिल स्थिरांक $\lambda _{1},\,\ldots ,\,\lambda _{k}$ और जटिल बहुपद $p_{1}(x),\,\ldots ,\,p_{k}(x)$ ऐसा कि प्रत्येक के लिए $n\geq n_{0}$ जो नंबर $s_{L}(n)$ लंबाई के शब्दों की $n$ में $L$ है $s_{L}(n)=p_{1}(n)\lambda _{1}^{n}+\dotsb +p_{k}(n)\lambda _{k}^{n}$. इस प्रकार, कुछ भाषाओं की गैर-नियमितता $L'$ दी गई लम्बाई के शब्दों को गिनकर सिद्ध किया जा सकता है $L'$. उदाहरण के लिए, संतुलित कोष्ठकों के तार की डाइक भाषा पर विचार करें। लंबाई के शब्दों की संख्या $2n$ डाइक भाषा में कैटलन संख्या के बराबर है $C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}$, जो स्वरूप का न हो $p(n)\lambda ^{n}$, डाइक भाषा की गैर-नियमितता का साक्षी। कुछ eigenvalues ​​​​के बाद से देखभाल की जानी चाहिए $\lambda _{i}$ समान परिमाण हो सकता है। उदाहरण के लिए, लंबाई के शब्दों की संख्या $n$ सबकी भाषा में द्विअर्थी शब्द भी रूप का नहीं है $p(n)\lambda ^{n}$, लेकिन सम या विषम लंबाई के शब्दों की संख्या इस रूप की है; संबंधित eigenvalues ​​​​हैं $2,-2$. सामान्य तौर पर, प्रत्येक नियमित भाषा के लिए एक स्थिरांक मौजूद होता है $d$ ऐसा कि सभी के लिए $a$, लंबाई के शब्दों की संख्या $dm+a$ असम्बद्ध रूप से है $C_{a}m^{p_{a}}\lambda _{a}^{m}$. किसी भाषा L का जीटा फलन है

$\zeta _{L}(z)=\exp \left({\sum _{n\geq 0}s_{L}(n){\frac {z^{n}}{n}}}\right)\ .$

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

सामान्यीकरण

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

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

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

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

संदर्भ

• Berstel, Jean; Reutenauer, Christophe (2011). Noncommutative rational series with applications. Encyclopedia of Mathematics and Its Applications. Vol. 137. Cambridge: Cambridge University Press. ISBN 978-0-521-19022-0. Zbl 1250.68007.
• Eilenberg, Samuel (1974). Automata, Languages, and Machines. Volume A. Pure and Applied Mathematics. Vol. 58. New York: Academic Press. Zbl 0317.94045.
• Salomaa, Arto (1981). Jewels of Formal Language Theory. Pitman Publishing. ISBN 0-273-08522-0. Zbl 0487.68064.
• Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Zbl 1169.68300. Chapter 1: Regular Languages, pp. 31–90. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp. 152–155.
• Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics: Symbolic Combinatorics. Online book, 2002.
• John E. Hopcroft; Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X.
• Alfred V. Aho and John E. Hopcroft and Jeffrey D. Ullman (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. ISBN 9780201000290.

अग्रिम पठन

• 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.

बाहरी संबंध

• Complexity Zoo: Class REG