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

در نظریهٔ محاسبه، یک ماشین پشته‌ای مشبک، یک ماشین متناهی است که می‌تواند از پشته ی شامل داده‌هایی که ممکن است پشته‌های اضافی باشند، استفاده کند. مانند یک ماشین پشته‌ای، یک ماشین پشته‌ای مشبک ممکن است، در پشته، بالا یا پایین رود و نماد جاری را بخواند؛ علاوه بر این، ممکن است در هر مکانی یک پشتهٔ جدید بسازد، در آن عمل کند، در نهایت آن را خراب کند، و اجرا در پشتهٔ قدیمی را ادامه بدهد. بدین طریق، پشته‌ها می‌توانند به‌طور بازگشتی، تا یک عمق دلخواه مشبک شوند، اگرچه ماشین همیشه فقط در درونی‌ترین پشته عمل می‌کند. یک ماشین پشته‌ای مشبک قادر به شناسایی زبان شاخص دار است و در حقیقت مجموعهٔ زبان‌های شاخص دار، دقیقاً مجموعهٔ زبان‌های پذیرفته شده بوسیلهٔ ماشین پشته‌ای مشبک غیر قطعی یک طرفه است. ماشین پشته‌ای مشبک نباید با ماشین پشته‌ای محاط اشتباه گرفته شود، که توان محاسباتی کمتری دارد.

تعریف رسمی

ماشین

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

Q,Σ، Γ,δ،q0,Z0,F,[،],]

است که در آن:

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

به‌طور غیررسمی، نماد بالای یک پشته همراه با شاخص سمت چپ قبلی "]"، به عنوان یک نماد دیده می‌شود، سپس δ موارد زیر را می‌خواند:

  • وضعیت فعلی
  • نماد ورودی فعلی و
  • نماد پشته فعلی

و خروجی‌ها

  • وضعیت بعدی
  • مسیری که ورودی در آن حرکت می‌کند و
  • مسیری که پشته در آن حرکت می‌کند یا رشته‌ای از نمادها برای جایگذاری بالاترین نماد پشته
  • q0Q حالت آغازین است
  • Z0 ∈ Γ نماد پشته‌ای آغازین است
  • FQ مجموعه‌ای از وضعیت‌های پایانی است.

پیکره بندی

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

q, [a1a2...ai...an-1], [Z1X2...Xj...Xm-1] ›,

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

  • qQ وضعیت فعلی است.
  • [a1a2...ai...an-1]رشتهٔ ورودی است، برای راحتی [ =a0 = [ and an وضعیت فعلی ورودی تعریف می‌شود که در آن viz. i with 0 ≤ i ≤ n با نماد ترتیبی زیربنایی مشخص شده‌است.
  • [Z1X2...Xj...Xm-1] یک پشته است که شامل زیر پشته‌هایی می‌باشد، برای راحتی [ =X1 = [ Z1 and Xmتعریف می‌شود ، حالت فعلی در پشته viz که در آن . l ≤ j ≤ m است و با استفاده از نماد ترتیبی مشخص می‌شود.

مثال

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

Action Step Stack
۱: [ab[k][p]c]
create substack ۲: [ab[k][p[rs]]c]
pop ۳: [ab[k][p[s]]c]
pop ۴: [ab[k][p[]]c]
destroy substack ۵: [ab[k][p]c]
move down ۶: [ab[k][p]c]
move up ۷: [ab[k][p]c]
move up ۸: [ab[k][p]c]
push ۹: [ab[k][nop]c]

ویژگی‌ها

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

منابع

    Wikipedia contributors, "Nested stack automaton," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Nested_stack_automaton&oldid=617539076 (accessed January 20, 2015).

    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.