حروف معین

کدگذاری حروف معین به حروف متداول

حروف معین بر روی  میتواند به حروف متداول که بر روی حرف تگ شده   کدگذاری شود . هر علامت a از ، 3 همتا تگ شده دارد . علامت ⟨a برای کدگذاری یک موقعیت تماس در یک حرف معین با برچسب a ، علامت  a⟩ برای کدگذاری موقعیت برگشت که با برچسب a علامت گذاری شده و در نهایت علامت a خودش برای نشان دادن موقعیت درونی که با برچسب a علامت گذاری شده است . دقیق‌تر اگر یک تابع φ نقشه‌برداری حروف معین بر روی Σ تا  به طوری که هر حرف معین (↝, بر روی کلمه  به طوری که حرف  معادل ⟨a و a و a⟩ و اگر  و i به ترتیب یک ( ممکن هست در حال انتظار) موقعیت تماس ، موقعیت داخلی ، و یک ( ممکن هست در حال انتظار ) موقعیت بازگشتی باشد.

مثال

برای تصویرسازی ، (↝,n=(w یک حرف معین بر روی الفبای ۳ گانه با w=abaabccca و مطابق با رابطه ↝ = {(−∞,1),(2,∞),(3,4),(5,7),(8,∞)} باشد سپس کدگذاری آن بر اساس حرف به طور
φ(n) = a⟩⟨b⟨aa⟩⟨bcc⟩⟨ca خوانده میشود.

ماشین حرف معین

ماشین حرف معین حالات محدودی از اعداد دارد و تقریباً همانطور که ماشین قطعی محدود روی رشته‌های کلاسیک هست عمل میکند . ماشین محدود کلاسیک ورودی  را از چپ به راست میخواند و حالت ماشین بعد از خواندن j امین حرف  بستگی به حالت ماشین قبل از خواندن  دارد.
در ماشین حرف معین ، موقعیت j در حرف معین (w,↝) ممکن است موقعیت بازگشتی باشد. اگر چنین باشد ، حالت بعد از خواندن  فقط به حالت خطی که در ماشین قبل از خواندن  هست وابسته نخواهد بود.
بلکه در یک حالت سلسله مراتبی که در زمان تماس متناظر آن توسط ماشین پخش شد وابسته خواهد بود.
در قیاس با زبان‌های منظم ، مجموعه L از حروف معین منظم نامیده میشود اگر توسط چند حالت محدود ماشین حرف معین پذیرفته شود.

ماشین غیرقطعی پشته‌ای عیان

ماشین غیرقطعی پشته‌ای عیان حاکی از آنهایی که قطعی هستند میباشد . از این رو میتوان یک ماشین غیرقطعی پشته‌ای عیان را به قطعی تبدیل کرد. اما اگر ماشین غیرقطعی  حالت داشته باشد ماشین قطعی آن  داراست.

مشکلات تصمیم‌گیری

اگر  اندازه یک ماشین باشد ، سپس میتوان چک کرد که آیا حرف n توسط ماشین در زمان  پذیرفته است یا خیر . به طور خاص مسئله خالی در زمان  حل میشود. اگر  ثابت باشد در زمان  و فضای  که  عمق n در جریان دیده شده میباشد قابل حل میباشد . همینطور با فضای  و زمان  قابل حل است و به فرم مدار یکنواخت Boolean با عمق  .
برای دو ماشین غیرقطعی A و B تصمیم گیری در مورد اینکه آیا مجموعه‌ای از کلمات پذیرفته شده توسط A یک زیرمجموعه از حروفی است که توسط B پذیرفته شده EXPTIME-Complete هست یا خیر . همینطور EXPTIME-complete برای کشف کردن اینکه حرف پذیرفته نشده است نیز میباشد.

زبان‌ها

همانطور که تعریف ماشین پشته‌ای عیان نشان میدهد ماشین قطعی پشته‌ای عیان میتواند به عنوان یک مورد ویژه از ماشین قطعی پشته‌ای دیده شود. بنابراین مجموعه VPL از زبان‌های پشته‌ای عیان بر روی  زیرمجموعه‌ای را از مجموعه DCFL (زبان‌های قطعی مستقل از متن) بر روی مجموعه‌ای از علامت  تشکیل میدهد. به خصوص تابعی که مطابق با رابطه‌ای که از حروف معین که زبان‌های منظم را به زبان‌های مستقل از متن تبدیل میکند.

رابطه با کلاس‌های دیگر زبان‌ها

Alur & Madhusudan (2004) اشاره کردند که زبان‌های پشته‌ای عیان عمومی‌تر از زبان‌های پرانتزی که توسط (McNaughton (1967 پیشنهاد شده است میباشد. همانطور که توسط  Crespi Reghizzi & Mandrioli (2012) نشان داده شده است VPL به نوبه خود به شدت در کلاس زبان‌های توصیف شده توسط گرامرهای عملگر اولویت که توسط (Floyd (1963 معرفی شد و دارای خواص و مشخصات مشابه ( دیده شده توسط  Lonati et al. (2015) برای زبان های ω  و منطق و خصوصیات مبتنی بر ماشین) . در مقایسه با گرامر همبستگی تعمیم دادن گرامرهای مستقل از متن (Okhotin (2011 نشان داد که همبستگی خطی زبان‌ها یک کلاس بزرگ از زبان‌های پشته‌ای عیان شکل میدهد. جدول آخر این مقاله گروهی از زبان‌های پشته‌ای عیان را در رابطه با گروه‌های دیگر زبان در وراثت چامسکی نشان میدهد. Rajeev Alur و Parthasarathy Madhusudan یک زیر کلاس از زبان‌های درختی باینری منظم تا زبان‌های پشته‌ای عیان را در برمیگیرد.

مدارات بولی یکنواخت

مشکل اینکه آیا یک کلمه با طول  که توسط ماشین حرف معین پذیرفته شده است میتواند توسط مدارات بولی یکنواخت با عمق  حل شود.

توضیح منطقی

زبان‌های منظم بیش از کلمات ناسازگار دقیقاً مجموعه‌ای از زبان‌ها هستند که توسط Monadic second-order logicبیان شده‌اند با دو پیش فرض غیرمعمول تماس و بازگشت جانشین خطی و رابطه تطبیقی  ↝ .