ماشین پشته‌ای مشبک

ماشین

یک ماشین پشته‌ای مشبک غیر قطعی دو طرفه، چندتایی

است که در آن:

• Q , Σ و Γ یک مجموعهٔ متناهی غیر تهی به ترتیب از وضعیت‌ها، نمادهای ورودی، و نمادهای پشته‌ای می‌باشد.
• [,] و ] نمادهای خاص متفاوت غیر مشمول در Σ ∪ Γ است.
  • [ به عنوان مشخصهٔ پایانی سمت چپ هم برای رشتهٔ ورودی و هم رشتهٔ زیر دسته‌ای استفاده می‌شود.
  • ] به عنوان مشخصهٔ پایانی سمت راست برای این رشته‌ها استفاده می‌شود.
  • ] به عنوان مشخصهٔ نهایی رشته‌ای که کل دسته را نشان می‌دهد، استفاده می‌شود.
• یک الفبای ورودی گسترده به وسیلهٔ Σ' = Σ ∪ {[,]} تعریف می‌شود، یک الفبای دسته‌ای گسترده بوسیلهٔ Γ' = Γ ∪{]} و مجموعهٔ جهت‌های حرکت ورودی توسط {D = {-۱٬۰، +۱ تعریف می‌شود.
• δ یعنی کنترل متناهی، نگاشتی از({[],[} ∪ 'Q × Σ' × (Γ' ∪ [Γ به زیر مجموعهٔ متناهی (Q × D ×([Γ* ∪ D است ، چنان‌که δ نگاشت‌های زیر را انجام می‌دهد:

یک پیکره بندی یا توصیف آنی از چنین ماشینی، از ۳ تایی

تشکیل شده‌است که در آن:

• q ∈ Q وضعیت فعلی است.
• [a₁a₂...ai...an-1]رشتهٔ ورودی است، برای راحتی [ =a₀ = [ and a_n وضعیت فعلی ورودی تعریف می‌شود که در آن viz. i with 0 ≤ i ≤ n با نماد ترتیبی زیربنایی مشخص شده‌است.
• [Z₁X₂...Xj...Xm-1] یک پشته است که شامل زیر پشته‌هایی می‌باشد، برای راحتی [ =X₁ = [ Z₁ and X_mتعریف می‌شود ، حالت فعلی در پشته viz که در آن . l ≤ j ≤ m است و با استفاده از نماد ترتیبی مشخص می‌شود.

یک مثال اجرا می‌شود( رشتهٔ ورودی نشان داده نشده‌است )

وقتی که به ماشین اجازهٔ خواندن مجدد ورودی‌های خود داده می‌شود، پشته‌های مشبک در مقایسه با پشته‌های ساده، منجر به توانایی‌های شناسایی زبان‌های دیگر نمی‌شود. گلیمن و شاپیرو از ماشین پشته‌ای مشبک برای حل مشکل کلمه در گروه‌های خاص استفاده کردند.