نظریه زبان ها و ماشین ها عملگرهای رشته و معرفی زبان

1396/5/2 محمدرضا احمدآبادی 4516

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

بریم سراغ مبحث جدید امروز

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

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

مثال)  

W=abb→w(R)=bba

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

W(1)=aa , w(2)= ba→ w(1).w(2)=aaba

چند نکته:

  w1.w2≠w2.w1
|w1.w2|= |w1|+|w2|
  w.λ=λ.w=w
λ(R)=λ

تکرار متناهی یک رشته: یک رشته را که به تعداد متناهی تکرار میشود با ( w(n   نشان میدهند که n  یک عدد صحیح خواهد بود . (w(n به معنی الحاق n  مرتبه رشته w  با خودش می باشد.
مثال)

 w(2)=ww
 w(3)=www=w(2)w
 w=ab→w(2)=abab

بستار یک رشته:
w ̽ :  
مجموعه ای از رشته هایی است که از تکرار صفر بار یا بیشتر رشته w   که با خود الحاق میشود ، بدست می اید.
  w(+):
مجموعه ای از رشته هایی است که از تکرار یک بار یا بیشتر رشته w  که با خود الحاق میشود، بدست می اید.
البته بین خودمون باشه معمولا بستار برای رشته ها به کار نمی رود، بلکه برای مجموعه الفبایی یک زبان مورد استفاده قرار میگیرد. اما من برای یادگیری عمل بستار براتون روی رشته تعریفش کردم
مثال) اگر ∑ یک مجموعه الفبایی باشد ، انگاه:
 ̽ ∑= مجموعه تمامی رشته های روی ∑ به همراه λ
(+)∑= مجموعه تمامی رشته های روی ∑ بدون λ.

نکته: {λ}-̽ ∑=(+)∑ .   البته لازم به گفتن نبود چون فکر کنم تا الان خودتون این نکته را گرفته بودید که اگه از استار لامبدا را حذف کنیم همون پلاس به دست می اید. اما نمیدونم چرا علاقه زیادی دارم به پررنگ نشون دادن موارد واضح

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

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

1-  در   مجموعه رشته های ̽ ∑ ، λ هم عضو باشد.
2-   اگر سمبل a  عضو مجموعه ∑ هست انگاه این سمبل باید عضو بستار این مجموعه هم باشد.
3-  اگر رشته w عضو  سیکما استار باشد و همچنین الفبای a  عضو مجموعه الفبای زبان باشد الحاق این سمبل با رشته باید داخل مجموعه سیکما استار ( ̽ ∑) باشد.

مثال )
 

∑={a,b} →∑  ̽={λ , a,b,aa,ab,ba,bb,aaa,abb,…}

مثال ) اگر {a,b,c  } = ∑ باشد ، انگاه ̽ ∑ به صورت زیر بدست می اید :
 

∑(0)={λ}
∑(1)={a,b,c}
∑(2)={aa,ab,ac,ba,bb,bc,ca,cb,cc}
∑(3)=…..
حال ̽ ∑ میشود اجتماع (0)∑ تا (i) ∑ .


̽ ∑ مجموعه ای است که در ساخت ان از دو عملگر اجتماع ( بین ̽ ∑ ها ) و الحاق ( برای ساختن  هر ̽ ∑ ها) استفاده میشود.
نکته : هر رشته که از ̽ ∑ انتخاب شود و با یکی از سمبل های الفبا ∑ الحاق شود رشته حاصل نیز در ̽ ∑ خواهد بود . حاصل الحاق هر دو رشته از مجموعه  
̽ ∑ در خود ̽ ∑ خواهد بود.
زبان :
به مجموعه ای از رشته ها که بر روی یک مجموعه الفبا ساخته میشوند ، زبان میگویند. یک زبان میتواند متناهی یا نا متناهی باشد . معمولا یک مجموعه ی زبان را با حرف   L نشان میدهند.
مثال)

{a,b }=∑

 زبان محدود    ab,aa,ba,bb }= L1}
زبان نامحدود   λ,a,aa,aaa,….. }=L2}

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

نکته خیلی خیلی خیلی خیلی مهم : تعریف یک زبان  باید طوری باشد که نه هیچ عضوی از این مجموعه رشته ها کم شود و نه هیچ رشته اضافی را شامل شود.

دلیل تاکید من این هست که بعدا وقتی میخواهید زبانی متناسب با چیزی که از شما خواسته شده را بسازید به این نکته توجه معمولا نمیکنید

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

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

حق باشماست منم باهاتون هم عقیده هستم  اما در همین حد فقط در احساس تاسف خودتون منو شریک بدونید اما  کاغذ و قلمو نمیتونم براتون حذف کنم

مثال)

∑={a,b}  L1={wԑ∑  ̽ / |w| = 2}


خب برای اولین قدم بزارید اعضای این مثالو براتون تعریف کنم.
{a,b }=∑ : همون الفبای زبان  L1 هست.
L1 : اسم زبان هست . (کاملا دل بخواهی هست.)
    ̽ ∑ ԑ w  : معنیش میشود، رشته هایی از این زبان با این الفبا

معمولا بعد از این قسمت / میگذارند تا شرط یا ویژگی اون رشته مورد پذیرش زبان را بگن  که شرط این زبان این هست که طول رشته های مورد پذیرش این زبان باید 2 باشد. یعنی رشته هایی که این زبان میپذیره اینا هستند:
 

L1={aa,ab,ba,bb}

البته یادتون نرود که  فقط از الفبای گفته شده باید استفاده کرد

واینک توصیف فارسی یک جمله ای این زبان: رشته هایی با الفبای {a,b } که باید طول این رشته ها 2 باشد.

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

در همین مثال چون از ̽  ∑ استفاده شده بود انتخاب جایگاه الفبا در رشته به عهده خودتون بود و چینش الفبا دررشته در این زبان قاعده مخصوصی نداشت فقط تنها شرطی که این زبان داشت این بود که به شما میگفت با این دو الفبای a  و b  هر رشته ای که دوست دارید بسازید ولی طول اون رشته باید 2 کاراکتر باشد.

مثال)
 

L2={an/ n>=0}

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

طبق جمله بالا متوجه میشویم که الفبای زبان L2 فقط  سمبل a  است

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

L2 ={λ,a,aa,aaa,aaaa,….}

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

کلمات کلیدی

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