Nested stack automaton
தானியங்கி கோட்பாட்டில், ஒரு உள்ளமைக்கப்பட்ட அடுக்கு தானியங்கி இயந்திரம் என்பது ஒரு வரையறுக்கப்பட்ட தானியங்கி இயந்திரமாகும், இது கூடுதல் அடுக்குகளாக இருக்கக்கூடிய தரவைக் கொண்ட அடுக்கைப் பயன்படுத்த முடியும். ஒரு அடுக்கு தானியங்கி இயந்திரத்தைப் போலவே, ஒரு உள்ளமைக்கப்பட்ட அடுக்கு தானியங்கி இயந்திரம் அடுக்கில் மேலே அல்லது கீழே இறங்கலாம், மேலும் தற்போதைய சின்னத்தைப் படிக்கலாம்; கூடுதலாக, அது எந்த இடத்திலும் ஒரு புதிய அடுக்கை உருவாக்கலாம், அதில் செயல்படலாம், இறுதியில் அதை அழித்து, பழைய அடுக்கில் தொடர்ந்து செயல்படலாம். இந்த வழியில், அடுக்குகளை ஒரு தன்னிச்சையான ஆழத்திற்கு மீண்டும் மீண்டும் கூடு கட்டலாம்; இருப்பினும், தானியங்கி இயந்திரம் எப்போதும் உள் அடுக்கில் மட்டுமே இயங்குகிறது. ஒரு நெஸ்டட் ஸ்டேக் ஆட்டோமேட்டன் ஒரு குறியீட்டு மொழியை அடையாளம் காணும் திறன் கொண்டது, உண்மையில் குறியீட்டு மொழிகளின் வகுப்பு சரியாக ஒரு வழி நிர்ணயிக்கப்படாத நெஸ்டட் ஸ்டேக் ஆட்டோமேட்டாவால் ஏற்றுக்கொள்ளப்பட்ட மொழிகளின் வகுப்பாகும். நெஸ்டட் ஸ்டாக் ஆட்டோமேட்டாவை உட்பொதிக்கப்பட்ட புஷ் டவுன் ஆட்டோமேட்டாவுடன் குழப்பக்கூடாது, அவை குறைந்த கணக்கீட்டு சக்தியைக் கொண்டுள்ளன. முறையான வரையறை ஆட்டோமெட்டன் ஏ (வரையறுக்கப்படாத இரு வழி) நெஸ்டட் ஸ்டேக் ஆட்டோமெட்டன் என்பது ஒரு டப்பிள் ஆகும், இதில் க்யூ, எஸ், மற்றும் ஜாதம் முறையே ஒரு வெற்றிடமற்ற வரையறுக்கப்பட்ட நிலைகள், உள்ளீட்டு சின்னங்கள் மற்றும் அடுக்கு சின்னங்கள், [,], மற்றும்] ஆகியவை தனித்துவமான சிறப்பு சின்னங்களாகும், அவை ஜாதத்தில் இல்லை, [உள்ளீட்டு சரம் மற்றும் ஒரு (துணை) அடுக்கு சரம் ஆகிய இரண்டிற்கும் இடது இறுதி முத்திரையாக பயன்படுத்தப்படுகிறது,] இந்த சரங்களுக்கு வலது இறுதி முத்திரையாக பயன்படுத்தப்படுகிறது,] முழு அடுக்கையும் குறிக்கும் சரத்தின் இறுதி இறுதி முத்திரையாக பயன்படுத்தப்படுகிறது. ஒரு நீட்டிக்கப்பட்ட உள்ளீட்டு எழுத்துக்கள் '=' [,] 'ஆல் வரையறுக்கப்படுகின்றன, ஒரு நீட்டிக்கப்பட்ட அடுக்கு எழுத்துக்கள்' = '[,]' ஆல் வரையறுக்கப்படுகின்றன, மேலும் உள்ளீட்டு நகர்வு திசைகளின் தொகுப்பு D = {-1,0, + 1} ஆல் வரையறுக்கப்படுகிறது. δ, வரையறுக்கப்பட்ட கட்டுப்பாடு, என்பது Q ×  நிஷ்பத்தியற்ற துணைக்குழுக்களாக Q × D × இன் வரையறுக்கப்பட்ட துணைக்குழுக்களில் ஒரு வரைபடமாகும், அதாவது δ முறைசாரா முறையில் வரைபடம் செய்கிறது, ஒரு (துணை) அடுக்கின் மேல் சின்னம் அதன் முந்தைய இடது இறுதி முத்திரையுடன் "[" ஒற்றை சின்னமாக பார்க்கப்படுகிறது; பின்னர் δ தற்போதைய நிலை, தற்போதைய உள்ளீட்டு சின்னம் மற்றும் தற்போதைய அடுக்கு சின்னத்தைப் படிக்கிறது, மேலும் அடுத்த நிலை, உள்ளீட்டில் நகர வேண்டிய திசை மற்றும் அடுக்கின் மீது நகர வேண்டிய திசை அல்லது மிக உயர்ந்த அடுக்கு சின்னத்தை மாற்றுவதற்கான சின்னங்களின் சரம் ஆகியவற்றை வெளியிடுகிறது. q0 என்பது ஆரம்ப நிலை, Z0 என்பது ஆரம்ப அடுக்கு சின்னம், F என்பது இறுதி நிலைகளின் தொகுப்பு. ஒரு உள்ளமைவு, அல்லது அத்தகைய தானியங்கி இயந்திரத்தின் உடனடி விளக்கம் மூன்று மடங்காக உள்ளது, அங்கு q ωQ என்பது தற்போதைய நிலை, [a1a2.ai.an-1] உள்ளீட்டு சரம்; வசதிக்காக, a0 = [மற்றும் an =] உள்ளீட்டில் தற்போதைய நிலை வரையறுக்கப்படுகிறது, அதாவது. 0 ≤ i ≤ n உடன் i, அந்தந்த சின்னத்தை அடிக்கோடிட்டுக் காட்டுவதன் மூலம் குறிக்கப்படுகிறது. [Z1X2.Xj.Xm-1] என்பது அடுக்குகள் உட்பட அடுக்காகும்; வசதிக்காக, X1 = [Z1 மற்றும் Xm =] வரையறுக்கப்படுகிறது. அடுக்கில் தற்போதைய நிலை, அதாவது. 1 ≤ j ≤ m உடன், அந்தந்த சின்னத்தை அடிக்கோடிட்டுக் காட்டுவதன் மூலம் குறிக்கப்படுகிறது. எடுத்துக்காட்டு ஒரு எடுத்துக்காட்டு ஓட்டம் (உள்ளீட்டு சரம் காட்டப்படவில்லை): பண்புகள் தானியங்கி உள்ளீட்டை ("இரு வழி தானியங்கி") மீண்டும் படிக்க அனுமதிக்கப்படும்போது, எளிய அடுக்குகளுடன் ஒப்பிடும்போது, உள்ளமைக்கப்பட்ட அடுக்குகள் கூடுதல் மொழி அங்கீகார திறன்களை ஏற்படுத்தாது. கில்மேன் மற்றும் ஷாபிரோ ஆகியோர் சில குழுக்களில் சிக்கல் என்ற வார்த்தையை தீர்க்க நெஸ்டட் ஸ்டாக் ஆட்டோமேட்டாவைப் பயன்படுத்தினர். குறிப்புகள் குறிப்புகள் கணக்கீட்டு மாதிரிகள் தானியங்கி (கணக்கீடு)