موضوع مقاله: اتوماتون پشته‌ای | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # اتوماتون پشته‌ای | مقدمه: اتوماتون پشته‌ای صوری‌سازی این مفهوم شهودی، یک تعریف دقیق از آتاماتون پشته‌ای بدست می‌دهد. | ## بخش 1: اتوماتون پشته‌ای | تعریف: یک پذیرندهٔ پشته‌ای غیر قطعی(NPDA) به شکل ( M=(Q،∑، Γ، ∂،qo،z،F نمایش داده می‌شود، بطوری‌که در آن Qیک مجموعه متناهی از حالت‌های داخلی واحد کنترل است، ∑الفبای ورودی است، Γ یک مجموعه متناهی از نشانه‌ها که الفبای پشته نامیده می‌شود، (∂:Q×(∑υ{⋋ ×Γ تابع انتقال، Q0€Q حالت اولیه واحد کنترل است، z€Γ≤Qنشانهٔ شروع پشته است شکل پیچیده دامنه و برد تابع انتقال نیاز به بررسی بیشتری دارد.آرگومان ∂ حالت‌های فعلی واحد کنترل، نشانه ورودی فعلی و نشانهٔ بالای پشته است.نتیجه یک مجموعه از زوج‌های (q،x) می‌باشد که در آن q حالت بعدی در واحد کنترل است.رشتهٔ x نیز به جای نشانه‌ای که اکنون بر روی پشته است قرار می‌گیرد.به خاطر داشته باشیم که دومین آرگومان∂ ممکن است برابر با⋋ باشد؛ بنابراین حرکتی که هیچ نشانه‌ای را از ورودی مصرف نمی‌کند امکان‌پذیر است. به چنین حرکتی، یک انتقال -⋋ گفته می‌شود.همچنین ∂ طوری تعریف شده‌است که به نشانهٔ موجود بر روی پشته نیاز دارد. اگر پشته خالی باشد هیچ حرکتی ممکن نیست.بالاخره اینکه، برد تابع انتقال یابد باید یک زیرمجموعه محدود باشد زیرا Q×Γ نامتناهی بوده و بنابراین دارای تعداد نامتناهای زیرمجموعه است. انتخاب‌های زیادی برای حرکت داشته باشد، این انتخاب‌ها باید به یک مجموعه متناهی از حالت‌ها محدود باشد. اگر در یک لحظهٔ مشخص، واحد کنترل در حالت q1، نشانه ورودی برابر با a و نشانه موجود در بالای پشته نیز برابر با b باشد، یکی از دو مورد زیر اتقاف می افتد: 1)واحد کنترل به حالت q2 می‌رودو رشتهٔ cd جایگزین نشانهٔ بالای پشته می‌شود. در این روش نشانه گذاری، اضافه کردن یک رشته به پشته، به صورت نشانه به نشانه و از انتهای راست آن رشته انجام می‌شود. عملکرد چپ|قاب|نمودار اتومات پشته ای اتومات پشته‌ای با ماشین‌های حالات متناهی در دو چیز متفاوت اند: 1-آن‌ها می‌توانند از قسمت بالا پشته استفاده کنند که کدان انتقال صورت گیرد. | ## بخش 2: اتوماتون پشته‌ای | اتوماتون پشته‌ای انتقال را انتخاب می‌کند که با نمایه‌سازی یک جدول توسط سیگنال ورودی، وضعیت فعلی و نماد در بالای پشته است.این به این معنا است که این سه پارامتر مسیر انتقال را انتخاب می‌کنند.ماشین‌های وضیعت محدود تنها به سیگنال‌های ورودی وحالت حاضر نگاه می‌کنند.اتومات پشته ای, پشته‌ای را به عنوان پارامتری برای انتخاب اضافه می‌کنند. انوماتون پشته‌ای می‌تواند بخشی از پشته را برای انتقال دستکاری کنند.ماشین‌های وضیعت محدود حالت جدیدی را که نتیجه انتقال است را انتخاب می‌کند.دستکاری‌ها یا می‌توانند به صورت وارد یا خارج کردن نماد خاصی از پشته باشد.دستکاری شدن یا نشدن توسط جدول انتقال معلوم می‌شود. با هم شدن:با توجه به سیگنال ورودی، وضعیت فعلی و نماد پشته،اتومات می‌تواند دنبال کند انتقال را به حالت دیگر و به صورت اختیاری پشته را دستکاری کند. به‌طور کلی اتوماتون پشته‌ای ممکن است محاسبات متعددی روی سیگنال‌های ورودی انجام دهد.اگر در هر موقعیت فقط یک انتقال برای ادامه محاسبات باشد در آن صورت نتیجه اتوماتون پشتهای قطعی است.(DPDA) در غیر این صورت اتوماتون پشتهای غیر قطعی می‌شود(NDPDA) .تنها در گرامر مستقل از متن می‌شود گرامرهای مبهم را از طریق DPDA یعنی گرامرمستقل از متن قطعی,شناخت.تمام گرامرهای مستقل از متن , قطعی نیستند و مشکل شناخت گرامر مستقل از متن قطعی حل نشده‌است.Greibach, Sheila (October 1966). اگرما اجازه دسترسی به 2 پشته به جای یک پشته داشتیم آنگاه وسیله‌ای قوی به مانند ماشین تورینگ داشتیم.اتوماتون خطی محدود ابزاری قوی تر از اتوماتون پشته‌ای است ولی از ماشین تورینگ ضعیف تر است. تعریف رسمی مااز نمادهای استاندارد زبان رسمی استفاده می‌کنیم: به رشته‌ای از حروف و و به رشته‌ای خالی اشاره می‌کند. اتوماتون پشته‌ای عموماً تبعیض ناپذیرند که در حالت لحظه‌ای چندین راه ممکن است باشد.هر کدام از این روش‌ها ممکن است انتخاب شوند.با تعاریف بالا در هر مرحله سمبل منفرد از بالای پشته خارج می‌شود و با نمادهایی که لازم تر است جایگزین می‌شود.به عنوان نتیجه هیچ مرحله‌ای که زمانی پشته خالی است انجام نمی‌شود. | ## بخش 3: اتوماتون پشته‌ای | محاسبات اتوماتون پشته‌ای دنباله‌ای از مراحل است.محاسبات با حالت اولیه و سمبل پشته‌ای اولیه و رشته ورودی آغاز می‌شود, بنابراین در حالت اولیه داریم .دو حالت پذیرش اولیه داریم.روش دیگر پذیرش از طریق حالت نهایی است.به این معنی است که پس از خواندن ورودی آن ماشین به یک حالت مورد قبول می‌رسد یا به وسیله پشته خالی پذیرش می‌شود.حالت پذیرش برای اولین بار با استفاده از حافظه داخلی و حلت دوم توسط حافظه خارجی است. بعبارت دیگر تعریف کنیم: و با با برای هر اتوماتون پشته‌ای این دو رابطه ربطی به هم ندارند.شاید در بعضی جاها با هم برابر باشند ولی دلیلی بر یکی بودن نیست.مشخصات ماشین نیز باید حالت مورد نظر را پذیرش می‌باشد.در تمامی اتوماتون پشته‌ای 2 حالت پذیرش بیانگر زبان یکی‌اند. توصیف آنی توصیف آنی یک سه‌تایی منظم به فرم (q,w,α) است که در آن: 1- q یک حالت باشد. ضمناً برای نمایش حروف الفبا معمولاً از b,a,...، برای نمایش حرف‌های پشته از Y,X,... (iii) .پذیرش محاسبه: در حالت پذیرش به پایان میرسد.، در حالی که ورودی کامل خوانده شده‌است. | ## جمع‌بندی | اتوماتون پشته‌ای عمومی GPDA یک نوع PDA است که رشته‌هایی را با طول مساوی درون پشته مینویسد و تمام رشته هارا از پشته خارج می‌کند.