عبارات منظم

عبارات منظم در واقع یک زبان برای نشان‌دادن هر چه بهتر رشته‌های واژگانی‌اند. اوّلین بار به‌سال 1956 کلين¹ عبارات منظم را ابداع نمود و تاکنون کاربران زیادی در امور مختلف از عبارات منظم استفاده می‌کنند. برای هر عبارت منظم باید یک الگو²  و یک محتوای متنی³  داشته باشیم.

در زبان عبارات منظم تعدادی علامت خاص به نام لنگر⁴ است که نشان‌دهنده خواصی در یک الگوی رشته‌ای است. به عنوان مثال، علامت \b یک لنگر است که نشان‌دهنده پایان یک محدوده واژگانی‌ست. در عبارات منظم عملگرها دارای اولویت‌های مخصوص به خود هستند.

اولویت اول: کمانک ()

اولویت دوم: شمارنده‌ها *؟+{}

اولویت سوم: تواترها و سپرها مثل \b و $

اولویت چهارم: علایم فصل |

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

آتاماتای حالت متناهی

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

یک آتاماتون حالت متناهی در کل با پنج مولفه صوری تعریف می‌شود:

Q: مجموعه‌ای از حالت‌های متناهی در ماشین.

∑: مجموعه‌ای از حالات محدود در ورودی.

q₀: حالت اوّلیه ماشین.

F : مجموعه‌ای از حالت نهایی که زیرمجموعه Q است.

تابع گذر سیگمای q و i.

زبان‌های صوری

زبان‌های صوری هم برای تولید رده خاصی از رشته‌ها یا یک زبان و نیز برای تشخیص پذیرفتن رشته‌ای در یک زبان به کار می‌رود. زبان‌های صوری از تعدادی محدود از علائم تشکیل می‌شوند که به این علائم الفبا می‌گویند. البته زبان‌های صوری تفاوت‌های بسیاری با زبان‌های طبیعی دارند ولی برای پیاده‌سازی و الگو قرار دادن قسمتی از زبان‌های طبیعی بسیار به کار می‌روند. دستور زبان مولد⁵ در واقع نشان‌دهنده دستور زبان یک زبان صوری است. ریشه اصلی این واژه از آتاماتونی‌ست که برای تعریف زبانی که همه رشته‌های موجود در آن زبان را تولید می‌نماید؛ گرفته شده است.

نوع دیگری از آتاماتای حالت متناهی وجود دارد که به آن آتاماتای حالت متناهی غیرقطعی⁶ گویند که در هر حالت به ازای یک ورودی ماشین ممکن است به چند حالت مختلف برود و یا به هیچ حالتی نرود و یا از طرفی دیگر بدون تغییر در ورودی یا بدون توجه به ورودی ماشین از حالتی به  حالت دیگری برود.

برای جست‌و‌جو در یک ماشین حالت متناهی غیرقطعی می‌شود از روش‌های موازی استفاده کرد. به همین منظور الگوریتم‌های جستجوی عمقی یا جستجوی سطحی و ساختمان داده‌ای پشته یا صف به عنوان حافظه کمکی برای این کار بسیار مناسب است. برای مسایل مشکل‌تر می‌توان از الگوریتم‌های برنامه‌سازی پویا و A^* استفاده نمود. البته برای هر ماشین حالت متناهی غیرقطعی، می‌توان ماشین قطعی معادلش را با الگوریتم‌های بسیار ساده‌اش به دست آورد.

زبان‌های منظم و ماشین‌های حالت متناهی

زبان‌های منظم را می‌توان با استفاده از FSAها پیاده‌سازی کرد و هر زبانی که در یک FSA پیاده می‌شود، لاجرم یک زبان منظم است.

تعریف زبان منظم به این صورت است که به ازای یک الفبای ∑، به ازای هر حرف a که عضوی از آن است؛ {a} یک زبان منظم است و نیز الحاق، اشتراک و نیز بسط کلین یا ستاره‌ای⁷ آن نیز یک زبان منظم خواهد بود. زبان‌های منظم در ضمن نسبت به اشتراک، تفاضل، معکوس خود و نیز متمم‌گیری بسته‌اند.

پی‌نوشت:

*مطالب فوق از فصل دوم کتاب پردازش زبان‌ها و مکالمات طبیعی نوشتۀ مارتین و جورافسکی است.

*برای یافتن جزئیات بیشتری در مورد زبان‌ها و عبارات منظم و ماشین‌های حالت متناهی می‌توانید به کتاب‌های نظریه زبان‌ها و ماشین‌ها از جمله کتابی با هین نام نوشته لینز مراجعه کنید. در ضمن کتاب لینز را آقای دکتر صراف‌زاده به فارسی ترجمه کرده‌اند.

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

1.        Kleene

2.        Pattern

3.        corpus

4.        anchor

5.        generative grammar

6.        NFSA (Nondeterministic FSA)

7.        Kleene(star) closure