नियमितता क्या है?

Question

यह एक प्रोग्रामिंग की तुलना में कंप्यूटर विज्ञान प्रश्न का अधिक है, लेकिन मुझे लगता है कि यह पूछने के लिए सभी संबंधित साइटों में से यह सबसे अच्छा स्थान है।

जब मैंने नियमित अभिव्यक्तियों की खोज की और मुझे लगता है कि "नियमितता" की यह संपत्ति इस तथ्य को संदर्भित करती है कि अभिव्यक्ति की भाषा का एक निश्चित संरचनात्मक पैटर्न है। हालांकि, इस विषय और इसके पीछे सिद्धांत के बारे में पढ़ने में मैंने सीखा कि ऐसी भाषाएं हैं जो नियमित नहीं हैं, और फिर भी जिस तरह से परिभाषित किया गया है, यह स्पष्ट है कि उनके साथ एक पैटर्न का मिलान किया जा सकता है। ऐसी एक भाषा है (ए^एन) (बी^एन)। स्पष्ट रूप से यह एक पैटर्न है, और फिर भी यह एक नियमित भाषा नहीं है। तो अब मैं सोच रहा हूं कि नियमित भाषाओं के बारे में क्या है जो उन्हें नियमित बनाता है, और यह भाषा नहीं?

Answer 1

नाम की व्युत्पत्ति, क्लेन के 1 9 50 के दशक के काम से नियमित सेट का वर्णन करती है जिसका उद्देश्य उद्देश्य के लिए बनाए गए गणितीय नोटेशन का उपयोग करता है। this देखें।

Answer 2

regularregular expression में नियमित रूप से गणितीय अवधारणा को संदर्भित करता है, अंग्रेजी अवधारणा नहीं। गणित में prime शब्द प्राइम गोमांस से थोड़ा सा संबंध कैसे है।

यह सीएस (जो गणित की एक शाखा है) द्वारा विरासत में मिली है एक अधिक विशिष्ट अवधारणा का उल्लेख करने के: http://en.wikipedia.org/wiki/Regular_language

Answer 3

नियमित अभिव्यक्ति वास्तव में नियमित रूप से नहीं कर रहे हैं, नाम व्युत्पत्ति है।

Answer 4

शायद regular languages पर विकिपीडिया लेख इसे बेहतर तरीके से समझा सकता है। हालांकि, मैं इसे एक शॉट दे दूँगा।

सैद्धांतिक दृष्टिकोण से, एक नियमित भाषा (तारों का सेट) एक है जिसे finite state automaton का उपयोग करके उत्पन्न किया जा सकता है। प्रोग्रामर शब्दों में, यह कहने के बराबर है कि इसे regular expressions का उपयोग करके उत्पन्न किया जा सकता है। इस प्रकार, सभी परिमित भाषाओं (तारों के सेट) नियमित हैं, लेकिन ^एन बी ^एन (ना के बाद के सभी तारों की भाषा एन बी के बाद) जैसी कुछ अनंत भाषाएं हैं जिन्हें उपयोग नहीं किया जा सकता है एक एफएसए या नियमित अभिव्यक्तियां। अधिक शक्तिशाली कम्प्यूटेशनल डिवाइस (जैसे कि आधुनिक कंप्यूटर, जिन्हें Turing Machines का उपयोग करके मॉडलिंग किया गया है) हैं जो उन भाषाओं को पहचान सकते हैं।

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

Answer 5

सहजता से कंप्यूटर विज्ञान समझाता है ... मुश्किल। मैं इसे एक शॉट दूंगा, लेकिन ध्यान रखें कि इनमें से कुछ "पर्याप्त करीब" होने जा रहा है लेकिन सैद्धांतिक रूप से कठोर नहीं है।

एक नियमित भाषा एक है कि एक मशीन एक परिमित ऑटोमेटा (DFA/NDFA) करने के लिए कम्प्यूटेशनल बराबर है कि द्वारा निर्णय लिया जा सकता है। एक सीमित ऑटोमाटा को एक मशीन के रूप में सोचा जा सकता है जो पूरी तरह से राज्यों में संचालित नहीं होता है, कोई भंडारण नहीं होता है। तो आप देख सकते हैं कि एक ⁿ ख ⁿ नियमित नहीं किया जा सकता, क्योंकि यह एक मशीन है कि एक और ख के की संख्या की गणना कर सकते हैं (और इस प्रकार अनंत * भंडारण क्षमता होनी चाहिए) आदेश उनकी तुलना करने में की आवश्यकता है।

तुलना के लिए, (एबीसी) ⁿ, नियमित रूप से है क्योंकि repetitions की संख्या अप्रासंगिक है।

अधिक कठोर (और संगत रूप से घने दृश्य) के लिए wikipedia article और लिंक किए गए पृष्ठों की जांच करें।

_{* अनंत यहां कोई फर्क नहीं पड़ता है, लेकिन मैं इसे पूर्णता के लिए उल्लेख करता हूं। इसे "सौभाग्य से, हमेशा पर्याप्त" भंडारण के रूप में सोचना आसान हो सकता है।}