Parikh's theorem
सैद्धांतिक कंप्यूटर विज्ञान में पारिख की प्रमेय कहती है कि यदि कोई संदर्भ-मुक्त भाषा में प्रत्येक अंतिम प्रतीक की घटनाओं की संख्या को केवल उनके क्रम की परवाह किए बिना देखता है, तो भाषा एक नियमित भाषा से अप्रभेद्य है। यह तय करने के लिए उपयोगी है कि दी गई संख्या में टर्मिनलों वाले स्ट्रिंग्स को संदर्भ-मुक्त व्याकरण द्वारा स्वीकार नहीं किया जाता है। यह पहली बार 1961 में रोहित पारिख द्वारा साबित किया गया था और 1966 में पुनः प्रकाशित किया गया था। परिभाषाएँ और औपचारिक कथन एक वर्णमाला होने चाहिए। किसी शब्द के पारिख सदिश को उस फलन के रूप में परिभाषित किया जाता है, जिसके द्वारा दिया जाता है कि वह शब्द में अक्षर की घटनाओं की संख्या को दर्शाता है। एक उपसमुच्चय को रैखिक कहा जाता है यदि यह कुछ वैक्टरों के रूप में होता है। के एक उपसमुच्चय को अर्ध-रैखिक कहा जाता है यदि यह परिमित रूप से कई रैखिक उपसमुच्चय का एक संघ है। संक्षेप में, संदर्भ-मुक्त भाषाओं और नियमित भाषाओं की छवि समान है, और यह अर्धरेखीय समुच्चयों के समूह के बराबर है। दो भाषाओं को पारस्परिक रूप से समतुल्य कहा जाता है यदि उनके पास पारिख वैक्टर का एक ही समूह है। इस प्रकार, प्रत्येक संदर्भ-मुक्त भाषा कम्यूटेटिव रूप से किसी नियमित भाषा के बराबर है। सबूत दूसरे भाग को साबित करना आसान है। पहला भाग कम आसान है। निम्नलिखित प्रमाण का श्रेय गोल्डस्टीन को दिया जाता है। सबसे पहले हमें संदर्भ-मुक्त भाषाओं के लिए पंपिंग लेम्मा को थोड़ा मजबूत करने की आवश्यकता हैः प्रमाण अनिवार्य रूप से मानक पंपिंग लेम्मा के समान हैः सबसे छोटे व्युत्पत्ति वृक्ष में सबसे लंबे मार्ग में कुछ गैर-अंतिम प्रतीक की प्रतियां खोजने के लिए कबूतर छेद सिद्धांत का उपयोग करें। सीमित भाषाओं के लिए सुदृढ़ीकरण एक भाषा सीमित होती है यदि कुछ निश्चित शब्दों के लिए। गिन्सबर्ग और स्पैनियर ने बंधी हुई भाषाओं के लिए पारिख के प्रमेय के समान एक आवश्यक और पर्याप्त शर्त दी। एक रैखिक समुच्चय को स्तरीकृत कहें, यदि प्रत्येक वेक्टर के लिए इसकी परिभाषा में यह गुण है कि इसमें अधिकतम दो गैर-शून्य निर्देशांक हैं, और प्रत्येक के लिए यदि प्रत्येक वैक्टर में क्रमशः दो गैर-शून्य निर्देशांक हैं, और, तो उनका क्रम नहीं है। एक अर्ध-रैखिक समुच्चय को स्तरीकृत किया जाता है यदि यह परिमित रूप से कई स्तरीकृत रैखिक उपसमुच्चय का एक संघ है। महत्व प्रमेय की कई व्याख्याएँ हैं। यह दर्शाता है कि एक सिंगलटन वर्णमाला पर एक संदर्भ-मुक्त भाषा एक नियमित भाषा होनी चाहिए और कुछ संदर्भ-मुक्त भाषाओं में केवल अस्पष्ट व्याकरण हो सकते हैं। ऐसी भाषाओं को स्वाभाविक रूप से अस्पष्ट भाषा कहा जाता है। एक औपचारिक व्याकरण के दृष्टिकोण से, इसका मतलब है कि कुछ अस्पष्ट संदर्भ-मुक्त व्याकरण को समतुल्य स्पष्ट संदर्भ-मुक्त व्याकरण में परिवर्तित नहीं किया जा सकता है। संदर्भ औपचारिक भाषाएँ