موضوع مقاله: حروف معین | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # حروف معین | مقدمه: در علوم رایانه مخصوصاً در نظریه زبان‌ها و ماشین‌ها، طرح حروف معین توسط Alur و Madhusudan به عنوان تعمیم مشترکی از کلمه‌ها بیان شده‌است همان‌طور که به‌طور سنتی برای مدل‌سازی سازه‌های خطی و درختهای مرتب بدون درجه استفاده می‌شود که به‌طور سنتی برای مدل‌سازی ساختارهای سلسله مراتبی استفاده می‌شود. | ## بخش 1: حروف معین | پذیرنده‌های حالت محدود برای حروف معین که ماشین حروف معین نامیده می‌شود که یک تعریف بیانگرانه‌تر از ماشین محدود را بر روی کلمات بیان می‌کند. کدگذاری خطی زبان‌های پذیرفته شده توسط ماشین حرف معین محدود یک کلاس از زبان‌های پشته‌ای عیان را ارائه می‌دهد. برای عددهای غیرمنفی 󠅟، نشان دهنده مجموعه {۱٬۲,…, ι-۱, ι} می‌باشد، با مورد ویژه [۰] = ᶲ مطابق با رابطه ↝ از طول 󠅟 که یک زیرمجموعه از می‌باشد از این رو: تمام لبه‌های این علامت‌ها رو ب جلو هستند، اگر i ↝ j آنگاه i <j . به‌طور معمول این لبه‌ها محدود نیستند، برای ∞> i> ∞- حداقل یک موقعیت h وجود دارد که h ↝ i و حداقل یک موقعیت j که i ↝ j. حرف معین با طول بالای حرف الفبا Σ یک جفت (w,↝) به طوری که w یک حرف یا رشته باشد با طول در بالای Σ و ↝ یک رابطه مطابق با طول می‌باشد. کدگذاری حروف معین به حروف متداول حروف معین بر روی می‌تواند به حروف متداول که بر روی حرف تگ شده کدگذاری شود. علامت ⟨a برای کدگذاری یک موقعیت تماس در یک حرف معین با برچسب a، علامت a⟩ برای کدگذاری موقعیت برگشت که با برچسب a علامت گذاری شده و در نهایت علامت a خودش برای نشان دادن موقعیت درونی که با برچسب a علامت گذاری شده‌است. دقیق‌تر اگر یک تابع φ نقشه‌برداری حروف معین بر روی Σ تا به طوری که هر حرف معین (↝, بر روی کلمه به طوری که حرف معادل ⟨a و a و a⟩ و اگر و i به ترتیب یک (ممکن هست در حال انتظار) موقعیت تماس، موقعیت داخلی، و یک (ممکن هست در حال انتظار) موقعیت بازگشتی باشد. ماشین‌ها ماشین حرف معین ماشین حرف معین حالات محدودی از اعداد دارد و تقریباً همان‌طور که ماشین قطعی محدود روی رشته‌های کلاسیک هست عمل می‌کند. ماشین محدود کلاسیک ورودی را از چپ به راست می‌خواند و حالت ماشین بعد از خواندن j امین حرف بستگی به حالت ماشین قبل از خواندن دارد. اگر چنین باشد، حالت بعد از خواندن فقط به حالت خطی که در ماشین قبل از خواندن هست وابسته نخواهد بود. بلکه در یک حالت سلسله مراتبی که در زمان تماس متناظر آن توسط ماشین پخش شد وابسته خواهد بود. در قیاس با زبان‌های منظم، مجموعه L از حروف معین منظم نامیده می‌شود اگر توسط چند حالت محدود ماشین حرف معین پذیرفته شود. ماشین پشته‌ای عیان ماشین حرف معین مدل ماشینی می‌باشد که حرف‌های معین را می‌پذیرد. مدل معادلی وجود دارد که حروف متداول را کنترل می‌کند به‌طور مثال مفهوم ماشین قطعی پشته‌ای عیان محدودیتی برای مفهوم ماشین قطعی پشته‌ای می‌باشد. | ## بخش 2: حروف معین | الفبای Σc مجموعه علامت‌های تماس را نشان می‌دهد، Σ شامل علامت‌های بازگشتی است و مجموعه Σint شامل علامت‌های داخلی. مجموعه محدود که الفبای پشته نامیده می‌شود که شامل علامت ویژه می‌باشد که نشان دهنده پشته خالی است. تابع انتقال است که به سه قسمت متناظر انتقال تماس ، انتقال بازگشتی و انتقال داخلی تقسیم‌بندی شده‌است. نظریه محاسبات ماشین پشته‌ای عیان به‌طور قابل ملاحظه‌ای محدودیتی است که برای ماشین‌های پشته‌ای استفاده می‌شود. ماشین پشته‌ای عیان فقط وقتی که خواندن علامت تماس باشد علامت را به پشته اضافه می‌کند. آنها فقط می‌توانند عنصر بالایی را از پشته وقتی که علامت بازگشتی می‌باشد حذف کنند و نمی‌توانند پشته را وقتی رویداد داخلی اتفاق میفتد تغییر دهند. بنابراین زبان نمی‌تواند توسط ماشین پشته‌ای عیان برای هر قسمتی از پذیرفته شود اگرچه ماشین پشته‌ای که این زبان را بپذیرد وجود دارد. اگر زبان در بالای الفبای توسط ماشین قطعی پشته‌ای عیان پذیرفته شده باشد، سپس زبان پشته‌ای عیان نامیده می‌شود. ماشین غیرقطعی پشته‌ای عیان ماشین غیرقطعی پشته‌ای عیان حاکی از آنهایی که قطعی هستند می‌باشد. مشکلات تصمیم‌گیری اگر اندازه یک ماشین باشد، سپس می‌توان چک کرد که آیا حرف n توسط ماشین در زمان پذیرفته‌است یا خیر. اگر ثابت باشد در زمان و فضای که عمق n در جریان دیده شده می‌باشد قابل حل می‌باشد. زبان‌ها همان‌طور که تعریف ماشین پشته‌ای عیان نشان می‌دهد ماشین قطعی پشته‌ای عیان می‌تواند به عنوان یک مورد ویژه از ماشین قطعی پشته‌ای دیده شود؛ بنابراین مجموعه VPL از زبان‌های پشته‌ای عیان بر روی زیرمجموعه‌ای را از مجموعه DCFL''' (زبان‌های قطعی مستقل از متن) بر روی مجموعه‌ای از علامت تشکیل می‌دهد. به خصوص تابعی که مطابق با رابطه‌ای که از حروف معین که زبان‌های منظم را به زبان‌های مستقل از متن تبدیل می‌کند. خواص بسته‌شدن مجموعه‌ای از زبان‌های پشته‌ای عیان که بر اساس عملیات زیر هستند: مجموعه عملیات‌ها: اجتماع تقاطع مکمل به این ترتیب به جبر بولی می‌رسیم. ستاره کلین الحاق برای عمل تقاطع می‌توان یک متغیر M از VPA (ماشین پشته‌ای عیان) شبیه‌سازی کنیم و ۲ VPA داده شده و با ساخت یک ضرب ساده (Alur & Madhusudan 2004): برای فرض کنیم داده شده باشد به صورت سپس برای ماشین M مجموعه حالات می‌باشد، حالت اولیه و حالت‌های پایانی می‌باشد و الفبای پشته توسط داده شده‌است و علامت پشته اولیه می‌باشد. | ## بخش 3: حروف معین | اگر در حالت بر روی علامت خواندن تماس باشد سپس علامت را Push می‌کند و به حالت می‌رود به طوری که علامت پشته‌ای است که توسط ، Push شده‌است از حالت به بر روی خواندن ورودی می‌رود. اگر در حالت بر روی خواندن علامت داخلی باشد سپس به حالت‌های می‌رود وقتی که از حالت به بر روی خواندن a انتقال یابد. اگر در حالت بر روی خواندن نماد بازگشتی باشد، سپس نماد را pop می‌کند از پشته و به حالت می‌رود به طوری که نماد پشته Pop شده توسط وقتی که از حالت به انتقال میابد با خواندن . صحت ساختار فوق به شدت بر این واقعیت متکی است که عملیات‌های push و pop از ماشین‌های شبیه‌سازی شده و هماهنگ با نمادهای ورودی خوانده می‌شود. در واقع شبیه‌سازی مشابه برای ماشین قطعی پشته‌ای وجود ندارد به عنوان کلاس بزرگتر از زبان‌های مستقل از متن قطعی بر روی تقاطع بسته می‌شود. در مقایسه با تلفیقی که در بالا نشان داده شده‌است، ساختار تکمیلی برای ماشین‌های پشته‌ای عیان با ساختار استاندارد ماشین‌های قطعی پشته‌ای همخوانی دارد. علاوه بر این شبیه کلاس از زبان‌های مستقل از متن کلاس زبان‌های پشته‌ای عیان زیر بستن پیشوند و برعکس بسته می‌شود. در مقایسه با گرامر همبستگی تعمیم دادن گرامرهای مستقل از متن (Okhotin (2011 نشان داد که همبستگی خطی زبان‌ها یک کلاس بزرگ از زبان‌های پشته‌ای عیان شکل می‌دهد. جدول آخر این مقاله گروهی از زبان‌های پشته‌ای عیان را در رابطه با گروه‌های دیگر زبان در وراثت چامسکی نشان می‌دهد. توضیح مدل‌های دیگر گرامرهای پشته‌ای عیان زبان‌های پشته‌ای دقیقاً زبان‌هایی هستند که می‌توانند توسط گرامرهای پشته‌ای عیان بیان شوند. گرامرهای پشته‌ای عیان می‌توانند به عنوان محدودیتی از گرامرهای مستقل از متن تعریف شوند. گرامر پشته‌ای عیان توسط ۴-تاپل به طوری که: و ''مجموعه‌های محدود جدا از هم می‌باشند هر عنصر یک کاراکتر غیرترمینال یا متغیر می‌باشد. هر متغیر یک زیر-زبان از زبان که توسط تعریف شده‌است و زیر-زبان بدون تماس‌های در حال انتظار و درحال انتظارهای بازگشتی می‌باشد. مجموعه محدودی از ترمینال‌ها که از جدا شده‌اند می‌باشد که محتوای واقعی حکم را تشکیل می‌دهند. و اگر آنگاه و و اگر آنگاه متغیر شروع (یا نماد شروع) برای نشان دادن کل جمله (یا برنامه) بیان می‌شود. | ## جمع‌بندی | مدارات بولی یکنواخت مشکل اینکه آیا یک کلمه با طول که توسط ماشین حرف معین پذیرفته شده‌است می‌تواند توسط مدارات بولی یکنواخت با عمق حل شود.