Nested stack automaton
অটোমাটা তত্ত্বে, একটি নেস্টেড স্ট্যাক অটোমেটন হল একটি সীমাবদ্ধ অটোমেটন যা ডেটা ধারণকারী একটি স্ট্যাক ব্যবহার করতে পারে যা অতিরিক্ত স্ট্যাক হতে পারে। স্ট্যাক অটোমেটন-এর মতো, একটি নেস্টেড স্ট্যাক অটোমেটন স্ট্যাকের মধ্যে উপরে বা নিচে নামতে পারে এবং বর্তমান প্রতীকটি পড়তে পারে; উপরন্তু, এটি যে কোনও জায়গায় একটি নতুন স্ট্যাক তৈরি করতে পারে, তার উপর কাজ করতে পারে, শেষ পর্যন্ত এটি ধ্বংস করতে পারে এবং পুরানো স্ট্যাকের উপর কাজ চালিয়ে যেতে পারে। এইভাবে, স্ট্যাকগুলি একটি নির্বিচারে গভীরতায় পুনরাবৃত্তিমূলকভাবে নেস্ট করা যেতে পারে; তবে, অটোমেটন সর্বদা শুধুমাত্র ভিতরের স্ট্যাকের উপর কাজ করে। একটি নেস্টেড স্ট্যাক অটোমেটন একটি সূচীভুক্ত ভাষাকে চিনতে সক্ষম, এবং প্রকৃতপক্ষে সূচীভুক্ত ভাষাগুলির শ্রেণীটি ঠিক একমুখী অনির্ধারিত নেস্টেড স্ট্যাক অটোমাটা দ্বারা গৃহীত ভাষাগুলির শ্রেণী। নেস্টেড স্ট্যাক অটোমাটাকে এমবেডেড পুশডাউন অটোমাটার সাথে বিভ্রান্ত করা উচিত নয়, যার গণনামূলক শক্তি কম। আনুষ্ঠানিক সংজ্ঞা অটোমেটন এ (অনির্ধারিত দ্বিমুখী) নেস্টেড স্ট্যাক অটোমেটন হল একটি টুপল যেখানে কিউ, এস, এবং এস, যথাক্রমে স্টেট, ইনপুট চিহ্ন এবং স্ট্যাক প্রতীকগুলির একটি নন-এম্প্টি ফাইনাইট সেট, [,], এবং] স্বতন্ত্র বিশেষ চিহ্ন যা এস এ অন্তর্ভুক্ত নয়, [ইনপুট স্ট্রিং এবং একটি (সাব) স্ট্যাক স্ট্রিং উভয়ের জন্য বাম এন্ডমার্কার হিসাবে ব্যবহৃত হয়,] এই স্ট্রিংয়ের জন্য ডান এন্ডমার্কার হিসাবে ব্যবহৃত হয়,] স্ট্রিংয়ের চূড়ান্ত এন্ডমার্কার হিসাবে পুরো স্ট্যাককে বোঝায়। একটি বর্ধিত ইনপুট বর্ণমালা দ্বারা সংজ্ঞায়িত করা হয় '=' [,] ', একটি বর্ধিত স্ট্যাক বর্ণমালা দ্বারা' = '[,]', এবং ইনপুট স্থানান্তর নির্দেশাবলীর সেট দ্বারা D = {-1,0, + 1}। δ, সসীম নিয়ন্ত্রণ, হল একটি ম্যাপিং যা Q × β '× (γ' ≤ [γ '≤ [], []]) থেকে Q × D × ([γ * ≤ D)-এর সসীম উপসেটগুলিতে, যেমন δ অনানুষ্ঠানিকভাবে ম্যাপ করে, একটি (উপ) স্ট্যাকের শীর্ষ প্রতীকটি তার পূর্ববর্তী বাম প্রান্তচিহ্ন "[" এর সাথে একক প্রতীক হিসাবে দেখা হয়; তারপর δ বর্তমান অবস্থা, বর্তমান ইনপুট প্রতীক এবং বর্তমান স্ট্যাক প্রতীকটি পড়ে এবং পরবর্তী অবস্থা, ইনপুটটিতে যে দিকে যেতে হবে, এবং স্ট্যাকের উপর যে দিকে যেতে হবে, বা শীর্ষস্থানীয় স্ট্যাক প্রতীক প্রতিস্থাপনের জন্য প্রতীকগুলির স্ট্রিং আউটপুট করে। Q হল প্রাথমিক অবস্থা, Z0 হল প্রাথমিক স্ট্যাক প্রতীক, F হল চূড়ান্ত অবস্থার সেট। কনফিগারেশন একটি কনফিগারেশন, বা এই ধরনের অটোম্যাটনের তাৎক্ষণিক বিবরণ একটি ট্রিপল নিয়ে গঠিত, যেখানে q ωQ হল বর্তমান অবস্থা, [a1a2.ai.an-1] হল ইনপুট স্ট্রিং; সুবিধার জন্য, a0 = [এবং an =] সংজ্ঞায়িত করা হয় ইনপুটের বর্তমান অবস্থান, অর্থাৎ। 0 ≤ i ≤ n সহ i, সংশ্লিষ্ট প্রতীককে আন্ডারলাইন করে চিহ্নিত করা হয়। [Z1X2.Xj.Xm-1] হল স্ট্যাক, সাবস্ট্যাক সহ; সুবিধার জন্য, X1 = [[Z1 এবং Xm =] সংজ্ঞায়িত করা হয়। স্ট্যাকের বর্তমান অবস্থান, অর্থাৎ। 1 ≤ জে ≤ মি সহ জে, সংশ্লিষ্ট প্রতীককে আন্ডারলাইন করে চিহ্নিত করা হয়। উদাহরণ একটি উদাহরণ রান (ইনপুট স্ট্রিং দেখানো হয়নি): বৈশিষ্ট্যগুলি যখন স্বয়ংক্রিয়ভাবে তাদের ইনপুট ("দ্বিমুখী স্বয়ংক্রিয়") পুনরায় পড়ার অনুমতি দেওয়া হয়, তখন নেস্টেড স্ট্যাকের ফলে সাধারণ স্ট্যাকের তুলনায় অতিরিক্ত ভাষা শনাক্তকরণ ক্ষমতা পাওয়া যায় না। গিলম্যান এবং শাপিরো নির্দিষ্ট গোষ্ঠীতে সমস্যা শব্দটি সমাধান করতে নেস্টেড স্ট্যাক অটোমাটা ব্যবহার করেছিলেন। তথ্যসূত্র গণনার মডেল অটোমাটা (গণনা)