زبان‌های پشته‌ای عیان

در گرایش نظریه زبان‌ها و ماشین‌ها از علوم کامپیوتر، زبان‌های پشته‌ای عیان (Visibly Pushdown Languages) زبان‌هایی هستند که بین زبان های منظم (Regular Languages) و زبان‌های مستقل‌ازمتن تصمیم‌پذیر (Deterministic Context-free Languages) جای می‌گیرند. این زبان‌ها در سال ۲۰۰۴ میلادی توسط Alur and Madhusudan پیشنهاد شدند و در مدل کردن ساختارهای طبقاتی کاربرد دارند. این کلاس از زبان‌ها را به اختصار با نماد VPL نمایش می‌دهند.

از تعریف زبان‌های پشته‌ای عیان بر می‌آید که زبان‌های پشته‌ای عیان تصمیم‌پذیر (Deterministic Visibly Pushdown Languages) یک کلاس خاص از زبان‌های پشته‌ای تصمیم‌پذیر (Deterministic Pushdown Languages) و به عبارتی زیرمجموعه‌ای از آن‌ها باشند. مجموعهٔ زبان‌های پشته‌ای عیان تحت اعمال اشتراک، اجتماع و متمم‌گیری بسته می‌باشد، لذا تشکیل‌دهنده یک جبر بولی (Boolean Algebra) می‌باشد. همین‌طور این مجموعه تحت اعمال ستاره کلین (Kleene Star [۱]) و پیوست (Concatenation) نیز بسته می‌باشد.

روابط متعددی برای زبان‌های فوق‌الذکر با دیگر زبان‌ها بیان‌شده‌است، که به عنوان مثال می‌توان به رابطه اَبَرکلاس بودن زبان‌های عطفی خطی، که خود زیرمجموعه‌ای از زبان‌های عطفی در حالت کلی هستند، برای مجموعه زبان‌های پشته‌ای عیان اشاره نمود. همین‌طور مخترعین کلاس زبان‌های پشته‌ای عیان یک زِبَرکلاس از زبان‌های درخت دودویی منظم را به این کلاس از زبان‌ها ارتباط داده‌اند.

تعریف رسمی

برای تعریف زبان‌های پشته‌ای عیان طبیعی است که ابتدا بایستی رابطه تناظر را تعریف نماییم. طبق روال معمول، برای هر عدد صحیح نامنفی همانند $\ell$با نماد [$\ell$] مجموعه‌ی$\{1,2,\ldots ,\ell -1,\ell \}$ را نمایش می‌دهیم. همین‌طور فرض می‌کنیم [ $0$] برابر با مجموعه تهی است.

در این صورت هر رابطه تناظر همانند ↝ بدین‌شکل خواهد بود که برای  $\ell \geq 0$ زیرمجموعه‌ای از$\{-\infty ,1,2,\ldots ,\ell -1,\ell \}\times \{1,2,\ldots ,\ell -1,\ell ,\infty \}$خواهد بود چنان که:

1. تمام یال‌های آن رو به جلو هستند، یعنی چنان‌چه i ↝ j آن‌گاه i<j خواهد بود
2. هیچ دو یال موقعیت (مقدمه) یکسان ندارند، بدین‌معنی که برای هر $-\infty <i<+\infty$حداکثر یک مقدمه مانند $h$وجود دارد که h↝i و همین‌طور حداکثر یک $j$وجود دارد که i↝j
3. هیچ دو یال از یک‌دیگر عبور نمی‌کنند، بدین‌معنی که اگر $i<i'\leqslant j<j'$آن‌گاه هر دو رابطه i ↝ j و 'i’ ↝ j را نمی‌توان داشت

هر موقعیت (مقدمه) i نیز به یکی از صور زیر نام‌گذاری می‌شود:

• موقعیت (مقدمه) فراخوانی (call) در صورتی که به ازای یک j ای داشته باشیم i ↝ j
• موقعیت (مقدمه) پندینگ (pending) در صورتی که $\infty$↝ i
• موقعیت (مقدمه) بازگشت (return) در صورتی که h ↝ i به ازای یک h
• موقعیت (مقدمه) بازگشت پندینگ (pending return) در صورتی که i ↝ −∞
• موقعیت (مقدمه) داخلی (internal) در تمام دیگر حالات

یک کلمه نهفته (Nested Word) به طول $\ell$بر زبانی همچون Σ یک جفت همانند (↝,w) است طوری که w کلمه‌ای به طول $\ell$بر زبان Σ می‌باشد و ↝ رابطه تناظری به طول $\ell$می‌باشد.

زبان‌های مربوطه و ویژگی‌های آنها

همان‌گونه که از تعریف ماشین‌های پشته‌ای عیان (visibly pushdown automata) برمی‌آید، ماشین‌های پشته‌ای عیان تصمیم‌پذیر (deterministic visibly pushdown automata) یک حالت خاص از ماشین‌های پشته‌ای تصمیم‌پذیر (deterministic pushdown automata) می‌باشند، لذا مجموعهٔ زبان‌های پشته‌ای عیان (VPL) بر هر زبان دلخواه زیرمجموعه‌ای از مجموعهٔ زبان‌های پشته‌ای مستقل از متن تصمیم‌پذیر (DCFL) را تشکیل می‌دهند.

عملگرهایی که این مجموعه زبان‌ها تحت آنها بسته هستند

مجموعهٔ زبان‌های پشته‌ای عیان (VPL) تحت عملگرهای زیر بسته هستند:

• عملگرهای مجموعه‌ای:
  • اجتماع
  • اشتراک
  • متمم‌گیری

لذا مجموعهٔ زبان‌های پشته‌ای عیان (VPL) تشکیل‌دهندهٔ یک جبر بولی می‌باشد.

• ستاره کلین (Kleene Star [۲])
• پیوست (Concatenation)

مدارهای بولی

توصیفات کلاس زبان‌های پشته‌ای عیان متعدد است، به عنوان مثال می‌توان با مدارهای بولی بدین‌نحو آن‌ها را بیان کرد که معادل مساله تعیین کردن این هستند که آیا کلمه‌ای به طول L توسط یک چنین اتوماتایی پذیرفته می‌شود یا خیر، توسط یک چنین مداری با عمق از $\mathrm {O} (\log \ell )$قابل حل هست یا خیر.