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

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

تعریف رسمی

ماشین

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

‹Q,Σ، Γ,δ،q₀,Z₀,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 × {ε می‌نگارد (حالت تخریب پشته). به‌طور غیررسمی، نماد بالای یک پشته همراه با شاخص سمت چپ قبلی "]"، به عنوان یک نماد دیده می‌شود، سپس δ موارد زیر را می‌خواند: وضعیت فعلی نماد ورودی فعلی و نماد پشته فعلی و خروجی‌ها وضعیت بعدی مسیری که ورودی در آن حرکت می‌کند و مسیری که پشته در آن حرکت می‌کند یا رشته‌ای از نمادها برای جایگذاری بالاترین نماد پشته q0 ∈ Q حالت آغازین است Z0 ∈ Γ نماد پشته‌ای آغازین است F ⊆ Q مجموعه‌ای از وضعیت‌های پایانی است.

پیکره بندی

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

‹ q, [a₁a₂...a_i...a_n-1], [Z₁X₂...X_j...X_m-1] ›,

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

• 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 است و با استفاده از نماد ترتیبی مشخص می‌شود.

مثال

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

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).