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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

تعریف رسمی[ویرایش]

ماشین[ویرایش]

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

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
۱: [a b [k ] [p ] c ]
create substack ۲: [a b [k ] [p [r s ] ] c ]
pop ۳: [a b [k ] [p [s ] ] c ]
pop ۴: [a b [k ] [p [] ] c ]
destroy substack ۵: [a b [k ] [p ] c ]
move down ۶: [a b [k ] [p ] c ]
move up ۷: [a b [k ] [p ] c ]
move up ۸: [a b [k ] [p ] c ]
push ۹: [a b [k ] [n o p ] 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).