حروف معین

در علوم رایانه مخصوصاً در نظریه زبان‌ها و ماشین‌ها، طرح حروف معین توسط Alur و Madhusudan به عنوان تعمیم مشترکی از کلمه‌ها بیان شده‌است همان‌طور که به‌طور سنتی برای مدل‌سازی سازه‌های خطی و درختهای مرتب بدون درجه استفاده می‌شود که به‌طور سنتی برای مدل‌سازی ساختارهای سلسله مراتبی استفاده می‌شود. پذیرنده‌های حالت محدود برای حروف معین که ماشین حروف معین نامیده می‌شود که یک تعریف بیانگرانه‌تر از ماشین محدود را بر روی کلمات بیان می‌کند. کدگذاری خطی زبان‌های پذیرفته شده توسط ماشین حرف معین محدود یک کلاس از زبان‌های پشته‌ای عیان را ارائه می‌دهد. کلاس زبان دوم به‌طور صحیح بین زبان‌های منظم و زبان‌های مستقل از متن قطعی است. از زمان معرفی آنها در سال ۲۰۰۴ تحقیقات زیادی در این زمینه انجام داده‌اند.

تعریف رسمی

برای تعریف کردن حروف معین، ابتدا باید رابطه‌های مربوط را تعریف کنیم. برای عددهای غیرمنفی 󠅟${\displaystyle \ell }$، ${\displaystyle [\ell ]}$ نشان دهنده مجموعه {۱٬۲,…, ι-۱, ι} می‌باشد، با مورد ویژه [۰] = ᶲ مطابق با رابطه ↝ از طول 󠅟${\displaystyle \ell \geq 0}$ که یک زیرمجموعه از ${\displaystyle \{-\infty ,1,2,\ldots ,\ell -1,\ell \}\times \{1,2,\ldots ,\ell -1,\ell ,\infty \}}$ می‌باشد از این رو:

1. تمام لبه‌های این علامت‌ها رو ب جلو هستند، اگر i ↝ j آنگاه i <j .
2. به‌طور معمول این لبه‌ها محدود نیستند، برای ∞> i> ∞- حداقل یک موقعیت h وجود دارد که h ↝ i و حداقل یک موقعیت j که i ↝ j.
3. لبه‌های معین هیچوقت قطع نمی‌کنند، هیچ ' i <i ′ ≤ j <j وجود ندارد به طوری که هر دو i ↝ j و 'i ′ ↝ j.

موقعیت i به عنوان‌های زیر اشاره می‌کند:

• موقعیت تماس، اگر i ↝ j برای برخی j .
• تماس در انتظار اگر i ↝ ∞.
• موقعیت برگشت، اگر h ↝ i برای برخی h .
• موقعیت برگشت اگر ∞- ↝ i .
• موقعیت داخلی در همه موردهای باقیمانده.

حرف معین با طول ${\displaystyle \ell }$ بالای حرف الفبا Σ یک جفت (w,↝) به طوری که w یک حرف یا رشته باشد با طول ${\displaystyle \ell }$ در بالای Σ و ↝ یک رابطه مطابق با طول ${\displaystyle \ell }$ می‌باشد.

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

حروف معین بر روی ${\displaystyle \Sigma =\{a_{1},a_{2},\ldots ,a_{n}\}}$ می‌تواند به حروف متداول که بر روی حرف تگ شده ${\displaystyle {\widehat {\Sigma }}}$ کدگذاری شود. هر علامت a از ${\displaystyle \Sigma }$، ۳ همتا تگ شده دارد. علامت ⟨a برای کدگذاری یک موقعیت تماس در یک حرف معین با برچسب a، علامت a⟩ برای کدگذاری موقعیت برگشت که با برچسب a علامت گذاری شده و در نهایت علامت a خودش برای نشان دادن موقعیت درونی که با برچسب a علامت گذاری شده‌است. دقیق‌تر اگر یک تابع φ نقشه‌برداری حروف معین بر روی Σ تا ${\displaystyle {\widehat {\Sigma }}}$ به طوری که هر حرف معین (↝,${\displaystyle ({\displaystyle w_{1}w_{2}\cdots w_{\ell }}}$ بر روی کلمه ${\displaystyle x_{1}x_{2}...x_{\ell }}$ به طوری که حرف ${\displaystyle x_{i}}$ معادل ⟨a و a و a⟩ و اگر ${\displaystyle w_{i}=a}$ و i به ترتیب یک (ممکن هست در حال انتظار) موقعیت تماس، موقعیت داخلی، و یک (ممکن هست در حال انتظار) موقعیت بازگشتی باشد.

مثال

برای تصویرسازی، (↝,n=(w یک حرف معین بر روی الفبای ۳ گانه با w=abaabccca و مطابق با رابطه ↝ = {(−∞,۱),(۲,∞),(۳٬۴),(۵٬۷),(۸,∞)} باشد سپس کدگذاری آن بر اساس حرف به‌طور

φ(n) = a⟩⟨b⟨aa⟩⟨bcc⟩⟨ca خوانده می‌شود.

ماشین‌ها

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

ماشین حرف معین حالات محدودی از اعداد دارد و تقریباً همان‌طور که ماشین قطعی محدود روی رشته‌های کلاسیک هست عمل می‌کند. ماشین محدود کلاسیک ورودی ${\displaystyle w=w_{1}\cdots w_{\ell }}$ را از چپ به راست می‌خواند و حالت ماشین بعد از خواندن j امین حرف ${\displaystyle w_{j}}$ بستگی به حالت ماشین قبل از خواندن ${\displaystyle w_{j}}$ دارد.

در ماشین حرف معین، موقعیت j در حرف معین (w,↝) ممکن است موقعیت بازگشتی باشد. اگر چنین باشد، حالت بعد از خواندن ${\displaystyle w_{j}}$ فقط به حالت خطی که در ماشین قبل از خواندن ${\displaystyle w_{j}}$ هست وابسته نخواهد بود.

بلکه در یک حالت سلسله مراتبی که در زمان تماس متناظر آن توسط ماشین پخش شد وابسته خواهد بود.

در قیاس با زبان‌های منظم، مجموعه L از حروف معین منظم نامیده می‌شود اگر توسط چند حالت محدود ماشین حرف معین پذیرفته شود.

ماشین پشته‌ای عیان

ماشین حرف معین مدل ماشینی می‌باشد که حرف‌های معین را می‌پذیرد. مدل معادلی وجود دارد که حروف متداول را کنترل می‌کند به‌طور مثال مفهوم ماشین قطعی پشته‌ای عیان محدودیتی برای مفهوم ماشین قطعی پشته‌ای می‌باشد.

به پیروی از Alur و Madhusudan ماشین پشته‌ای عیان توسط ۶-تاپل معرفی می‌شود ${\displaystyle M=(Q,{\hat {\Sigma }},\Gamma ,\delta ,q_{0},F)}$ به طوری که:

• ${\displaystyle Q}$ مجموعه محدودی از حالات
• ${\displaystyle {\widehat {\Sigma }}}$ الفبا ورودی است به طوری که – در تضاد ماشین پشته‌ای متداول – در ۳ مجموعه، Σ_int Σ_c, Σ قسمت‌بندی میشه. الفبای Σ_c مجموعه علامت‌های تماس را نشان می‌دهد، Σ شامل علامت‌های بازگشتی است و مجموعه Σ_int شامل علامت‌های داخلی.
• ${\displaystyle \tau }$ مجموعه محدود که الفبای پشته نامیده می‌شود که شامل علامت ویژه می‌باشد که نشان دهنده پشته خالی است.
• ${\displaystyle {\displaystyle \delta }={\displaystyle \delta }_{c}\cup {\displaystyle \delta }_{\tau }\cup {\displaystyle \delta }_{int}}$ تابع انتقال است که به سه قسمت متناظر انتقال تماس ، انتقال بازگشتی و انتقال داخلی تقسیم‌بندی شده‌است.
• ${\displaystyle \delta _{c}:Q\times \Sigma _{c}\longrightarrow Q\times \tau }$ تابع انتقال تماس.
• ${\displaystyle \delta _{\text{int}}:Q\times \Sigma _{\text{int}}\to Q}$ تابع انتقال بازگشتی.
• ${\displaystyle q_{0}\in \,Q}$ تابع انتقال داخلی.
• ${\displaystyle F\subseteq Q}$ حالت اولیه می‌باشد.
• مجموعه‌ای از حالت‌های قابل پذیرش می‌باشد.

نظریه محاسبات ماشین پشته‌ای عیان به‌طور قابل ملاحظه‌ای محدودیتی است که برای ماشین‌های پشته‌ای استفاده می‌شود. ماشین پشته‌ای عیان فقط وقتی که خواندن علامت تماس ${\displaystyle {\displaystyle a_{\text{c}}\in \Sigma _{\text{c}}}}$ باشد علامت را به پشته اضافه می‌کند. آنها فقط می‌توانند عنصر بالایی را از پشته وقتی که علامت بازگشتی ${\displaystyle a_{\text{r}}\in \Sigma _{\text{r}}}$ می‌باشد حذف کنند و نمی‌توانند پشته را وقتی رویداد داخلی ${\displaystyle {\displaystyle a_{\text{i}}\in \Sigma _{\text{int}}}}$ اتفاق میفتد تغییر دهند.

یک محاسبه که در حالت پذیرش پایان میابد یک محاسبه‌پذیر است.

در نتیجه یک ماشین پشته‌ای عیان نمی‌تواند با علامت یکسان از پشته هم push و هم pop کند.

بنابراین زبان ${\displaystyle L=\{a^{n}ba^{n}\mid n\in {\mathrm {N} }\}}$ نمی‌تواند توسط ماشین پشته‌ای عیان برای هر قسمتی از ${\displaystyle \Sigma }$ پذیرفته شود اگرچه ماشین پشته‌ای که این زبان را بپذیرد وجود دارد.

اگر زبان ${\displaystyle {\displaystyle L}}$ در بالای الفبای ${\displaystyle {\displaystyle {\hat {\Sigma }}}}$ توسط ماشین قطعی پشته‌ای عیان پذیرفته شده باشد، سپس ${\displaystyle {\displaystyle L}}$ زبان پشته‌ای عیان نامیده می‌شود.

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

ماشین غیرقطعی پشته‌ای عیان حاکی از آنهایی که قطعی هستند می‌باشد. از این رو می‌توان یک ماشین غیرقطعی پشته‌ای عیان را به قطعی تبدیل کرد. اما اگر ماشین غیرقطعی ${\displaystyle s}$ حالت داشته باشد ماشین قطعی آن ${\displaystyle 2^{s^{2}}}$ داراست.

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

اگر ${\displaystyle |A|}$ اندازه یک ماشین ${\displaystyle {\displaystyle A}}$باشد، سپس می‌توان چک کرد که آیا حرف n توسط ماشین در زمان ${\displaystyle O(|A|^{3}\ell )}$ پذیرفته‌است یا خیر. به‌طور خاص مسئله خالی در زمان ${\displaystyle O(|A|^{3})}$ حل می‌شود. اگر ${\displaystyle {\displaystyle A}}$ ثابت باشد در زمان ${\displaystyle O(\ell )}$ و فضای ${\displaystyle O(d)}$ که ${\displaystyle d}$ عمق n در جریان دیده شده می‌باشد قابل حل می‌باشد. همین‌طور با فضای ${\displaystyle O(\log(\ell ))}$ و زمان ${\displaystyle O(\ell ^{2}\log(\ell ))}$ قابل حل است و به فرم مدار یکنواخت Boolean با عمق ${\displaystyle O(\log \ell )}$ .

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

زبان‌ها

همان‌طور که تعریف ماشین پشته‌ای عیان نشان می‌دهد ماشین قطعی پشته‌ای عیان می‌تواند به عنوان یک مورد ویژه از ماشین قطعی پشته‌ای دیده شود؛ بنابراین مجموعه VPL از زبان‌های پشته‌ای عیان بر روی ${\displaystyle \,{\hat {\Sigma }}}$ زیرمجموعه‌ای را از مجموعه DCFL (زبان‌های قطعی مستقل از متن) بر روی مجموعه‌ای از علامت ${\displaystyle \,{\hat {\Sigma }}}$ تشکیل می‌دهد. به خصوص تابعی که مطابق با رابطه‌ای که از حروف معین که زبان‌های منظم را به زبان‌های مستقل از متن تبدیل می‌کند.

خواص بسته‌شدن

مجموعه‌ای از زبان‌های پشته‌ای عیان که بر اساس عملیات زیر هستند:

• مجموعه عملیات‌ها:
• اجتماع
• تقاطع
• مکمل

به این ترتیب به جبر بولی می‌رسیم.

• ستاره کلین
• الحاق

برای عمل تقاطع می‌توان یک متغیر M از VPA (ماشین پشته‌ای عیان) شبیه‌سازی کنیم و ۲ VPA داده شده ${\displaystyle M_{1}}$ و ${\displaystyle M_{2}}$ با ساخت یک ضرب ساده (Alur & Madhusudan 2004): برای ${\displaystyle i=1,2}$ فرض کنیم ${\displaystyle M_{i}}$ داده شده باشد به صورت ${\displaystyle (Q_{i},\ {\hat {\Sigma }},\ \Gamma _{i},\ \delta _{i},\ s_{i},\ Z_{i},\ F_{i})}$ سپس برای ماشین M مجموعه حالات ${\displaystyle \,Q_{1}\times Q_{2}}$ می‌باشد، حالت اولیه ${\displaystyle \left(s_{1},s_{2}\right)}$ و حالت‌های پایانی ${\displaystyle F_{1}\times F_{2}}$ می‌باشد و الفبای پشته توسط ${\displaystyle \,\Gamma _{1}\times \Gamma _{2}}$ داده شده‌است و علامت پشته اولیه ${\displaystyle (Z_{1},Z_{2})}$می‌باشد.

اگر ${\displaystyle M}$ در حالت ${\displaystyle (p_{1},p_{2})}$ بر روی علامت خواندن تماس ${\displaystyle \left\langle a\right.}$ باشد سپس ${\displaystyle M}$ علامت ${\displaystyle (\gamma _{1},\gamma _{2})}$را Push می‌کند و به حالت ${\displaystyle (q_{1},q_{2})}$ می‌رود به طوری که ${\displaystyle \gamma _{i}}$ علامت پشته‌ای است که توسط ${\displaystyle M_{i}}$، Push شده‌است از حالت ${\displaystyle p_{i}}$ به ${\displaystyle q_{i}}$ بر روی خواندن ورودی ${\displaystyle \left\langle a\right.}$ می‌رود.

اگر ${\displaystyle M}$ در حالت ${\displaystyle (p_{1},p_{2})}$ بر روی خواندن علامت داخلی ${\displaystyle a}$ باشد سپس ${\displaystyle M}$ به حالت‌های ${\displaystyle (q_{1},q_{2})}$ می‌رود وقتی که ${\displaystyle M_{i}}$ از حالت ${\displaystyle p_{i}}$ به ${\displaystyle q_{i}}$ بر روی خواندن a انتقال یابد.

اگر ${\displaystyle M}$ در حالت ${\displaystyle (p_{1},p_{2})}$ بر روی خواندن نماد بازگشتی ${\displaystyle \left.a\right\rangle }$ باشد، سپس ${\displaystyle M}$ نماد ${\displaystyle (\gamma _{1},\gamma _{2})}$ را pop می‌کند از پشته و به حالت ${\displaystyle (q_{1},q_{2})}$ می‌رود به طوری که ${\displaystyle \gamma _{i}}$ نماد پشته Pop شده توسط ${\displaystyle M_{i}}$ وقتی که از حالت ${\displaystyle p_{i}}$ به ${\displaystyle q_{i}}$ انتقال میابد با خواندن ${\displaystyle \left.a\right\rangle }$ .

صحت ساختار فوق به شدت بر این واقعیت متکی است که عملیات‌های push و pop از ماشین‌های شبیه‌سازی شده ${\displaystyle M_{1}}$ و ${\displaystyle M_{2}}$ هماهنگ با نمادهای ورودی خوانده می‌شود. در واقع شبیه‌سازی مشابه برای ماشین قطعی پشته‌ای وجود ندارد به عنوان کلاس بزرگتر از زبان‌های مستقل از متن قطعی بر روی تقاطع بسته می‌شود.

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

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

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

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

توضیح مدل‌های دیگر

گرامرهای پشته‌ای عیان

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

گرامرهای پشته‌ای عیان می‌توانند به عنوان محدودیتی از گرامرهای مستقل از متن تعریف شوند. گرامر پشته‌ای عیان ${\displaystyle G}$ توسط ۴-تاپل ${\displaystyle G=(V=V^{0}\cup V^{1}\,,\Sigma \,,R\,,S\,)}$به طوری که:

• ${\displaystyle V^{0}\,}$و ${\displaystyle V^{1}\,}$ مجموعه‌های محدود جدا از هم می‌باشند هر عنصر ${\displaystyle v\in V}$ یک کاراکتر غیرترمینال یا متغیر می‌باشد. هر متغیر بیانگر نوع متفاوتی از عبارت یا جمله در جمله می‌باشد. هر متغیر یک زیر-زبان از زبان که توسط ${\displaystyle G}$ تعریف شده‌است و زیر-زبان ${\displaystyle V^{0}\,}$ بدون تماس‌های در حال انتظار و درحال انتظارهای بازگشتی می‌باشد.
• ${\displaystyle \Sigma \,}$ مجموعه محدودی از ترمینال‌ها که از ${\displaystyle V\,}$ جدا شده‌اند می‌باشد که محتوای واقعی حکم را تشکیل می‌دهند. مجموعه ترمینال‌ها الفبای زبان تعریف شده توسط گرامر ${\displaystyle G\,}$ می‌باشد.
• ${\displaystyle R\,}$ رابطه محدودی از ${\displaystyle V}$ تا ${\displaystyle (V\cup \Sigma )^{*}}$ که ${\displaystyle \exists \,w\in (V\cup \Sigma )^{*}:(S,w)\in R}$ . عضوهای ${\displaystyle R}$ محصول گرامر می‌باشند. ۳ نوع بازنویسی قوانین وجود دارد به صورت ${\displaystyle X,Y\in V,Z\in V^{0},{\displaystyle a\in {\hat {\Sigma }}}}$ و ${\displaystyle b\in {\hat {\Sigma }}}$ .
• ${\displaystyle X\to \epsilon }$
• ${\displaystyle X\to aY}$و اگر ${\displaystyle X\in V^{0}}$آنگاه ${\displaystyle Y\in V^{0}}$و ${\displaystyle a\in \Sigma }$
• ${\displaystyle X\to \langle aZb\rangle Y}$و اگر ${\displaystyle X\in V^{0}}$آنگاه ${\displaystyle Y\in V^{0}}$
• ${\displaystyle {\displaystyle S\in V\,}}$ متغیر شروع (یا نماد شروع) برای نشان دادن کل جمله (یا برنامه) بیان می‌شود.

در اینجا ستاره بیانگر عملیات ستاره کلین و ${\displaystyle \epsilon }$ حرف خالی است.

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

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

توضیح منطقی

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

منابع

• https://swt.informatik.uni-freiburg.de/teaching/SS2012/AutomataTheory/Resources/Slides/nestedwordautomata-seminarslides-christianschilling.pdf
• Floyd, R. W. (July 1963). "Syntactic Analysis and Operator Precedence". Journal of the ACM. 10 (3): 316–333. doi:10.1145/321172.321179.
• McNaughton, R. (1967). "Parenthesis Grammars". Journal of the ACM. 14 (3): 490. doi:10.1145/321406.321411.
• Alur, R.; Arenas, M.; Barcelo, P.; Etessami, K.; Immerman, N.; Libkin, L. (2008). Grädel, Erich, ed. "First-Order and Temporal Logics for Nested Words". Logical Methods in Computer Science. 4 (4). arXiv:0811.0537. doi:10.2168/LMCS-4(4:11)2008.
• Crespi Reghizzi, Stefano; Mandrioli, Dino (2012). "Operator precedence and the visibly pushdown property" (PDF). Journal of Computer and System Sciences. 78 (6): 1837–1867. doi:10.1016/j.jcss.2011.12.006. Archived from the original (PDF) on 9 August 2017. Retrieved 31 December 2017.
• Lonati, Violetta; Mandrioli, Dino; Panella, Federica; Pradella, Matteo (2015). "Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization". SIAM Journal on Computing. 44 (4). doi:10.1137/140978818.
• Okhotin, Alexander: Comparing linear conjunctive languages to subfamilies of the context-free languages, 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011).
• ویکی‌پدیای انگلیسی: Nested Word