زبان منظم

1396/1/12 محمدرضا احمدآبادی 2191

سلام حالتون چطوره؟ محمدرضا احمدآبادی هستم با جلسه نوزدهم آموزش نظریه زبان ها در خدمتتون هستم . امروز در مورد ماشین ها با هم صحبت نخواهیم کرد . پس درباره چی میخواهیم صحبت کنیم؟ اگه یادتون باشه از جلسه سوم به بعد آموزش ها من از یه لغت گاها استفاده میکردم . اون هم زبان منظم بود اما تعریف نمیکردم و میگفتم در آینده براتون تعریف خواهم کرد . اون آینده ای که درباره اش صحبت میکردم امروز هست.  پس با من همراه باشید تا ببینیم این زبان منظم چی هست ؟ و چه ویژگی هایی داره؟

یک زبان منظم خواهد بود اگر و تنها اگر برای رشته های آن بتوان یک ماشین متناهی(DFA یا NFA )یا یک گرامر منظم و یا یک عبارت منظم ارائه داد .
در مورد زبان های منظم بهتره سه نکته زیر را همیشه به خاطر داشته باشید:

1-  هر زبان متناهی منظم خواهد بود.
برای این که بهتر براتون توضیح بدم باید بگم اگه برای یه زبان متناهی توانستید ماشین متناهی یا گرامر منظم و یا عبارت منظم بنویسید که هیچ ، مشکل حل هست . اما بعضی مواقع نمیتوانید برای زبانی که بهتون داده شده هیچ کدام از موارد بالا را رسم کنید اما زبانی هم که بهتون داده شده متناهی هست در این مواقع اکثرا همه فکر میکنند چون نمیتونند برای زبان این موارد را رسم کنند فوری اعلام میکنند زبان مورد نظر منظم نیست .  که کاملا اشتباه میکنند. چرا؟
 دلیلش این هست که ما داریم زبان میخونیم تا بتونیم یه دسته رشته را نشون بدیم یعنی ما داریم با زبان شکل و شمایل رشته های هدف این زبان را نشان میدهیم.  حالا به ما یه زبان دادن که خیلی چغر و بد بدن هست و ما نمیتونیم شکل علائم اختصاری زبان را براشون بنویسیم اما این دلیل نمیشه که زبان منظم نباشه.
در این مواقع اگر شما نمیتوانید زبان را بنویسید مشکلی نیست ، چون زبان محدود هست میتوانید رشته های هدف این زبان را کامل بنویسید . این نوشتن رشته ها عملا داره زبان را معرفی میکنه.

2-  اگر در یک زبان حداقل دوتا از سمبل های الفبا از نظر تعداد به هم وابسته باشند و این تعداد مقدار نامحدودی باشد ، آن زبان منظم نخواهد بود.
مثال) منظم بودن یا نبودن زبان های زیر را بررسی کنید.

L={an bm c2n|n,m>=0}


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

اگر دقت کرده باشید من از اصطلاح منظم نیست استفاده کرده ام و نمیگویم نامنظم. چون رشته های یه زبان حتما یه ترتیبی بینشون هست که باعث نظم و ترتیب بینشون خواهد شد اما زبان منظم زبانی هست که ما در بالا تعریف کردیم پس درست نیست برای حالت مخالف عبارت نامنظم به کار ببریم. از حالا تمرین کنید و بگویید منظم نیست.

L={w ԑ{a,b}* | na(w)=nb(w)}


این زبان هم مشابه زبان قبلی به دلیل وابسته بودن سمبل a وb به یکدیگر منظم نیست.

آموزش نظریه زبان ها و ماشین ها

نظرتون در مورد این زبان چی هست؟ شاید دارید باخودتون فکر میکنید که چون سمبل a وb به همدیگه وابسته هست پس این زبان منظم نیست.
اما نظر من با شما فرق داره . این زبان در بند 1 نکات گیر میکنه و از اونجا بیرون نمیاد . چون این زبان یه زبان محدود هست ( درسته تعداد حالاتش خیلی زیاده به خاطر اون عدد بزرگ، اما در انتها متناهی هست و میشه یه جورایی رشته های این زبانو بدست آورد) پس این زبان منظم است.
اما چرا بند 2 جواب نمیدهد: در تعریف بند دو زبان باید دوتا شرط داشته باشه یکی این که حداقل دوتا از سمبل هاش به همدیگه وابسته باشند و دوم اینکه نامتناهی باشد  . این زبان متناهی نبود  پس اصلا نباید بر اساس بند دو تعیین تکلیف بشود.

3-  اگر در یک زبان تعداد یک سمبل الفبایی مقدار خاصی باشد (مانند فاکتوریل، عدد اول ، مربع کامل ، توانی از 2 و ...) به شکلی که این اعداد همگی مضرب یک عدد مشخصی نباشند  یا اگر مضرب آن عدد هستند اعداد دیگری هم که این ویژگی را ندارند مضرب آن عدد باشند و این مقدار نا محدود باشد آن زبان منظم نخواهد بود.
مثال) زبان های زیر به دلیل بند 3 منظم نیستند.

 

L={an|یک عدد اول استn}
L={an|n==m!}

ویژگی های زبان های منظم:
اگر L1و L2 دو زبان منظم باشند ، آنگاه L1∩L2  و L1ᴜL2 و L1-L2 و L1.L2 و L1* منظم اند.
به عبارت دیگر زبان های منظم نسبت به عملگرهای اجتماع ، اشتراک ، الحاق، تفاضل ، متمم، بستار و معکوس بسته هستند.

یه سوال ازتون میپرسم تا جلسه آینده بهش فکرکنید .
تمرین ) اگر L1 و L1ᴜL2 دو زبان منظم باشند ، آیا همواره میتوان گفت زبان L2 نیز منظم است؟

خواص الگوریتمیک زبان های منظم:
1)  اگر L یک زبان منظم روی الفبای ∑  و W رشته ای از  ∑* باشد، الگوریتمی وجود دارد که بررسی میکند wԑL هست یا نه.
2)  اگر L یک زبان منظم روی الفبای ∑ باشد، الگوریتمی وجود دارد که بررسی میکند L متناهی است یا نه.
3)  اگر L یک زبان منظم روی الفبای ∑ باشد، الگوریتمی وجود دارد که بررسی میکند  L=ф هست یا نه.
4)  اگر L یک زبان منظم روی الفبای ∑ باشد، الگوریتمی وجود داردکه بررسی میکند L ԑ λ هست یا نه.
5)  اگر L یک زبان منظم روی الفبای ∑ باشد، الگوریتمی وجود دارد که بررسی میکند  L=∑* هست یا نه.
6)  اگر L1,L2 دو زبان منظم روی الفبای ∑ باشد، الگوریتمی داریم که بررسی میکند L1زیرمجموعه L2 هست یا نه.

خلاصه برای هر عمل زبان های منظم یک الگوریتم وجود دارد.

خب به پایان این جلسه ام رسیدیم . امیدوارم تا الان خسته نباشید وحوصله شما سر نرفته باشه.

شادوموفق و سربلند باشید.
تا جلسه بعد خدانگهدار.

دانلود PDF قسمت نوزدهم آموزش نظریه زبان ها و ماشین ها

کلمات کلیدی

محمدرضا احندآبادی
مهندس نرم افزار
کارشناسی مهندسی نرم افزار
مدرس دوره نظریه زبان ها و ماشین ها