![[تصویر: 328737_60660a85f1be0b0d5d48cd58116eeb99a6241836.jpg]](https://img.manesht.ir/328737_60660a85f1be0b0d5d48cd58116eeb99a6241836.jpg)
چیزی که من از این سوال فهمیدم اینه که اگر رشته x متعلق به زبان بود باید حداقل یک جایگشت x هم متعلق به زبان باشه، در این صورت اون زبان جایگشتی محسوب میشه.
با یه کم دقت میشه فهمید که زبان های منظم و مستقل از متن، لزومی ندارد که حتما جایگشتی باشند. مثلا اگر یک زبان متناهی منظم رو مثال بزنیم که فقط رشته aabb رو داره واسه این که جایگشتی باشه باید حداقل یه جایگشت aabb مثلا bbaa رو داشته باشه که اینظور نیست. واسه مستقل از متن هم میشه به همین صورت مثال زد/.
پس تا اینجا گزینه یک و چهار غلطه.
برای غلط بودن گزینه ۲ :
اگر زبان [tex](01)^{\ast}[/tex] رو به عنوان یه زبان منظم داشته باشیم، در صورتی جایگشتی میشه که برای هر رشته عضو زبان حداقل یه جایگشت اون نیز عضو زبان باشه مثلا برای رشته ۰۱ باید ۱۰ نیز عضو زبان باشه که دیگه منظم حساب نمیشه.
پس فقط گزینه سه می مونه یعنی هر زبان جایگشتی ، مستقل از متن است.
یک زبان دارید واسه هر رشته ش باید جوری یه دونه از جایگشت هاشو انتخاب کنید که مجموعه ی جایشگتها توسط m پذیرفته بشه یعنی مجموعه ی جایشگتها حتما منظمه اما خود اون زبان می تونه نباشه ممکنه یه زبان دیگه باشه
با این اوصاف گزینه ۱ صددرصد درشته
چون مشا وقتی یه زبان منظم دارید جایگشت هر رشته شو بگیرید reverse ش. واضحه که وقتی زبان L منظمه dfa ای مثل M وجود داره که reverse(L) را بپذیره
پس هر زبان منظم جایگشتی است
اما نادرستی سایر گزینه ها:
زبان [tex]L=\{a^nb^nc^n,\: n\ge0\}[/tex] رو در نظر بگیرید واسه هر رشته از زبان می تونم جایگشتی رو در نظر بگیریم که به فرم [tex](abc)^{\ast}[/tex] باشه یعنی ممی توان مجموعه ای از جایشگتها یافت که منظم باشه و توسط اتوماتون متناهی ای مثل M پذیرفته شود پس با این اوصاف ممکن است یه زبان جایشگتی ، حساس به مت نشود پس گزینه های دو و سه غلط هستند.
گزینه ۴ به نظر غلط می رسه اما اثباتش یه کم سخته مثلا فک نمی کنم زبان ww^R جایشگتی باشه اما نمی تونم اثبات کنم
(۰۳ بهمن ۱۳۹۳ ۱۱:۵۱ ب.ظ)ana9940 نوشته شده توسط: چیزی که من از این سوال فهمیدم اینه که اگر رشته x متعلق به زبان بود باید حداقل یک جایگشت x هم متعلق به زبان باشه،به نظرم استدلالتون درست نیست
وقتی شما یک رشته از زبان رو در نظر می گیرید لزومی نداره جایگشت عضو همون زبان باشه جایگشتش باید توسط اتوماتون m پذیرفته بشه
ممنون دوستان
گزینه یک قطعا اشتباه، مثال های زیادی از زبان متناهی منظم هست که جایگشت رشته اش توسط ماشین متناهی پذیرفته نمیشه، مثلا یه زبان متناهی که فقط یه رشته abb رو داره، واضحه که هیچ جایگشتی از اون رو نمیشه با همون ماشین متناهی پذیرفت. البته یه ماشین متناهی دیگه غیر از ماشین زبان اولیه، میشه براش نوشت. حالا گیج شدم، یعنی اجباری نیست که با همون ماشین متناهی زبان اولیه، جایگشت ها پذیرفته بشن؟؟؟؟
(۰۴ بهمن ۱۳۹۳ ۱۱:۴۰ ق.ظ)ana9940 نوشته شده توسط: واضحه که هیچ جایگشتی از اون رو نمیشه با همون ماشین متناهی پذیرفت. البته یه ماشین متناهی دیگه غیر از ماشین زبان اولیه، میشه براش نوشت. حالا گیج شدم، یعنی اجباری نیست که با همون ماشین متناهی زبان اولیه، جایگشت ها پذیرفته بشن؟؟؟؟
نه لزومی نداره که با همون ماشین اولیه پذیرفته بشن
می گه یه زبان داریم L ( که معلوم نیست منظمه یا مستقل از متنه یا چیز دیگه ای ) اما می خواخیم از هر رشتهش یه دونه جایشگت برداریم به طوریکه مجموعه ی جایشگتها منظم بشه
مثلا همون L={abb}که فرمودید اگه بگشم جایشگتهاش می تونه bab, abb, bba باشه ، ما هر کدوم از این سi تا رو که برداریم باز مجموعه ی بدست آمده از جایشگتها مجموعه ای منظم است
فکر کنم داری اشتباه می کنی. صورت سوال رو یه بار دیگه بخونید:
[تصویر: ۳۲۸۷۳۷_۶۰۶۶۰a85f1be0b0d5d48cd58116eeb99a...6.jpg]
گفته رشته x رو ماشین M می پذیره، حالا جایگشت رو هم همون ماشین M می پذیره.
فکر کنم گزینه صحیح هم طبق کلید و همین طور کتابها همون گزینه سه هست.
(۰۴ بهمن ۱۳۹۳ ۰۲:۳۲ ب.ظ)ana9940 نوشته شده توسط: فکر کنم داری اشتباه می کنی. صورت سوال رو یه بار دیگه بخونید:صورت سوال گفته هر گاه اتوماتون قطعی M ای باشد
[تصویر: ۳۲۸۷۳۷_۶۰۶۶۰a85f1be0b0d5d48cd58116eeb99a...6.jpg]
گفته رشته x رو ماشین M می پذیره، حالا جایگشت رو هم همون ماشین M می پذیره.
فکر کنم گزینه صحیح هم طبق کلید و همین طور کتابها همون گزینه سه هست.
یعنی یه اتوماتون قطعی بشه واسه جایشگت ها پیدا کرد
و نگفته که اتوماتون M حتما L را می پذیرد فقط کافیه جایگشتی از رشته های L رو بپذیره
اگر حرف شما صحیح باشه پس چرا گزینه ۲ غلطه؟ هر زبان جایگشتی که توسط اتوماتون متناهی M پذیرفته می شه پس منظمه که؟
(۰۵ بهمن ۱۳۹۳ ۱۲:۱۷ ق.ظ)Hamid_0311 نوشته شده توسط: پاسخ که خانوم مدیر دادن و درستم هست ولی برای ساده سازی اینکه گزینه یک درسته و جواب گزینه یک هست یه اثبات ساده تر اینه
اینو که همه قبول داریم که ماشین dfa زبان منظم می پذیره
صورت سوالم داره میگه یه جایگشتیشو برداریم یه dfa باشه که بپذیرتش اینم که قبول داریم که این تعریف سوال از زبان جایگشتی به نوعی عملگر shuffle هستش
اینم میدونیم زبان های منظم تحت عملگر shuffle بسته هستن
پس واضحه که گزینه یک درست هست بقیه گزینه هام با اون مثال های که زدن میشه نقض کرد
موفق باشید
آره این جوری باز قابل قبوله.
حالا یه سوال؟
زبان منظم [tex](01)^{\ast}[/tex] رو داریم. باید هر رشته ای که انتخاب میشه، حداقل یک جایگشت اون نیز عضو زبان باشه من اگه رشته ۰۱ رو انتخاب کنم، هیچ جایگشتی از اون عضو زبان نیست! خب اینجوری قطعا گزینه یک درست نیست. واسه من این قضیه روشن نیست. الان واسه این مثال ، جایگشت رشته ۰۱ مگه ۱۰ نیست؟؟ خب ۱۰ که عضو زبان حساب نمیشه؟؟تنها در یک صورت گزینه یک درسته که فرض کنیم جایگشت رشته x رو با یک زبان منظم دیگه پیاده سازی کنیم نه خود زبان اصلی. ولی در صورت سوال دو ماشین رو جدا نکرده، مثلا باید این جوری می گفت:
"گویی زبان ......... هر گاه یک اتومان قطعی متنهای M باشد به طوری که .....
اگر و تنها اگر جایگشتی از رشته x رو اتومان M2 بپذیرد"
کتاب کنکور ۹۱ مقسمی رو من رفتم دیدم دوباره، اون گفته گزینه سه درسته و واسه غلط بودن گزینه یک هم مثال نقض آورده.
سوال حس میکنم ابهاماتی داره اون جواب خودمم با اجازه دوستان پاکش میکنم چون حس میکنم نمیشه اینطوری توجیه اش کرد و یه جورای یه مبحث دیگه قاطی میشه
ابهاماتی مثل اینکه صرفا همون ماشین بپذیرتش یا ماشین دیگه
صرفا تمام رشته ها تحت یکی از جایگشت ها پذیرش باشن یا نه ماشین بلاخره یکی از چایگشت های اون رشته را بپذیره
با عرض معذرت از دوستان بنده پستمو پاک میکنم