حروف معین
در علوم رایانه مخصوصاً در نظریه زبان‌ها و ماشین‌ها، طرح حروف معین توسط و Madhusudan به عنوان تعمیم مشترکی از کلمه‌ها بیان شده‌است همان‌طور که به‌طور سنتی برای مدل‌سازی سازه‌های خطی و درختهای مرتب بدون درجه استفاده می‌شود که به‌طور سنتی برای مدل‌سازی ساختارهای سلسله مراتبی استفاده می‌شود. پذیرنده‌های حالت محدود برای حروف معین که ماشین حروف معین نامیده می‌شود که یک تعریف بیانگرانه‌تر از ماشین محدود را بر روی کلمات بیان می‌کند. کدگذاری خطی زبان‌های پذیرفته شده توسط ماشین حرف معین محدود یک کلاس از زبان‌های پشته‌ای عیان را ارائه می‌دهد. کلاس زبان دوم به‌طور صحیح بین زبان‌های منظم و زبان‌های مستقل از متن قطعی است. از زمان معرفی آنها در سال ۲۰۰۴ تحقیقات زیادی در این زمینه انجام داده‌اند.
برای تعریف کردن حروف معین، ابتدا باید رابطه‌های مربوط را تعریف کنیم. برای عددهای غیرمنفی 󠅟formula_1، formula_2 نشان دهنده مجموعه {۱٬۲,…, ι-۱, ι} می‌باشد، با مورد ویژه [۰] = ᶲ مطابق با رابطه ↝ از طول 󠅟formula_3 که یک زیرمجموعه از formula_4 می‌باشد از این رو:
موقعیت "i" به عنوان‌های زیر اشاره می‌کند:
حرف معین با طول formula_1 بالای حرف Σ یک جفت (w,↝) به طوری که w یک حرف یا رشته باشد با طول formula_1 در بالای Σ و ↝ یک رابطه مطابق با طول formula_1 می‌باشد.
حروف معین بر روی formula_8 می‌تواند به حروف متداول که بر روی حرف تگ شده formula_9 کدگذاری شود. هر علامت a از formula_10، ۳ همتا تگ شده دارد. علامت ⟨a برای کدگذاری یک موقعیت تماس در یک حرف معین با برچسب a، علامت a⟩ برای کدگذاری موقعیت برگشت که با برچسب a علامت گذاری شده و در نهایت علامت a خودش برای نشان دادن موقعیت درونی که با برچسب a علامت گذاری شده‌است. دقیق‌تر اگر" "یک تابع "φ" نقشه‌برداری حروف معین بر روی Σ تا formula_9 به طوری که هر حرف معین (↝,formula_12 بر روی کلمه formula_13 به طوری که حرف formula_14 معادل ⟨a و a و a⟩ و اگر formula_15 و "i" به ترتیب یک (ممکن هست در حال انتظار) موقعیت تماس، موقعیت داخلی، و یک (ممکن هست در حال انتظار) موقعیت بازگشتی باشد.
برای تصویرسازی، (↝,"n"=("w" یک حرف معین بر روی الفبای ۳ گانه با w=abaabccca و مطابق با رابطه ↝ = {(−∞,۱),(۲,∞),(۳٬۴),(۵٬۷),(۸,∞)} باشد سپس کدگذاری آن بر اساس حرف به‌طور
"φ"("n") = "a"⟩⟨"b"⟨"aa"⟩⟨"bcc"⟩⟨"ca" خوانده می‌شود.
ماشین حرف معین حالات محدودی از اعداد دارد و تقریباً همان‌طور که ماشین قطعی محدود روی رشته‌های کلاسیک هست عمل می‌کند. ماشین محدود کلاسیک ورودی formula_16 را از چپ به راست می‌خواند و حالت ماشین بعد از خواندن "j" امین حرف formula_17 بستگی به حالت ماشین قبل از خواندن formula_17 دارد.
در ماشین حرف معین، موقعیت "j" در حرف معین (w,↝) ممکن است موقعیت بازگشتی باشد. اگر چنین باشد، حالت بعد از خواندن formula_17 فقط به حالت خطی که در ماشین قبل از خواندن formula_17 هست وابسته نخواهد بود.
بلکه در یک حالت سلسله مراتبی که در زمان تماس متناظر آن توسط ماشین پخش شد وابسته خواهد بود.
در قیاس با زبان‌های منظم، مجموعه "L" از حروف معین منظم نامیده می‌شود اگر توسط چند حالت محدود ماشین حرف معین پذیرفته شود.
ماشین حرف معین مدل ماشینی می‌باشد که حرف‌های معین را می‌پذیرد. مدل معادلی وجود دارد که حروف متداول را کنترل می‌کند به‌طور مثال مفهوم ماشین قطعی پشته‌ای عیان محدودیتی برای مفهوم ماشین قطعی پشته‌ای می‌باشد.
به پیروی از Alur و Madhusudan ماشین پشته‌ای عیان توسط ۶-تاپل معرفی می‌شود formula_21 به طوری که:
نظریه محاسبات ماشین پشته‌ای عیان به‌طور قابل ملاحظه‌ای محدودیتی است که برای ماشین‌های پشته‌ای استفاده می‌شود. ماشین پشته‌ای عیان فقط وقتی که خواندن علامت تماس formula_30 باشد علامت را به پشته اضافه می‌کند. آنها فقط می‌توانند عنصر بالایی را از پشته وقتی که علامت بازگشتی formula_31 می‌باشد حذف کنند و نمی‌توانند پشته را وقتی رویداد داخلی formula_32 اتفاق میفتد تغییر دهند.
یک محاسبه که در حالت پذیرش پایان میابد یک محاسبه‌پذیر است.
در نتیجه یک ماشین پشته‌ای عیان نمی‌تواند با علامت یکسان از پشته هم push و هم pop کند.
بنابراین زبان formula_33 نمی‌تواند توسط ماشین پشته‌ای عیان برای هر قسمتی از formula_34 پذیرفته شود اگرچه ماشین پشته‌ای که این زبان را بپذیرد وجود دارد.
اگر زبان formula_35 در بالای الفبای formula_36 توسط ماشین قطعی پشته‌ای عیان پذیرفته شده باشد، سپس formula_37 زبان پشته‌ای عیان نامیده می‌شود.
ماشین غیرقطعی پشته‌ای عیان حاکی از آنهایی که قطعی هستند می‌باشد. از این رو می‌توان یک ماشین غیرقطعی پشته‌ای عیان را به قطعی تبدیل کرد. اما اگر ماشین غیرقطعی formula_38 حالت داشته باشد ماشین قطعی آن formula_39 داراست.
اگر formula_40 اندازه یک ماشین formula_41باشد، سپس می‌توان چک کرد که آیا حرف n توسط ماشین در زمان formula_42 پذیرفته‌است یا خیر. به‌طور خاص مسئله خالی در زمان formula_43 حل می‌شود. اگر formula_41 ثابت باشد در زمان formula_45 و فضای formula_46 که formula_47 عمق n در جریان دیده شده می‌باشد قابل حل می‌باشد. همین‌طور با فضای formula_48 و زمان formula_49 قابل حل است و به فرم مدار یکنواخت Boolean با عمق formula_50 .
برای دو ماشین غیرقطعی A و B تصمیم‌گیری در مورد اینکه آیا مجموعه‌ای از کلمات پذیرفته شده توسط A یک زیرمجموعه از حروفی است که توسط B پذیرفته شده EXPTIME-Complete هست یا خیر. همین‌طور -complete برای کشف کردن اینکه حرف پذیرفته نشده‌است نیز می‌باشد.
همان‌طور که تعریف ماشین پشته‌ای عیان نشان می‌دهد ماشین قطعی پشته‌ای عیان می‌تواند به عنوان یک مورد ویژه از ماشین قطعی پشته‌ای دیده شود؛ بنابراین مجموعه VPL از زبان‌های پشته‌ای عیان بر روی formula_51 زیرمجموعه‌ای را از مجموعه DCFL (زبان‌های قطعی مستقل از متن) بر روی مجموعه‌ای از علامت formula_51 تشکیل می‌دهد. به خصوص تابعی که مطابق با رابطه‌ای که از حروف معین که زبان‌های منظم را به زبان‌های مستقل از متن تبدیل می‌کند.
مجموعه‌ای از زبان‌های پشته‌ای عیان که بر اساس عملیات زیر هستند:
به این ترتیب به می‌رسیم.
برای عمل تقاطع می‌توان یک متغیر M از VPA (ماشین پشته‌ای عیان) شبیه‌سازی کنیم و ۲ VPA داده شده formula_53 و formula_54 با ساخت یک ضرب ساده (Alur & Madhusudan 2004): برای formula_55 فرض کنیم formula_56 داده شده باشد به صورت formula_57 سپس برای ماشین "M" مجموعه حالات formula_58 می‌باشد، حالت اولیه formula_59 و حالت‌های پایانی formula_60 می‌باشد و الفبای پشته توسط formula_61 داده شده‌است و علامت پشته اولیه formula_62می‌باشد.
اگر formula_63 در حالت formula_64 بر روی علامت خواندن تماس formula_65 باشد سپس formula_66 علامت formula_67را Push می‌کند و به حالت formula_68 می‌رود به طوری که formula_69 علامت پشته‌ای است که توسط formula_70، Push شده‌است از حالت formula_71 به formula_72 بر روی خواندن ورودی formula_65 می‌رود.
اگر formula_66 در حالت formula_64 بر روی خواندن علامت داخلی formula_76 باشد سپس formula_63 به حالت‌های formula_68 می‌رود وقتی که formula_70 از حالت formula_71 به formula_72 بر روی خواندن "a" انتقال یابد.
اگر formula_63 در حالت formula_64 بر روی خواندن نماد بازگشتی formula_84 باشد، سپس formula_63 نماد formula_86 را pop می‌کند از پشته و به حالت formula_68 می‌رود به طوری که formula_69 نماد پشته Pop شده توسط formula_56 وقتی که از حالت formula_71 به formula_72 انتقال میابد با خواندن formula_84 .
صحت ساختار فوق به شدت بر این واقعیت متکی است که عملیات‌های push و pop از ماشین‌های شبیه‌سازی شده formula_53 و formula_54 هماهنگ با نمادهای ورودی خوانده می‌شود. در واقع شبیه‌سازی مشابه برای ماشین قطعی پشته‌ای وجود ندارد به عنوان کلاس بزرگتر از زبان‌های مستقل از متن قطعی بر روی تقاطع بسته می‌شود.
در مقایسه با تلفیقی که در بالا نشان داده شده‌است، ساختار تکمیلی برای ماشین‌های پشته‌ای عیان با ساختار استاندارد ماشین‌های قطعی پشته‌ای همخوانی دارد.
علاوه بر این شبیه کلاس از زبان‌های مستقل از متن کلاس زبان‌های پشته‌ای عیان زیر بستن پیشوند و برعکس بسته می‌شود. از این رو بسته شدن پسوند نیز دارد.
Alur & Madhusudan (2004) اشاره کردند که زبان‌های پشته‌ای عیان عمومی‌تر از زبان‌های پرانتزی که توسط پیشنهاد شده‌است می‌باشد. همان‌طور که توسط نشان داده شده‌است VPL به نوبه خود به شدت در کلاس زبان‌های توصیف شده توسط گرامرهای عملگر اولویت که توسط معرفی شد و دارای خواص و مشخصات مشابه (دیده شده توسط Lonati et al. (2015) برای زبان‌های ω و منطق و خصوصیات مبتنی بر ماشین). در مقایسه با تعمیم دادن گرامرهای مستقل از متن نشان داد که همبستگی خطی زبان‌ها یک کلاس بزرگ از زبان‌های پشته‌ای عیان شکل می‌دهد. جدول آخر این مقاله گروهی از زبان‌های پشته‌ای عیان را در رابطه با گروه‌های دیگر زبان در وراثت چامسکی نشان می‌دهد. Rajeev Alur و Parthasarathy Madhusudan یک زیر کلاس از زبان‌های درختی باینری منظم تا زبان‌های پشته‌ای عیان را در برمیگیرد.
زبان‌های پشته‌ای دقیقاً زبان‌هایی هستند که می‌توانند توسط گرامرهای پشته‌ای عیان بیان شوند.
گرامرهای پشته‌ای عیان می‌توانند به عنوان محدودیتی از گرامرهای مستقل از متن تعریف شوند. گرامر پشته‌ای عیان formula_95 توسط ۴- formula_96به طوری که:
در اینجا ستاره بیانگر عملیات ستاره کلین و formula_121 حرف خالی است.
مشکل اینکه آیا یک کلمه با طول formula_1 که توسط ماشین حرف معین پذیرفته شده‌است می‌تواند توسط مدارات بولی یکنواخت با عمق formula_123 حل شود.
زبان‌های منظم بیش از کلمات ناسازگار دقیقاً مجموعه‌ای از زبان‌ها هستند که توسط بیان شده‌اند با دو پیش فرض غیرمعمول تماس و بازگشت جانشین خطی و رابطه تطبیقی ↝.