Nested stack automaton
آٹومیٹا تھیوری میں، ایک نیسٹڈ اسٹیک آٹومیٹن ایک محدود آٹومیٹن ہے جو ڈیٹا پر مشتمل اسٹیک کا استعمال کر سکتا ہے جو اضافی اسٹیک ہو سکتا ہے۔ اسٹیک آٹومیٹن کی طرح، ایک نیسٹڈ اسٹیک آٹومیٹن اسٹیک میں اوپر یا نیچے جا سکتا ہے، اور موجودہ علامت کو پڑھ سکتا ہے ؛ اس کے علاوہ، یہ کسی بھی جگہ پر ایک نیا اسٹیک بنا سکتا ہے، اس پر کام کر سکتا ہے، آخر کار اسے تباہ کر سکتا ہے، اور پرانے اسٹیک پر کام جاری رکھ سکتا ہے۔ اس طرح، اسٹیکوں کو من مانی گہرائی تک بار بار گھونسلہ بنایا جا سکتا ہے ؛ تاہم، آٹومیٹن ہمیشہ صرف اندرونی اسٹیک پر کام کرتا ہے۔ ایک نیسٹڈ اسٹیک آٹومیٹن ایک انڈیکسڈ زبان کو پہچاننے کی صلاحیت رکھتا ہے، اور درحقیقت انڈیکسڈ زبانوں کی کلاس بالکل وہی کلاس ہے جو یک طرفہ غیر متعین نیسٹڈ اسٹیک آٹومیٹا کے ذریعہ قبول کی جاتی ہے۔ نیسٹڈ اسٹیک آٹومیٹا کو سرایت شدہ پش ڈاؤن آٹومیٹا کے ساتھ الجھن میں نہیں ڈالنا چاہیے، جس میں کمپیوٹیشنل طاقت کم ہوتی ہے۔ رسمی تعریف آٹومیٹن اے (غیر تعیناتی دو طرفہ) نیسٹڈ اسٹیک آٹومیٹن ایک ٹپل ہے جہاں کیو، ایس، اور ایس، اسٹیٹس، ان پٹ علامتوں، اور اسٹیک علامتوں کا ایک غیر خالی محدود مجموعہ ہے، بالترتیب، [،]، اور] الگ الگ خاص علامتیں ہیں جو ایس میں موجود نہیں ہیں، [ان پٹ سٹرنگ اور (ذیلی) اسٹیک سٹرنگ دونوں کے لیے لیفٹ اینڈ مارکر کے طور پر استعمال ہوتا ہے،] ان سٹرنگز کے لیے رائٹ اینڈ مارکر کے طور پر استعمال ہوتا ہے،] سٹرنگ کے حتمی اینڈ مارکر کے طور پر استعمال ہوتا ہے جو پورے اسٹیک کو ظاہر کرتا ہے۔ ایک توسیعی ان پٹ حروف تہجی کی تعریف σ '= β [،]}، ایک توسیعی اسٹیک حروف تہجی کی طرف سے β' = β []}، اور ان پٹ حرکت کی سمتوں کا مجموعہ D = {-1,0, + 1} کے ذریعے کیا جاتا ہے۔ δ، فینیٹ کنٹرول، ایک نقشہ سازی ہے جو Q × β '× (β' β [β]، []]) سے Q × D × ([β * βD) کے محدود ذیلی سیٹوں میں ہوتی ہے، جیسے کہ β غیر رسمی طور پر نقشہ بناتا ہے، ایک (ذیلی) اسٹیک کی اوپری علامت کو اس کے پچھلے بائیں اینڈ مارکر کے ساتھ مل کر "[" کو ایک واحد علامت کے طور پر دیکھا جاتا ہے۔ پھر δ موجودہ حالت، موجودہ ان پٹ علامت، اور موجودہ اسٹیک علامت کو پڑھتا ہے، اور اگلی حالت، جس سمت میں ان پٹ پر منتقل ہونا ہے، اور اس سمت کو آؤٹ پٹ کرتا ہے جس میں اسٹیک پر منتقل ہونا ہے، یا سب سے اوپر اسٹیک علامت کو تبدیل کرنے کے لیے علامتوں کی تار۔ q0 ωQ ابتدائی حالت ہے، Z0 ων ابتدائی اسٹیک کی علامت ہے، FωQ حتمی حالتوں کا مجموعہ ہے۔ ترتیب ایک ترتیب، یا اس طرح کے آٹومیٹن کی فوری تفصیل ٹرپل پر مشتمل ہوتی ہے، جہاں q ωQ موجودہ حالت ہے، [a1a2.ai.an-1] ان پٹ سٹرنگ ہے ؛ سہولت کے لیے، a0 = [اور an =] کی وضاحت کی جاتی ہے۔ i کو 0 ≤ i ≤ n کے ساتھ، متعلقہ علامت کو واضح کر کے نشان زد کیا جاتا ہے۔ [Z1X2.Xj.Xm-1] اسٹیک ہے، بشمول سب اسٹیکس ؛ سہولت کے لیے، X1 = [Z1 اور Xm =] کی وضاحت کی گئی ہے۔ اسٹیک میں موجودہ پوزیشن، یعنی۔ 1 ≤ j ≤ m کے ساتھ، متعلقہ علامت کو واضح کر کے نشان زد کیا جاتا ہے۔ مثال ایک مثال رن (ان پٹ سٹرنگ نہیں دکھائی گئی): خصوصیات جب آٹومیٹا کو ان کے ان پٹ ("دو طرفہ آٹومیٹا") کو دوبارہ پڑھنے کی اجازت دی جاتی ہے، تو نیسٹڈ اسٹیکس کے نتیجے میں سادہ اسٹیکس کے مقابلے میں زبان کی شناخت کی اضافی صلاحیتیں نہیں ہوتی ہیں۔ گلمین اور شاپیرو نے بعض گروپوں میں لفظ مسئلہ کو حل کرنے کے لیے نیسٹڈ اسٹیک آٹومیٹا کا استعمال کیا۔ نوٹ حوالہ جات کمپیوٹیشن آٹومیٹا (کمپیوٹیشن) کے ماڈل