ماشین پشته‌ای جاسازی‌شده

یک ماشین پشته‌ای جاسازی‌شده () یا EPDA یک مدل محاسباتی برای تجزیه زبان‌هایی که به وسیله گرامر درخت مجاور (TAG) تولید می‌شوند است. آن شبیه گرامر مستقل از متن ماشین پشته‌ای را تجزیه می‌کند به جز اینکه به جا استفاده از ماشین یک پشته ساده برای ذخیره سمبل‌ها، یک پشته از پشته‌های تاثیری که نمادها را ذخیره می‌کنند دارد، دادن گرامرهای درخت مجاور یک ظرفیت تولیدی بین گرامر مستقل از متن و گرامر حساس به متن، یا یک زیرمجموعه از گرامرهای حساس به متن ملایم است و ماشین پشته‌ای جاسازی شده نباید با ماشین پشته‌ای تودرتو که قدرت محاسباتی بیشتری دارد اشتباه گرفته شود.
تاریخچه و کاربرد
EPDAها ابتدا توسط K. Vijay-Shanker و در پایان‌نامه دکترایش تعریف شدند. آن‌ها برای تعریف‌های کامل‌تر از کلاس‌های گرامرهای حساس به متن ملایم درخواست شده‌اند و نقش مهمی در پالایش سلسله مراتب چامسکی داشته‌اند؛ بنابراین زیرگرامرهای متنوع، به طور مثال linear indexed grammar می‌تواند تعریف شود. EPDAها همچنین شروع کننده و ایفاکننده نقش مهمی در پردازش زبان طبیعی هستند.
در حالی که زبان‌های طبیعی به طور سنتی به وسیله گرامرهای مستقل از متن تجزیه و تحلیل می‌شده‌اند. transformational-generative grammar) وcomputational linguistics (این مدل برای زبان‌های با وابستگی ضربدری خوب کار نمی‌کند، از قبیل Dutch وضعیت‌ها برای یک EPDA خیلی مناسب است. یک تحلیل دقیق زبانی در دسترس است.
نظریه
یک EPDA یک ماشین با وضعیت‌های متناهی و یک مجموعه از پشته‌ها که از طریق پشته جاسازی شده به همدیگر دسترسی دارند، است. هر پشته شامل عناصری از الفبای پشته است و بنابراین ما یک عنصر از پشته را با (که بستار کلینی است) تعریف می‌کنیم.
هر پشته سپس می‌تواند به لحاظ عناصرش تعریف شود؛ بنابراین ما پشته jام را با استفاده از نماد دو خنجر معنی می‌کنیم. ,جایی که نماد بعدی قابل دستیابی در پشته است. پشته جاسازی شده از پشته می‌تواند به شکل زیر معنی شود.
ما یک EPDA را به وسیله یک ۷تایی تعریف می‌کنیم.
مجموعه محدودی از وضعیت‌ها است.
یک مجموعه محدود از الفبای ورودی است.
مجموعه متناهی از الفبای پشته است.
وضعیت شروع است.
مجموعه وضعیت‌های پایانی است.
نماد شروع پشته است.
تابع انتقال است که در آن یک زیرمجموعه متناهی از است.
بنابراین تابع انتقال یک وضعیت را با نماد بعدی از رشته ورودی و نماد روی پشته جاری می‌گیرد و وضعیت بعدی را تولید می‌کند. پشته‌ها داخل پشته جاسازی شده نشانده و برداشته می‌شوند، نشاندن و برداشتن از پشته جاری صورت می‌گیرد و پشته‌ها، پشته جار ی را در انتقال بعد در نظر می‌گیرند. به عبارت دقیق‌تر پشته جاسازی شده نشانده و برداشته می‌شود، پشته جاری به طور اختیاری داخل پشته جاسازی شده نشانده می‌شود و هر یک از گشته‌های دیگر بالای آن نشانده می‌شوند ودر بازگویی بعدی از آخرین پشته می‌خوانیم؛ بنابراین پشته‌ها می‌توانند بالا و پایین پشته جاری نشانده شوند.
یک وضعیت داده شده به صورت زیر تعریف می‌شود:
که در آن وضعیت جاری و‌ها پشته‌های داخل پشته جاسازی شده هستند و پشته جاری است و برای یک رشته ورودی ، بخشی از رشته است که با خواندن نماد جاری توسط head در حال حاضر به وسیله ماشین پردازش می‌شود و بخشی است که پردازش خواهد شد. دقت داشته باشید که رشته تهی به طور ضمنی به عنوان نماد پایان تعریف شده یعنی اگر ماشین در یک وضعیت پایانی باشد وقتی رشته تهی خوانده می‌شود، تمام رشته ورودی پذیرفته شده است و در غیراین صورت رد شده است. این رشته‌های پذیرفته شده عناصر زبان ما هستند.
که در آن و تابع انتقال است که با توجه به تجزیه رشته هر چند بار که لازم باشد استفاده شده است.
یک تعریف غیررسمی از EPDA همچنین می‌تواند در Joshi, Schabes (1997), Sect.7, p.23-25 پیدا شود.
EPDA ی k سطحی و بند سلسله مراتب
به طور دقیق‌تر سلسله مراتب زبان‌ها را که مرتبط با کلاس حساس به متن ملایم است را تعریف می‌کند که به وسیله David J. Weir انجام شده است. بر اساس کار سلسله مراتب کنترل زبان Weir عبارت است از سلسله مراتب مجموعه قابل شمارش از کلاس‌های زبان که سطح اول در آن به عنوان مستقل از متن و سطح دوم کلاس از درخت مجاور و سه گرامر دیگر است.
در زیر بعضی از. ویژگی‌های زبان‌های سطح k در سلسله مراتب آورده شده است:
زبان‌های سطح k در کلاس زبان سطح (k+1) هستند.
زبان‌های سطح k می‌توانند در زمان تجزیه شوند.
سطح k شامل زبان هست اما شامل نیست.
سطح k شامل زبان هست اما شامل نیست.
این ویژگی‌ها در ارتباط با kهای کوچک ولی بزرگتر از ۱ در شرایط حساس به متن ملایم خوب عمل می‌کنند اما هرچه k بزرگتر می‌شود، کلاس‌های زبان حساسیت به متن کمتری پیدا می‌کنند.