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

در گرایش نظریه زبان‌ها و ماشین‌ها از علوم کامپیوتر، زبان‌های پشته‌ای عیان (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) نیز بسته می‌باشد.
روابط متعددی برای زبان‌های فوق‌الذکر با دیگر زبان‌ها بیان‌شده است، که به عنوان مثال می‌توان به رابطه ابرکلاس بودن زبان‌های عطفی خطی، که خود زیرمجموعه‌ای از زبان‌های عطفی در حالت کلی هستند، برای مجموعه زبان‌های پشته‌ای عیان اشاره نمود. همین‌طور مخترعین کلاس زبان‌های پشته‌ای عیان یک زبرکلاس از زبان‌های درخت دودویی منظم را به این کلاس از زبان‌ها ارتباط داده‌اند.
تعریف رسمی
برای تعریف زبان‌های پشته‌ای عیان طبیعی است که ابتدا بایستی رابطه تناظر را تعریف نماییم. طبق روال معمول، برای هر عدد صحیح نامنفی همانند با نماد مجموعه‌ی را نمایش می‌دهیم. همین‌طور فرض می‌کنیم برابر با مجموعه تهی است.
در این صورت هر رابطه تناظر همانند ↝ بدین‌شکل خواهد بود که برای زیرمجموعه‌ای از خواهد بود چنان که:
تمام یال‌های آن رو به جلو هستند، یعنی چنان‌چه i ↝ j آن‌گاه i<j خواهد بود
هیچ دو یال موقعیت (مقدمه) یکسان ندارند، بدین‌معنی که برای هر حداکثر یک مقدمه مانند وجود دارد که h↝i و همین‌طور حداکثر یک وجود دارد که i↝j
هیچ دو یال از یک‌دیگر عبور نمی‌کنند، بدین‌معنی که اگر آن‌گاه هر دو رابطه i ↝ j و i’ ↝ j را نمی‌توان داشت
هر موقعیت (مقدمه) i نیز به یکی از صور زیر نام‌گذاری می‌شود:
موقعیت (مقدمه) فراخوانی (call) در صورتی که به ازای یک j ای داشته باشیم i ↝ j
موقعیت (مقدمه) پندینگ (pending) در صورتی که ↝ i
موقعیت (مقدمه) بازگشت (return) در صورتی که h ↝ i به ازای یک h
موقعیت (مقدمه) بازگشت پندینگ (pending return) در صورتی که i ↝ −∞
موقعیت (مقدمه) داخلی (internal) در تمام دیگر حالات
یک کلمه نهفته (Nested Word) به طول بر زبانی همچون  یک جفت همانند (↝,w) است طوری که w کلمه‌ای به طول بر زبان  می‌باشد و ↝ رابطه تناظری به طول می‌باشد.
زبان‌های مربوطه و ویژگی‌های آنها
همان‌گونه که از تعریف ماشین‌های پشته‌ای عیان (visibly pushdown automata) برمی‌آید، ماشین‌های پشته‌ای عیان تصمیم‌پذیر (deterministic visibly pushdown automata) یک حالت خاص از ماشین‌های پشته‌ای تصمیم‌پذیر (deterministic pushdown automata) می‌باشند، لذا مجموعه‌ی زبان‌های پشته‌ای عیان (VPL) بر هر زبان دلخواه زیرمجموعه‌ای از مجموعه‌ی زبان‌های پشته‌ای مستقل از متن تصمیم‌پذیر (DCFL) را تشکیل می‌دهند.
عملگرهایی که این مجموعه زبان‌ها تحت آنها بسته هستند
مجموعه‌ی زبان‌های پشته‌ای عیان (VPL) تحت عملگرهای زیر بسته هستند:
عملگرهای مجموعه‌ای:
اجتماع
اشتراک
متمم‌گیری
لذا مجموعه‌ی زبان‌های پشته‌ای عیان (VPL) تشکیل‌دهنده‌ی یک جبر بولی می‌باشد.
ستاره کلین (Kleene Star )
پیوست (Concatenation)
دیگر طرق توصیف
مدارهای بولی
توصیفات کلاس زبان‌های پشته‌ای عیان متعدد است، به عنوان مثال می‌توان با مدارهای بولی بدین‌نحو آنها را بیان کرد که معادل مساله تعیین کردن این هستند که آیا کلمه‌ای به طول L توسط یک چنین اتوماتایی پذیرفته می‌شود یا خیر، توسط یک چنین مداری با عمق از قابل حل هست یا خیر.