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

آقای احمد آبادی 1395/1/14 1856

معرفی عملگرها روی رشته ها

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

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

مثال)

L={ wԑ {a, b}  ̽ /na(w) =nb(w)}

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

قبل از این که من توصیف این زبان را براتون بگم ، خودتون فکر میکنید این زبان چه رشته هایی را میپذیره؟

حالا بریم سراغ توصیف زبان و ببینید که آیا حدسی که زده بودید درست بوده یا نه: این زبان میگه من رشته هایی را میپذیرم که اولا الفبای به کار برده شده داخل ان ها  a,b  باشد  ثانیا تعداد a  به کار برده شده در این زبان باید برابر با تعداد b  به کار برده شده باشد و بالعکس.

خب این زبان یه زبان نامحدود هست برای همین من قسمتی از رشته های مورد پذیرش این زبانو براتون مینویسم تا سرنخ رشته های این زبان دستتون بیاید.

{ λ, ab,ba,aabb,baba,bbbabaaa,ababababab,……}

حالا که بحث این زبان باز شد یه مثال دیگه  بزنیم:

مثال)

L={ anbn /n>=0}


سوال : این زبان چه رشته هایی را میپذیرد؟

مسلما الان همتون دارید میگید رشته هایی که تعداد a ,b مساوی دارند . پس همون مثال قبل هست ولی به یک شکلی دیگه.

خب بریم ببینیم ایا درست گفتید یا نه؟

الفبای این زبان همون الفبای مثال قبله یعنی a , b . تعداد a , b  هم طبق  حرف n  که برای هردو ذکر شده این حرف را میزنه که باید تعداد این دو الفبا  در رشته مورد پذیرش زبان با هم برابر باشه. ولی این زبان داره با زبون بی زبونی میگه علاوه بر این شروط  رشته های مورد پذیرش من باید این جوری باشه که حرف a  هرچقدر که میخواهید به کار ببرید در رشته های من باید قبل از اولین حرف b  باشد.به زبان خودمون یعنی در رشته اول باید a  های مورد نظرمونو بنویسیم بعد به همون تعداد باید حرف b  را بنویسیم. پس این زبان خیلی  محدود تر نسبت به زبان مثال قبله.

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

حالا رشته های مورد پذیرش این زبان اینا هستند:

{λ, ab,aabb,aaabbb,aaaabbbb,….}

در واقع این زبان زیرمجموعه زبان مثال قبله.

حالا اگه تو صورت زبان به جای شرط     n>=0 ، گفته میشد   n>0 یا n>=1  اون وقت رشته های مورد پذیرش این زبان چگونه بودند؟

در شکل ظاهری  رشته ها تغییری به وجود نمیاد اما دیگه ما نمیتونیم رشته تهی را داشته باشیم یعنی لامبدا جزء رشته های مورد پذیرش این زبان نمیشد. چون طبق شرط حداقل یک بار باید ab تکرار (یا نوشته ) شده باشند.

واما بریم سراغ بحث جدید امروزمون
عملگرهای روی زبان:

اجتماع:رشته های مورد پذیرش این عملگر یا عضو رشته های مورد پذیرش زبان اول خواهند بود ویا عضو رشته های زبان دوم

L1ᴜL2={ wԑ ∑  ̽/ wԑL1  OR  wԑL2}

اشتراک: رشته هایی از دو زبان که در هردو زبان موجود باشد.

L1∩L2={ wԑ∑  ̽/ wԑL1  And  wԑL2}

تفاضل: هررشته ای که در زبان اول هست اگر در زبان دوم هم وجود داشته باشد ان را خط زده و مابقی رشته ها ان زبان پاسخ خواهد بود.

L1-L2= {  wԑ ∑  ̽/wԑL1  And  w!ԑ L2}

یعنی رشته هایی از L1 که داخل L2 نیست.

الحاق: رشته هایی که قسمت اولشان از رشته های زبان L1 و قسمت دوم اونها از زبان L2 باشد.

L1.L2={xyԑ ∑  ̽ / x ԑ L1  And y ԑ L2}

معکوس: رشته های یک زبان را همه را معکوس کنید.

L(R)= {w ԑ ∑  ̽/ w(R) ԑ L}

بستار:

L  ̽=L.L.L….=L0 ᴜL1ᴜL2ᴜ….

متمم: در مجموعه های ریاضی وقتی متمم را تعریف میکردیم میگفتیم متمم یک مجموعه میشود تفاضل مجموعه جهانی از مجموعه ذکر شده. این جا هم داستان همینه :

L ˊ =∑  ̽-L

خب بریم سراغ یک مثال جامع)

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

L1={ anbn/ n>=0}  , L2={ wԑ{a,b}  ̽ / na(w)=nb(w) }

A)  L1ᴜL2=?

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

B)  L1∩ L2=?

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

C)  L1-L2=?

برای این که بتونیم حاصل این مورد را بدست بیاریم ازتون خواهش میکنم یک بار دیگه توصیف این دوزبان را که در اول بحثمون گفتم را بخونید .
زبان L1  رشته هایی میپذیره که a,b مساوی داشته باشند و در این رشته ها سمبل a به هر تعداد که بخواهیم بنویسیم باید قبل از اولین b نوشته شود.
اما زبان L2 به قول خودمون کلاهشو گذاشته بالاتر و میگه فقط باید تعداد a,b در رشته های من مساوی باشه حالا به هرشکلی که هست.
خب به نظرتون اگه زبان L1  را بخواهیم از زبان L2کم کنیم جواب چی میشه؟
جواب میشه اون رشته هایی از L2 که تعداد a,b مساوی دارند وهمه سمبل های a نباید قبل از اولین سمبل b باشند.
حالا اگه بخواهیم شکل رسمی این زبان جدیدو بنویسیم این شکلی میشه:

L2-L1= { wԑ{a,b}  ̽ / w≠anbn,n>=0  ,  w=na(w)=nb(w) }

E)  L1.L2=?

به نظرتون الحاق این دو زبان میتونه چه غول بی شاخ و دمی تولید کنه؟

زبان L1  و زبان L2 هردو زبان های نا محدود هستند. میخوام جواب این سوالو با یه مثال از این دو زبان براتون حل کنم.

L1={λ,ab,aabb,aaabbb,…}   w1=ab ,   w2=aabb
L2={λ, ab,abab,ababab,aabbab,…}   w3=ab  , w4=abab

در بالا براتون اول اومدم بعضی رشته های مورد پذیرش این دو زبانو نوشتم و از این رشته ها برای هرکدوم از زبان ها دو تا زیر رشته از این مجموعه ها انتخاب کردم.

حالا با هم حساب کنیم :

W1= ab, W3=ab  →  W1.W3= abab

W1=ab  ,W4=abab  → W1.W4= ababab

W2=aabb  , w3=ab  → W2.W3=aabbab

حالا به  جواب هایی که از الحاق دو زیر رشته در هر مرحله به دست اومده یه بار دیگه دقت کنید. به نظرتون اشنا نیست ؟

به نظرتون چند سطر بالاتر به عنوان رشته های مورد قبول زبان L2 من نیاورده بودم؟

فکر کنم گرفتید میخوام چی بگم . دقیقا حدستون درسته!!!

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

F)L2.L1=?

خب جواب این هم میشه L2. چرا؟
اگه روند مورد قبلی را برای این مورد هم به کار ببرید خواهید دید همون زبان L2 بدست میاد .

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

G)  L1(R)=?

این مورد داره از ما معکوس زبان L 1 را میخواهد . خود این زبان رشته هایی را میپذیرفت که اولا تعداد a,b مساوی داشتند ثانیا  همه سمبل های a  باید قبل از اولین سمبل b نوشته شده باشند. خب معکوس این زبان میشه رشته هایی هست که همه سمبل های b باید قبل از اولین سمبل a  نوشته شده باشند پس میشه:

L1(R )={bnan / n>=0}

H)  L2(R)=?

حتما الان تو فکرتون یه علامت سوال خیلی بزرگ به وجود اومده و با خودتون میگید دیگه  معکوس زبان L2 چی هست ؟

این که رشته های مورد پذیرشش قاعده خاصی نداره.
اجازه بدید این را هم با مثال براتون حلاجی کنم.

L2={ab, aabb,bbaa,abab,ba,baba,….}
W1=ab  → W1(R )= ba

W2=abab  →W2(R )=baba

به مثالی که براتون زدم دقت کنید دو نمونه زیر رشته از رشته های مورد پذیرش زبان L2  انتخاب کردم و معکوس اون ها را بدست اوردم اگه خوب به رشته اصلی و معکوس اون ها توجه کنید متوجه خواهید شد که رشته های معکوس شده قبلا جز رشته های مورد پذیرش زبان قرار گرفته بودند. خب به چه نتیجه ای رسیدید؟

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

قسمت بعدی قسمت قبلی