ماشین پشته‌ای جاسازی‌شده کیست؟ توضیح بده.
یک ماشین پشته‌ای جاسازی‌شده () یا EPDA یک مدل محاسباتی برای تجزیه زبان‌هایی که به وسیلهٔ گرامر درخت مجاور (TAG) تولید می‌شوند است. آن شبیه گرامر مستقل از متن ماشین پشته‌ای را تجزیه می‌کند به جز اینکه به جا استفاده از ماشین یک پشتهٔ ساده برای ذخیره سمبل‌ها، یک پشته از پشته‌های تأثیری که نمادها را ذخیره می‌کنند دارد، دادن گرامرهای درخت مجاور یک ظرفیت تولیدی بین گرامر مستقل از متن و گرامر حساس به متن، یا یک زیرمجموعه از گرامرهای حساس به متن ملایم است و ماشین پشته‌ای جاسازی شده نباید با ماشین پشته‌ای تودرتو که قدرت محاسباتی بیشتری دارد اشتباه گرفته شود.تاریخچه و کاربرد.EPDAها ابتدا توسط K. Vijay-Shanker و در پایان‌نامه دکترایش تعریف شدند. آن‌ها برای تعریف‌های کامل تر از کلاس‌های گرامرهای حساس به متن ملایم درخواست شده‌اند و نقش مهمی در پالایش سلسله مراتب چامسکی داشته‌اند؛ بنابراین زیرگرامرهای متنوع، به‌طور مثال linear indexed grammar می‌تواند تعریف شود. EPDAها همچنین شروع‌کننده و ایفاکنندهٔ نقش مهمی در پردازش زبان طبیعی هستند.در حالی که زبان‌های طبیعی به‌طور سنتی به وسیلهٔ گرامرهای مستقل از متن تجزیه و تحلیل می‌شده‌اند. transformational-generative grammar) وcomputational linguistics (این مدل برای زبان‌های با وابستگی ضربدری خوب کار نمی‌کند، از قبیل Dutch وضعیت‌ها برای یک EPDA خیلی مناسب است. یک تحلیل دقیق زبانی در دسترس است.نظریه.یک EPDA یک ماشین با وضعیت‌های متناهی و یک مجموعه از پشته‌ها که از طریق پشته جاسازی شده به همدیگر دسترسی دارند، است. هر پشته شامل عناصری از الفبای پشته formula_1 است و بنابراین ما یک عنصر از پشته را با formula_2 (که بستار کلینی است) تعریف می‌کنیم.هر پشته سپس می‌تواند به لحاظ عناصرش تعریف شود؛ بنابراین ما پشتهٔ jام را با استفاده از نماد دو خنجر معنی می‌کنیم. formula_3,جایی که نماد بعدیformula_4 قابل دستیابی در پشته است. پشته جاسازی شده از پشته می‌تواند به شکل زیر معنی شود.formula_5ما یک EPDA را به وسیلهٔ یک ۷تایی تعریف می‌کنیم.مجموعهٔ محدودی از وضعیت‌ها است. formula_7یک مجموعهٔ محدود از الفبای ورودی است. formula_8formula_1 مجموعهٔ متناهی از الفبای پشته است.formula_10 وضعیت شروع است.مجموعهٔ وضعیت‌های پایانی است. formula_11نماد شروع پشته است. formula_12formula_13تابع انتقال است که در آن formula_14 یک زیرمجموعهٔ متناهی از formula_15 است.بنابراین تابع انتقال یک وضعیت را با نماد بعدی از رشتهٔ ورودی و نماد روی پشتهٔ جاری می‌گیرد و وضعیت بعدی را تولید می‌کند. پشته‌ها داخل پشتهٔ جاسازی شده نشانده و برداشته می‌شوند، نشاندن و برداشتن از پشتهٔ جاری صورت می‌گیرد و پشته‌ها، پشتهٔ جار ی را در انتقال بعد در نظر می‌گیرند. به عبارت دقیق تر پشتهٔ جاسازی شده نشانده و برداشته می‌شود، پشته جاری به‌طور اختیاری داخل پشتهٔ جاسازی شده نشانده می‌شود و هر یک از گشته‌های دیگر بالای آن نشانده می‌شوند و در بازگویی بعدی از آخرین پشته می‌خوانیم؛ بنابراین پشته‌ها می‌توانند بالا و پایین پشتهٔ جاری نشانده شوند.یک وضعیت داده شده به صورت زیر تعریف می‌شود:که در آن formula_17 وضعیت جاری و formula_18ها پشته‌های داخل پشتهٔ جاسازی شده هستند و formula_19 پشتهٔ جاری است و برای یک رشتهٔ ورودی formula_20، formula_21 بخشی از رشته است که با خواندن نماد جاری توسط head در حال حاضر به وسیلهٔ ماشین پردازش می‌شود وformula_22 بخشی است که پردازش خواهد شد. دقت داشته باشید که رشتهٔ تهی formula_23 به‌طور ضمنی به عنوان نماد پایان تعریف شده یعنی اگر ماشین در یک وضعیت پایانی باشد وقتی رشتهٔ تهی خوانده می‌شود، تمام رشتهٔ ورودی پذیرفته شده‌است و در غیراین صورت رد شده‌است. این رشته‌های پذیرفته شده عناصر زبان ما هستند.که در آن formula_25و formula_26 تابع انتقال است که با توجه به تجزیهٔ رشته هر چند بار که لازم باشد استفاده شده‌است.یک تعریف غیررسمی از EPDA همچنین می‌تواند در Joshi, Schabes (1997), Sect.7, p.23-25 پیدا شود.EPDA ی k سطحی و بند سلسله مراتب.به‌طور دقیق تر سلسله مراتب زبان‌ها را که مرتبط با کلاس حساس به متن ملایم است را تعریف می‌کند که به وسیلهٔ David J. Weir انجام شده‌است. بر اساس کار سلسله مراتب کنترل زبان Weir عبارت است از سلسله مراتب مجموعه قابل شمارش از کلاس‌های زبان که سطح اول در آن به عنوان مستقل از متن و سطح دوم کلاس از درخت مجاور و سه گرامر دیگر است.در زیر بعضی از. ویژگی‌های زبان‌های سطح k در سلسله مراتب آورده شده‌است:زبان‌های سطح k در کلاس زبان سطح (k+1) هستند.زبان‌های سطح k می‌توانند در زمان formula_27 تجزیه شوند.سطح k شامل زبان formula_28 هست اما شامل formula_29 نیست.سطح k شامل زبان formula_30 هست اما شامل formula_31نیست.این ویژگی‌ها در ارتباط با kهای کوچک ولی بزرگتر از ۱ در شرایط حساس به متن ملایم خوب عمل می‌کنند اما هرچه k بزرگتر می‌شود، کلاس‌های زبان حساسیت به متن کمتری پیدا می‌کنند.