سلام
تمرین ۱۳ قسمت الف فصل ۴ بخش ۳ کتاب لینز یه تمرین داره که آیا زبان زیر منظم هست یا نه ؟
صفحه ۱۳۴ ترجمه دکتر صراف زاده
به نظر من منظم نیست ولی تو حل المسائل و حل تمرین منتخب ترجمه جعفر تنها قید شده منظم و البته توضیحات هم برام قابل قبول نبود.
میخواستم نظر شما رو هم بدونم.
تو کنکور علوم ۸۵ هم یه تست بود که یه گزینه اش همین زبان بود که اونجا نامنظم در نظر گرفته شده.
[tex]L=\left \{ uww^{R}v : u,v,w\in \left \{ a,b \right \}^{ } \right \}[/tex]
البته میشه حالت خاص تعریف کرد که در این فرم قرار بگیره ولی برداشت من این بوده که با حالت خاص نمیشه گفت زبان منظم هست.
مثل:
[tex]\left ( a b \right )\left ( a b \right )^{*}\left ( aa bb \right )\left ( a b \right )\left ( a b \right )^{*}[/tex]
سپاسگزارم
این مثالی که شما زدید اشتباه ست. الان شما WW^R رو چطور مشخص کردید؟ با aa + bb ؟
فکر می کنم این زبان منظم باشه. و بصورت [tex](a b)^{ }[/tex] باید باشه!
به نظر من زبان منظمه. اون عبارت به نظرم با کمی اغماض درسته:
[tex]\left ( a b \right )^{ }\left ( aa bb \right )\left ( a b \right )^{ }[/tex]
(۰۱ مرداد ۱۳۹۲ ۱۱:۱۰ ب.ظ)azad_ahmadi نوشته شده توسط: الان شما WW^R رو چطور مشخص کردید؟ با aa + bb ؟مشکلش کجاست؟
فقط در صورتی که [tex]w\epsilon (a,b)^{*}[/tex] باشه میتونیم بگیم زبان منظم هست چون فقط در اینصورت میشه [tex]\lambda \epsilon (a,b)^{*}[/tex] و باعث میشه [tex]ww^{R}[/tex] را از کل عبارت ساده کرد و زبان منظم میشه اما در حالتیکه [tex]w\epsilon (a,b)^{ }[/tex] هست دیگه [tex]\lambda[/tex] شامل [tex](a,b)^{ }[/tex] نمیشه و نمیشه عبارت کل ساده کرد و [tex]ww^{R}[/tex] از عبارت کل ساده کرد پس این عبارت نامنظم هست.
[tex]ww^{R}[/tex] کلا نامنظم هست.
سلام. [tex]ww^'[/tex] نامنظمه ولی زبان این سوال منظمه. به ازای w با طول یک، تمام رشته های زبان تولید میشه. بقیه رشته ها زیر مجموعه از این زبان هستند. عبارت های منظمی که دوستان نوشتند کاملاً درسته. اگه قبول ندارید یک رشته از عبار منظم مشخص کنید که عضو زبان نباشه و یا یک رشته از زبان رو مشخص کنید که عبارت منظم اونو تولید نکنه.
این تمرین تو کتاب نظریه لینز ترجمه جعفر تنها صفحه ۱۵۴ هست (ویرایش ۵)
تو این کتاب بعضی تمرینها آخر کتاب جوابش هست از جمله همین سئوال
و نوشته:
زبان منظم است. چون هر رشته ای که دارای دو سمبل متوالی یکسان باشد در این زبان قرار دارد. یکی از عبارتهای منظم برای L، [tex]\left ( a b \right )\left ( a b \right )^{*}\left ( aa bb \right )\left ( a b \right )\left ( a b \right )^{*}[/tex]
ولی نمیدونم چرا تجسمش برام سخته، فکر میکنم یه مثال نقض داره
آخه یجورایی رشته w رو محدود کرده به یه کاراکتر
قسمت دوم همین تمرین [tex]L= \left \{ uww^Rv: u,v,w\in \left \{ a,b \right \}^ ,\left | u \right |\geqslant \left | v \right | \right \}[/tex] هست که منظم هم نیست.
و اونچه که تو کنکور علوم ۸۵ بود:
[tex]\left \{ uww^Rv : u,v,w\in \left \{ 0,1 \right \}^* \right \}[/tex]
که با توجه به کلید منظم هست.
و یه خط هم آقای مهربخش توضیح نوشتن که به دلیل وجود u و v در دو طرف w و w^R ارتباط مسقیم اونها از بین رفته.
این تنها موردی از [tex]ww^R[/tex] بوده که دیدم منظم هست.
مرز بین u , v , w مشخص نیست، بخاطر همین یه مقدار گنگ هست.
اونچه که مشخصه تعریف زبان منظم هست، "زبانی منظم است که حداقل برای اون یک عبارت منظم پیدا بشه".
هر رشته ای از اون زبان رو که شما بخواید بنویسید با اون عبارت منظمی که نوشتید خودتون قابل بیان هست.
این زبان منظم هست و دلیلش هم واضحه چون شما هر شته ای در نظر بگیری طبق صورت سوال و البته لم تزریق میتونی تشخیص بدی که زبان منظم هست البته کنکور دیگه جای لم تزریق نیست!! توضیح سادش میشه اینکه uوv دو طرفه رشته معکوس میتونن همه رشته ها رو هم پوشان کنن
لم تزریق هیچ فایده ای برای این سوال نداره. لم تزریق یه اثبات به روش مثال نقضه که درصورت انتخاب شدن رشته مناسب از زبان، میتونه مشخص کنه که زبانمون منظم یا مستقل از متن نیست. به هیچ وجه برای اثبات منظم بودن کاربرد نداره.
خیلی واضحه که منظمه . اون ww' که وسط هست رو در نظر بگیر . قبول داری که اخرین حرف w میشه اولین حرف w' ؟ حله! پس حتما وسط رشته یه حرف تکرار میشه . دیگه بقیه حروف w و w' میچسبن به u و v که اونها می تونن هر ترکیبی از a و b باشند. به این ترتیب هر رشته ای که یک حرف اون وسط ها تکرار بشه ( البته طول رشته های این زبان حداقل ۴ هست ) جزو این زبانه که میشه همون عبارت منظمی که نوشتید.
(۰۳ مرداد ۱۳۹۲ ۰۱:۱۰ ق.ظ)Jooybari نوشته شده توسط: لم تزریق هیچ فایده ای برای این سوال نداره. لم تزریق یه اثبات به روش مثال نقضه که درصورت انتخاب شدن رشته مناسب از زبان، میتونه مشخص کنه که زبانمون منظم یا مستقل از متن نیست. به هیچ وجه برای اثبات منظم بودن کاربرد نداره.دقیقا درست می فرمایین من نیست از کنکور به این ور درس نخوندم صوتی دادم- برا مثال خلف بر رد زبان استفاده میشه!! ولی خوب قسمت دوم جوابم درسته ادبیاتش واضح نبود ولی به نظرم درست بود
پس زبان مورد نظر منظم هست.
حالا میشه به طریق مشابه گفت که زبانهای زیر هم منظم هست ؟
[tex]L_{1}=\left \{ ww^Rv : w,v\in \left \{ a,b \right \}^ \right \}[/tex]
و
[tex]L_{2}=\left \{ ww^Rv : w,v\in \left \{ a,b \right \}^* \right \}[/tex]
- L1 نامنظم و L2 منظم اعلام شده.
- میشه برای L1 عبارت منظم زیر رو نوشت ؟
[tex]\left ( aa bb \right )\left ( a b \right )^ [/tex]
- L1 با لم تزریق و رشته [tex]w=\left ( ab \right )^m\left ( ba \right )^ma[/tex] منظم بودنش رد شده.
(۰۴ مرداد ۱۳۹۲ ۰۶:۳۹ ب.ظ)iman_n21 نوشته شده توسط: پس زبان مورد نظر منظم هست.
حالا میشه به طریق مشابه گفت که زبانهای زیر هم منظم هست ؟
[tex]L_{1}=\left \{ ww^Rv : w,v\in \left \{ a,b \right \}^ \right \}[/tex]
و
[tex]L_{2}=\left \{ ww^Rv : w,v\in \left \{ a,b \right \}^* \right \}[/tex]
- L1 نامنظم و L2 منظم اعلام شده.
- میشه برای L1 عبارت منظم زیر رو نوشت ؟
[tex]\left ( aa bb \right )\left ( a b \right )^ [/tex]
- L1 با لم تزریق و رشته [tex]w=\left ( ab \right )^m\left ( ba \right )^ma[/tex] منظم بودنش رد شده.
سلام.
چون سوالات یه جورایی به سوال ابتدای تاپیک مرتبط میشه، اشکال نداره، اما هر سوالی رو باید در یک تاپیک پرسید.
عبارت منظمی که براش نوشتین درست نیست. چرا که براش شرط گذاشتین و هر رشته ای که بخوایم بنویسیم، باتوجه به عبارت منظم شما یا با aa و یا با bb شروع میشه.