Global index grammar
वैश्विक सूचकांक व्याकरण (जी. आई. जी.) प्राकृतिक भाषा व्याकरण और जीनोम व्याकरण सहित कई घटनाओं को मॉडल करने के लिए कास्टानो (2004) में पेश किए गए व्याकरण का एक वर्ग है। अनुक्रमित व्याकरण की तुलना में जी. आई. जी. का सबसे आसान विवरण है। जबकि अनुक्रमित व्याकरण में, सूचकांकों का एक ढेर प्रत्येक गैर-अंतिम प्रतीक के साथ जुड़ा होता है, और व्युत्पत्ति के पाठ्यक्रम के आधार पर एक से दूसरे में भिन्न हो सकता है, एक जी. आई. जी. में, एक एकल वैश्विक सूचकांक ढेर होता है जिसे व्युत्पत्ति के दौरान हेरफेर किया जाता है (जो किसी भी पुनर्लेखन संचालन के लिए सख्ती से बचा होता है जो एक प्रतीक को ढेर पर धकेलता है)। वैश्विक ढेर के अस्तित्व के कारण, एक जी. आई. जी. व्युत्पत्ति को पूर्ण माना जाता है जब कोई गैर-अंतिम प्रतीक फिर से लिखने के लिए नहीं बचे होते हैं, और ढेर खाली होता है। नियम विवरण जी. आई. जी. नियम अनिवार्य रूप से चार रूपों में आते हैंः नियम जो कुछ बिना शर्त करते हैं, नियम जो स्टैक के शीर्ष प्रतीक पर कुछ सशर्त करते हैं, नियम जो स्टैक को धक्का देते हैं, और नियम जो स्टैक से पॉप होते हैं। हम इन्हें बारी-बारी से इस प्रकार नोट कर सकते हैंः {।--।। (बिना शर्त ए को फिर से लिखें, स्टैक पर कुछ न करें)।-। (ए को फिर से लिखें जैसे कि एफ सबसे शीर्ष स्टैक प्रतीक है, स्टैक पर कुछ नहीं कर रहा है)।-। (बिना शर्त ए को फिर से लिखें और एफ को स्टैक पर दबाएं)।-। (सशर्त रूप से ए को फिर से लिखें जैसे कि एफ स्टैक का सबसे शीर्ष प्रतीक है, फिर स्टैक से पॉप एफ)।} जहां एफ कोई सूचकांक प्रतीक है, टर्मिनलों और/या गैर-टर्मिनल प्रतीकों की कोई भी स्ट्रिंग है, और एक्स एक टर्मिनल है जो एक टर्मिनल प्रतीक है। क्योंकि कभी-कभी एक पुनर्लेखन नियम को किसी अर्थ में स्टैक के खाली होने पर शर्त लगाने की आवश्यकता हो सकती है, प्रतीक #का उपयोग सबसे निचले स्टैक प्रतीक के रूप में किया जाता है, जिसका अर्थ है कि एक "खाली" स्टैक में बिल्कुल एक प्रतीक होता है, #। तीसरा नियम रूप, पुश नियम, इंगित किया जाना चाहिए, क्योंकि यह पॉप नियम से अलग है जिसमें आवश्यक है कि सभी पुश संचालन व्युत्पत्ति स्ट्रिंग में कम से कम एक नया टर्मिनल प्रतीक पेश करें। इस बाधा के बिना, व्याकरण का वर्ग टाइप-0 होगा और इस प्रकार ट्यूरिंग पूर्ण होगा। उदाहरण इस उदाहरण के लिए, हम व्युत्पत्ति स्ट्रिंग को एक ढेर के ऊपर रखकर व्युत्पत्ति में चरणों को निरूपित करेंगे। जी. आई. जी. (लेकिन नीचे दिए गए रूप में टी. आर. जी. आई. जी. नहीं) निम्नलिखित व्याकरण का उपयोग करके गैर-अनुक्रमित भाषा उत्पन्न कर सकते हैंः स्ट्रिंग के लिए एक व्युत्पत्ति इस प्रकार हैः, और ऐसे अन्य वाक्यों के लिए एक समान व्युत्पत्ति का अनुसरण किया जाता है। कम्प्यूटेशनल शक्ति वैश्विक सूचकांक भाषाएँ संदर्भ संवेदनशील भाषाओं का एक उपसमुच्चय हैं, और संदर्भ मुक्त भाषाओं का एक सुपरसेट हैं। यह ज्ञात है कि जी. आई. जी. मिक्स/बाख भाषा उत्पन्न कर सकते हैं, जहाँ पी स्ट्रिंग क्रमपरिवर्तन फलन है, जिसका अनुमान (लेकिन सिद्ध नहीं) एक अनुक्रमित भाषा के रूप में प्रतिनिधित्व करने योग्य नहीं है। यह ज्ञात नहीं है कि सभी आई. जी. भी जी. आई. जी. हैं या नहीं। यह पूरी तरह से संभव है कि जी. आई. जी. और आई. जी. सी. एस. एल. के केवल अतिव्यापी उपसमुच्चय का वर्णन करते हैं। जी. आई. जी. का एक उपवर्ग टी. आर. जी. आई. जी. का वर्ग है, जो पॉप और पुश नियमों को समान बनाता है, इसके लिए आवश्यक है कि पॉप नियम भी व्युत्पत्ति में कम से कम एक अंतिम प्रतीक पेश करें। उदाहरण भाषा की विशेषता वाले इस तरह के व्याकरण का एक उदाहरण हैः स्ट्रिंग के लिए व्युत्पत्ति तब हैः संदर्भ औपचारिक भाषा व्याकरण संरचना