ادامه عملگرهای زبان و تعریف عبارتهای منظم
سلام محمدرضا احمدآبادی هستم با جلسه چهارم آموزش نظریه زبانها و ماشین ها در خدمتتون هستم .
در جلسه گذشته اومدیم یه سری عملگر روی زبان ها را بررسی کردیم و برای هرکدوم از این عملگرها مثال اوردیم اما چند عملگر دیگه مثل بستار و متمم را قرار گذاشتیم برای این جلسه که انرژی بیشتری داشته باشید با هم کار کنیم و در اخر این جلسه هم یه مختصر مبحث جدید قصد دارم که بگم .
خب صورت مثال جلسه قبل که فراموشتون نشده؟
نمیدونم چرا یه حسی داره به من میگه : محمدرضا سنگین تر هستی که خودت یه بار دیگه صورت مثال جلسه قبل را بنویسی . شما هم موافقید؟
حدس میزنم که اکثرا موافق هستید
خب پس یه بار دیگه براتون صورت مثال جلسه قبل را مینویسم و بعد میرویم سراغ موارد باقی مونده از مثال
با در نظر گرفتن دو زبان زیر موارد خواسته شده را بدست اورید.
L1={ anbn/ n>=0} , L2={ wԑ{a,b} ̽ / na(w)=nb(w) }
خب جلسه قبلی تا مورد H رفتیم جلو حالا بریم سراغ بقیه موارد.
I) L2 ̽=?
برای این که بستار زبان L2 را بدست اوریم یک بار دیگه به تعریف بستار که در جلسه قبل گفته بودم دقت کنید :
در جلسه قبلی بستار را این طوری تعریف کرده بودم
بستار:
L ̽=L.L.L….=L0 ᴜL1ᴜL2ᴜ….
حالا سوال من این هست اگر زبان L2 را با خودش چندین دفعه اجتماع بگیریم ( یا باخودش چندین بار الحاق کنیم ) زبان بدست اومده از این عمل به چه شکلی خواهد بود؟
خود زبان L2 رشته هایی را قبول میکنه که تعداد a,b داخل رشته ها مساوی باشه. خب در رابطه با اجتماع این زبان با خودش میشه گفت شامل رشته هایی میشه که باز هم a,b مساوی خواهند داشت .
حالا یه سوال: مگه نگفتیم زبان L2 شامل رشته هایی هست که a,b مساوی دارند پس شکل زبان این اجتماع به نظرتون چطور خواهد بود؟
من که میگم خود زبان L2 خواهد بود.چون هر رشته ای که از این اجتماع بدست بیاد داخل خود L2 از قبل بوده، حالا به هرتعدادی که دلتون میخواد این زبانو با خودش اجتماع بگیرید اما این شرط مساوی بودن تعداد a,b باز برقرار خواهد بود. مگه نه؟
J) L1 ̽=?
اگه یه همچین روندی که در مورد بالا طی کردیم برای این زبان هم طی کنیم خواهیم دید که جواب به این صورت خواهد شد:
{(a(m)b(m))(i) /i>=0, در هر تکرار ( ام) میتواند متفاوت از تکرار های قبلی باشد }
امیدوارم که از پرانتز گزاری های قسمت اول گیج نشده باشید ، هر چند که بعید میدونم اما لطفا قراری که با همدیگه در جلسه دوم اموزش بین خودمون گذاشتیمو ( درباره محدودیت های تلگرام ) به یاد بیارید.
K) L1 ˊ=?
خب متمم زبان L1 به نظرتون چی میشه؟
در تعریف متمم گفته بودیم تفاضل مجموعه جهانی از مجموعه مورد نظر میشه متمم. یادتون اومد؟
خود زبان L1 رشته هایی را میپذیره که سمبل های a باید قبل از اولین b بیایند پس متمم این زبان میشه:
{ wԑ {a,b} ̽/ w≠ anbn, n>=0}
توصیف این زبان: رشته های مورد پذیرش این زبان به طوری است که نباید سمبل های a قبل از اولین b نوشته شوند.( و اگه بخوام بهتر براتون بگم متمم این زبان میشه رشته هایی که تحت قانون رشته های مورد پذیرش زبان L1 نباشند)
L) L2 ˊ=?
زبان L2 میگه رشته های مورد پذیرش من باید تعداد a,b مساوی داشته باشند. پس متمم این زبان میشه رشته هایی که تعداد a,b مساوی نداشته باشند.
اگر بخواهیم این زبان حاصل متمم را به صورت رسمی نشان دهیم به این شکل خواهد بود:
{ wԑ{a,b} ̽/na(w)≠nb(w) }
خب باید عرض کنم که در این جا این مثال وحشت انگیزناک به پایان رسید . امیدوارم خسته نشده باشید چون هنوز اون مختصر بحث جدیدی که اول جلسه امروز بهتون قول داده بودم را هنوز نگفتم.
عبارت های منظم:
عبارت منظم ابزاری است که برای بعضی از زبان ها توصیف میشود تا پذیرش یا عدم پذیرش یک رشته توسط ان زبان بررسی شود.
نکته: عبارت منظم را تنها برای زبان های منظم میتوان نوشت.(لطفا به این جمله فعلا توجه نکنید ، چون من هنوز زبان منظم را تعریف نکرده ام).
یک عبارت منظم از سه جزء تشکیل میشود:
1) الفبای زبان: هر یک از سمبل های الفبا و همچنین سمبل λ میتواند در یک عبارت منظم مورد استفاده قرار گیرد.
2) عملگرهای زبان: سه نوع عملگر در عبارت های منظم به کار میرود( نه بیشتر)
[ Photo, عملگرهای تعریف شده برای نوشتن عبارت منظم ]
3) علامت پرانتز برای دسته بندی.
نکته : در یک عبارت منظم فقط از موارد بالا استفاده میشود ونه هیچ چیز دیگری.
خب برای این جلسه دوتا مثال باهم بررسی خواهیم کرد و برای دو جلسه اینده هم هیچ مبحث جدیدی نخواهیم گفت و فقط مثال های عبارت منظم نویسی را با هم بررسی خواهیم کرد .یعنی تقریبا هیجده یا نوزده تا مثال خواهیم داشت . البته نترسید مثال ها از اسون شروع میشه و کم کم شعله زیرشون زیاد میشه.
مثال ) برای هریک از زبان های زیر عبارت منظم بنویسید.
L1={an / n>=0}
خب این زبان داره به ما میگه رشته های مورد پذیرش من فقط الفبای a باید داشته باشد . وطبق شکلی که درباره عملگرهای عبارت منظم براتون گذاشته بودم اگر بخواهیم این زبان را با عبارت منظم نشان دهیم خواهیم داشت:
a ̽
L2={an / n>=1}
تفاوت این زبان با زبان قبلی در این هست که زبان قبلی رشته لامبدا را میپذیرفت ولی این زبان رشته لامبدا را نمیپذیرد برای نمایش دادن عبارت منظم این زبان دو روش وجود داره یکی اگر طبق شکل بخواهیم نشان دهیم باید بنویسیم a(+) اما بعضی از کتاب ها عملگر پلاس را به رسمیت نمیشناسند برای همین میان داخل عبارت منظم اجبار یکبار a را میگذارند یعنی مینویسند:
aa ̽
با این عبارت هررشته ای که بخواهید تولید کنید مجبور هستید که حتما حداقل یک بار سمبل a را نشان دهید. چرا؟
زیرا a اول عملگر استار ندارد یعنی ما نمیتونیم این سمبل a را در نظر نگیریم.اما اگر الفبایی عملگر استار را داشته باشد اختیار عدد فرض شده استار با خود خواننده هست وحتی میتواند صفر در نظر بگیرد.
نکته: اگر در عبارت منظمی به این شکل دیدید :
a ̽ b ̽
باید عرض کنم که عدد فرض شده استارa با عدد فرض شده استار b میتواند یکجور باشد ( دقت کنید گفتم میتواند و نگفتم حتما باید یکجور باشد. )
امیدوارم این نکته ای که گفتم هیچ موقع فراموشتان نشود.( چون تقریبا همین نکات ریز هستند که نظریه زبان ها را جالب (زهردار) میکنند) مخصوصا این دو جلسه بعدی که در پیش داریم.
خب مطالب این جلسمون به پایان رسید امیدوارم برای جلسه اینده خودتون را به خوبی اماده کنید ( من هیچ موقع ناامید نمیشوم )، چون دو جلسه اینده کلا در حال مثال حل کردن خواهیم بود .
نظرات کاربران