روش های به دست آوردن عبارت منظم یک ماشین

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

سلام  خدمت همه شما همراهان همیشگی . امروز میخوام  براتون نحوه تبدیل ماشین متناهی به عبارت منظم را بگویم

برای بدست آوردن عبارت منظم یک ماشین متناهی ( DFA یا NFA ) میتوان از یکی از دو روش زیر استفاده کرد.

1-  استفاده از گراف انتقال عمومی(GTG):
یک گراف انتقال عمومی دقیقا مانند یک ماشین متناهی خواهد بود با این تفاوت که بر روی یال های آن میتواند عبارت منظم قرار بگیرد. یک گراف انتقال عمومی کامل نوعی گراف است که در آن از هر راس به راس دیگر ( حتی خود آن راس) یک یال مستقیم وجود دارد .
برای تبدیل یک DFA به عبارت منظم ابتدا ماشین را به یک گراف انتقال عمومی کامل تبدیل میکنیم . در این تبدیل تنها کافی است از هر راس به راس دیگر که یال مستقیم ندارد ، یک یال با برچسب تهی اضافه کنیم . سپس گراف کامل انتقال را تا رسیدن به یک گراف انتقال عمومی دو حالته ( یک حالت شروع و یک حالت پایان )  کاهش حالت میدهیم . روند کاهش حالت باید به گونه ای باشد که در هر مرحله یک حالت از این گراف کاسته شود.
نکته دیگر این که این روند باید به گونه ای انجام شود که در انتها گراف عمومی دو حالته حتما دارای یک حالت شروع و یک حالت پایانی باشد .
هر گاه میخواهیم یک حالت را کاهش دهیم باید تمامی انتقال های بین حالت های دیگر را با عبور از این حالت کاسته شده نیز در نظر بگیریم  و عبارت منظم لازم را اضافه کنیم . در پایان اگر به گراف انتقال عمومی  دو حالته مانند زیر رسیدیم  عبارت منظم آن به شکلی که گفته میشود به دست می آید.

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

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

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

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

قدم اول برای حل این سوال این هست که من این ماشین را تبدیل کنم به گراف کامل عمومی کامل. ( گراف کامل عمومی میگفت باید از هر راس به تمام رئوس( حتی خود همان راس) یک یال باید وجود داشته باشد) . خب پس من باید یه سری یال به این ماشین اضافه کنم تا تبدیل به گراف کامل عمو می بشه . مثلا از حالت شروع به حالت پایانی یال مستقیم نیست پس من باید یک یال از حالت شروع به حالت پایانی رسم کنم و سمبل روی یال را تهی بنویسم . چون در روش هم گفته شد که اگر یالی موجود نبود آن را اضافه کرده و وزن آن را تهی  مینویسیم . بقیه حالت ها هم باید برسی شده و اگر یال مستقیمی بین دو حالت نبود آنرا باید اضافه کنیم. پس گراف کامل من خواهد شد :

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

حالا من باید برم سراغ کاهش حالت . برای این که من بخوام کاهش حالت انجام بدم باید یک حالت را انتخاب کنم و اونو کاهش بدم . مسلما حالت شروع و حالت پایان را نباید کاهش بدم چون باید این دو حالت را حفظ کنم تا بتونم طبق الگو عبارت منظم را بنویسم پس باید حالت B را کاهش بدم . وقتی حالت B را کاهش دادم باید انتقال هایی که به B بود را در نظر بگیرم  چون مثلا حالت A با 0 به B انتقال داشت اما وقتی این حالت B را حذف کنم این انتقال هم از بین خواهد رفت که نباید این طور بشه . برای این کار اولا از این به بعد به صورت عبارت منظم روی گراف عبارت ها را خواهیم نوشت. بزارید چندتا مثال از خود همین شکل براتون بگم تا قشنگ مطلب براتون جا بیوفته.
من حالت B را کاهش دادم اما از حالت A به حالت B چند انتقال داشتم یعنی یک مسیر وجود داشت.  
من از حالت A با سمبل 0 به حالت B میروم و در اونجا یه تعداد( نامشخص تهی (ф* ) )  میبینم بعد با سمبل 1 دو باره به حالت A بر میگردم.
این یه خط داستانی که گفتمو بهش توجه کنید. برای همین یه خط  عبارت منظمش میشود :

0 ф*1


این عبارت منظم باید در کنار عبارت منظم ( همون سمبل 1 ) حالت A نوشته بشه. پس تا اینجا حالت A خواهد شد:

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

از طرفی حالت A با حالت C از دو حالت ارتباط داشت یکی به صورت مستقیم با تهی و دیگری به واسطه حالت B .پس باید عبارت منظم ارتباط حالت A با حالت C به واسطه B را در کنار حالت مسقیم اضافه کنیم.  دوباره یه داستان یک خطی دیگه باید بگیم و عبارتشو بنویسیم:
من از حالت A با سمبل 0 به حالت B میروم و دراونجا با دیدن یه تعداد  ф  تاب میخورم (  ф*  ) و با دیدن سمبل 0 به حالت C میروم.
عبارت منظم این داستان خواهد شد:

0 ф*0


که این هم در کنار یال مستقیم نوشته خواهد شد.

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

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

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

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

(0+1)+ фф*0


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

Ф* = λ


بعد ما یه قانون داشتیم که میگفت : 

ф.r=ф


 پس با توجه به این قانون حاصل عبارت زیر این چنین خواهد شد:

Ф0=ф


و دوباره اگه از این قانون استفاده کنیم حاصل   ф.λ=ф خواهد شد.
تا این جا میرسیم به :

(0+1)+ ф


با تو جه به قاعده  r+ф=r  حاصل عبارت بالا خواهد شد:

(0+1)


برای مابقی حالت ها هم به همین روش عمل میکنیم  تا حاصل هر مرحله به دست آید . گراف  نهایی ما خواهد شد:

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

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

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

پس عبارت منظم ما با توجه به این الگو خواهد شد:
 

(1+01)*00[(0+1)+ ф(1+01)*00]* =(1+01)*00(0+1)*

2-  استفاده از معادلات حالت:
در این روش ابتدا معادله حالت هر  حالت از ماشین را با توجه به انتقال های خروجی از آن حالت مینویسیم. سپس هر معادله حالت به فرم  X=pX+q  را به معادله ی حالت  X=p*q  تبدیل میکنیم. در نهایت با جایگذاری های مختلف  باید به جایی برسیم که معادله حالت متناظر با حالت شروع  فاقد هرگونه نام حالتی باشد. این عبارت همان عبارت منظم ماشین است.

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

برای نوشتن معادلات حالت ماشین  هرتابع انتقال  به فرم  (qi,a)=qj به معادله  حالت  qi=aqj تبدیل میشود.
همچنین هر حالتی که به عنوان یک حالت پایانی مطرح شود یک عبارت λ  به صورت اجتماع به معادله حالتش اضافه میشود.
حالا بریم معادله حالت هر حالتو بنویسیم با استفاده از انتقال های خروجی اون حالت.

A=1A+0B
B=0C+1A


برای حالت C مثل A,B عمل میکنیم اما چون این حالت یک خروجی هم محسوب میشود پس λ راهم به آن اضافه خواهیم کرد .

C=0C+1C+λ


من از معادله حالت C خود متغیر C را نیاز دارم تا بتونم معادله حالت متغیر B  را جایگذاری کنم و از اون جا متغیر B را بدست بیارم و به این ترتیب معادله حالت Aرا جایگزین کنم تا عبارت منظم این ماشین به دست بیارم .

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

دیدید که از هردو روش به جواب یکسان رسیدیم . پس انتخاب با خودتون ، باهرکدوم از هر دو روش که راحت تر هستید  تمرین کنید.
در اینجا به پایان بحث امروزمون میرسیم .


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

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

کلمات کلیدی

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