ماشین ها و ماشین های متناهی

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

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

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

ماشین های متناهی:
ماشین های حالت متناهی ، ماشین هایی هستند که برای پذیرش زبان های منظم طراحی میشوند. مدل انتزاعی هر ماشین متناهی  دارای یک نوار ورودی ، یک نوارخوان و یک کنترل کننده ی وضعیت به شکل زیر است:

رشته ورودی بر روی  نوار ورودی قرار میگیرد  و کنترل کننده وضعیت  که تنها قادر به خواندن سمبل ها و تغییر وضعیت است  با تغیر وضعیت های متوالی بررسی میکند که آیا رشته ورودی نوار توسط  ماشین پذیرفته  خواهد شد. یک رشته زمانی پذیرفته میشود که نوارخوان در انتهای رشته ورودی باشد و وضعیت ماشین ، در یک وضعیت پایانی باشد.

تعریف استاندارد ماشین متناهی قطعی (DFA):
یک ماشین متناهی قطعی یا DFA یک پنج تایی به فرم زیر میباشد:

M=(Q,∑,q0,δ,F)


که در آن:
Q : یک مجموعه متناهی و غیر تهی از حالت ها  یا وضعیت های ماشین می باشد.
∑ :  یک مجموعه متناهی و غیر تهی از الفبای  زبان ماشین  می باشد.
q0 ԑQ   : بیانگر حالت شروع است.
F  : یک مجموعه غیر تهی از حالت های پایانی ماشین است.
 δ : مجموعه توابع انتقال ماشین است  که هر تابع آن به شکل زیر توصیف میشود:

δ : Q * ∑→Q


این عبارت بیان میکند که هر حالت از ماشین  با هر یک از سمبل های الفبا  به چه حالت دیگری  از ماشین منتقل خواهد شد.  برای مثال   δ(qi,a)=qj  بیان میکند که حالت qi با سمبل الفبایی a به حالت qj منتقل میشود.

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

 

M=(Q,∑,q,δ,F),   Q={q0,q1,q2},   ∑={a,b} ,  q=q0 ,    F={q2}
δ (q0,a)= q0 , δ(q0,b)=q1, δ(q1,a)=q2, δ(q1,b)=q2,δ(q2,a)=q0,δ(q2,b)=q1

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

مثال) با توجه به مثال قبل  پذیرش رشته های w را بررسی کنید.
 

W= bbab

برای این که ببینیم این رشته توسط ماشین پذیرفته می شود اون شکل حالت انتزاعی را در ذهنتون تصور کنید و همچنین قواعد تولید این ماشین را هم در کنار دستتون داشته باشید.  روی نوار سمبل های رشته w را قرار دهید. برای شروع باید از حالت q0 روند انتقال را بررسی کنیم .  خب با این حساب در مرحله اول خواهیم داشت:

حالا باید ببینیم  در قواعد انتقال ببینیم حالت q0با سمبل b به چه حالتی رفته تا هدنوارخوان هم به اون حالت برود. که در قوانین انتقال داشتیم:  δ(q0,b)=q1 پس هد به حالت q1 میرود .

حالا باید ببینیم حالت q1 با سمبل b به چه حالتی رفته. در قوانین انتقال ماشینمون داریم:   δ(q1,b)=q2   پس ماشین به حالت q2 میرود.

حالا موقع این رسیده که حالت q2 را با سمبل a چک کنیم که با توجه به قوانین انتقال میشود:    δ(q2,a)=q0   پس ماشین در این حالت به q0 میرود( یعنی حالت شروع)

حالا باید q0  را با سمبل b ببینیم که میشود:    δ(q0,b)=q1  پس ماشین به حالت q1  میرود.

خب سمبل های رشته مورد نظر تموم شد حالا باید حالت ماشین را نگاه کنیم اگر جز مجموعه حالت های پایانی بود رشته پذیرفته میشود وگرنه این زبان و این ماشین این رشته را نمیپذیرد.
حالت پایانی این مثال فقط حالت q2 بوده و ماشین در حالت q1 قرار دارد پس رشته مورد نظر ، مورد پذیرش این ماشین نیست.

زبان ماشین:
 اگر  M=(Q,∑,q,δ,F)  یک ماشین متناهی باشد  مجموعه تمامی  رشته های ورودی  ∑ که توسط M پذیرفته میشود را زبان  ماشین میگویند و آن را با L(M) نمایش می دهند به عبارت  دیگر :

 

L(M)={wԑ ∑*| δ*(q0,w) ԑ F}

متمم زبان ماشین:
متمم زبان ماشین مجموعه رشته هایی است که توسط ماشین پذیرفته نمیشوند و به صورت زیر نمایش داده میشوند.

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

مثال) توابع انتقال  ماشین متناهی مطرح شده در مثال امروزمون خواهد شد:

نمودار وضعیت DFA : نمودار وضعیت یک DFA گراف برچسب دار، جهت داریست  که با توجه به قوانین زیر ساخته میشود:

مثال) نمودار وضعیت DFA مثال قبل با توجه به این نکات خواهد شد:

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

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

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

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

کلمات کلیدی

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