Nested stack automaton
ઓટોમેટા સિદ્ધાંતમાં, નેસ્ટેડ સ્ટૅક ઓટોમેટન એ એક મર્યાદિત ઓટોમેટન છે જે ડેટા ધરાવતા સ્ટેકનો ઉપયોગ કરી શકે છે જે વધારાના સ્ટેક્સ હોઈ શકે છે. સ્ટેક ઓટોમેટનની જેમ, નેસ્ટેડ સ્ટેક ઓટોમેટન સ્ટેકમાં ઉપર અથવા નીચે જઈ શકે છે, અને વર્તમાન પ્રતીક વાંચી શકે છે; વધુમાં, તે કોઈપણ જગ્યાએ નવો સ્ટેક બનાવી શકે છે, તેના પર કામ કરી શકે છે, આખરે તેનો નાશ કરી શકે છે અને જૂના સ્ટેક પર કામ કરવાનું ચાલુ રાખી શકે છે. આ રીતે, સ્ટેક્સને મનસ્વી ઊંડાઈ સુધી પુનરાવર્તિત રીતે ગોઠવી શકાય છે; જો કે, ઓટોમેટન હંમેશા માત્ર સૌથી અંદરના સ્ટેક્સ પર કામ કરે છે. નેસ્ટેડ સ્ટૅક ઓટોમેટન અનુક્રમિત ભાષાને ઓળખવા માટે સક્ષમ છે, અને હકીકતમાં અનુક્રમિત ભાષાઓનો વર્ગ બરાબર એક તરફી બિનનિર્ધારિત નેસ્ટેડ સ્ટેક ઓટોમેટા દ્વારા સ્વીકૃત ભાષાઓનો વર્ગ છે. નેસ્ટેડ સ્ટૅક ઓટોમેટાને એમ્બેડેડ પુશડાઉન ઓટોમેટા સાથે ભેળસેળ ન કરવી જોઈએ, જેમાં ઓછી કોમ્પ્યુટેશનલ શક્તિ હોય છે. ઔપચારિક વ્યાખ્યા ઓટોમેટન એ (બિનનિર્ધારણીય દ્વિ-માર્ગીય) નેસ્ટેડ સ્ટૅક ઓટોમેટન એ એક ટુપલ છે જ્યાં ક્યુ, એસયુ, અને એસયુ એ અનુક્રમે સ્થિતિઓ, ઇનપુટ પ્રતીકો અને સ્ટેક પ્રતીકોનો બિન-ખાલી મર્યાદિત સમૂહ છે, [,], અને] એ વિશિષ્ટ વિશેષ પ્રતીકો છે જે એસયુમાં સમાવિષ્ટ નથી, [ઇનપુટ સ્ટ્રિંગ અને (પેટા) સ્ટેક સ્ટ્રિંગ બંને માટે ડાબી એન્ડમાર્કર તરીકે વપરાય છે,] નો ઉપયોગ આ સ્ટ્રિંગ્સ માટે જમણી એન્ડમાર્કર તરીકે થાય છે,] નો ઉપયોગ સમગ્ર સ્ટેકને સૂચવતા સ્ટ્રિંગના અંતિમ એન્ડમાર્કર તરીકે થાય છે. વિસ્તૃત ઇનપુટ મૂળાક્ષરની વ્યાખ્યા β '= β [,]} દ્વારા કરવામાં આવે છે, વિસ્તૃત સ્ટૅક મૂળાક્ષરની વ્યાખ્યા β' = β [,]} દ્વારા કરવામાં આવે છે, અને ઇનપુટનો સમૂહ D = {-1,0, + 1} દ્વારા દિશાઓ ખસેડે છે. δ, મર્યાદિત નિયંત્રણ, એ Q × β '× (β' β [β], []]) માંથી Q × D × ([β * β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 સાથે, સંબંધિત પ્રતીકને રેખાંકિત કરીને ચિહ્નિત થયેલ છે. ઉદાહરણ એક ઉદાહરણ રન (ઇનપુટ સ્ટ્રિંગ બતાવેલ નથી): ગુણધર્મો જ્યારે ઓટોમેટાને તેમના ઇનપુટ ("દ્વિ-માર્ગી ઓટોમેટા") ને ફરીથી વાંચવાની મંજૂરી આપવામાં આવે છે, ત્યારે નેસ્ટેડ સ્ટેક્સ સાદા સ્ટેક્સની તુલનામાં વધારાની ભાષા ઓળખવાની ક્ષમતાઓમાં પરિણમતા નથી. ગિલમેન અને શાપિરોએ ચોક્કસ જૂથોમાં સમસ્યા શબ્દને ઉકેલવા માટે નેસ્ટેડ સ્ટેક ઓટોમેટાનો ઉપયોગ કર્યો હતો. નોંધો સંદર્ભો ગણતરીના નમૂનાઓ ઓટોમેટા (ગણતરી)