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

یک ماشین پشته ای جاسازی شده (انگلیسی: Embedded pushdown automaton) یا EPDA یک مدل محاسباتی برای تجزیه زبان هایی که به وسیلهٔ گرامر درخت مجاور (TAG) تولید می شوند است. آن شبیه گرامر مستقل از متن ماشین پشته ای را تجزیه می کند به جز اینکه به جا استفاده از ماشین یک پشتهٔ ساده برای ذخیره سمبل ها، یک پشته از پشته های تأثیری که نمادها را ذخیره می کنند دارد، دادن گرامرهای درخت مجاور یک ظرفیت تولیدی بین گرامر مستقل از متن و گرامر حساس به متن، یا یک زیرمجموعه از گرامرهای حساس به متن ملایم است و ماشین پشته ای جاسازی شده نباید با ماشین پشته ای تودرتو که قدرت محاسباتی بیشتری دارد اشتباه گرفته شود.
EPDAها ابتدا توسط K. Vijay-Shanker و در پایان نامه دکترایش تعریف شدند. آن ها برای تعریف های کامل تر از کلاس های گرامرهای حساس به متن ملایم درخواست شده اند و نقش مهمی در پالایش سلسله مراتب چامسکی داشته اند؛ بنابراین زیرگرامرهای متنوع، به طور مثال linear indexed grammar می تواند تعریف شود. EPDAها همچنین شروع کننده و ایفاکنندهٔ نقش مهمی در پردازش زبان طبیعی هستند.
در حالی که زبان های طبیعی به طور سنتی به وسیلهٔ گرامرهای مستقل از متن تجزیه و تحلیل می شده اند. transformational-generative grammar) وcomputational linguistics (این مدل برای زبان های با وابستگی ضربدری خوب کار نمی کند، از قبیل Dutch وضعیت ها برای یک EPDA خیلی مناسب است. یک تحلیل دقیق زبانی در دسترس است.
یک EPDA یک ماشین با وضعیت های متناهی و یک مجموعه از پشته ها که از طریق پشته جاسازی شده به همدیگر دسترسی دارند، است. هر پشته شامل عناصری از الفبای پشته Γ {\displaystyle \,\Gamma }   است و بنابراین ما یک عنصر از پشته را با σ i ∈ Γ ∗ {\displaystyle \,\sigma _{i}\in \Gamma ^{*}}   (که بستار کلینی است) تعریف می کنیم.