یک زبان دارید واسه هر رشته ش باید جوری یه دونه از جایگشت هاشو انتخاب کنید که مجموعه ی جایشگتها توسط 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 نوشته شده توسط:  فکر کنم داری اشتباه می کنی. صورت سوال رو یه بار دیگه بخونید:

[تصویر: ۳۲۸۷۳۷_۶۰۶۶۰a85f1be0b0d5d48cd58116eeb99a...6.jpg]

گفته رشته x رو ماشین M می پذیره، حالا جایگشت رو هم همون ماشین M می پذیره.
فکر کنم گزینه صحیح هم طبق کلید و همین طور کتابها همون گزینه سه هست.

صورت سوال گفته هر گاه اتوماتون قطعی M ای باشد
یعنی یه اتوماتون قطعی بشه واسه جایشگت ها پیدا کرد
و نگفته که اتوماتون M حتما L را می پذیرد فقط کافیه جایگشتی از رشته های L رو بپذیره


اگر حرف شما صحیح باشه پس چرا گزینه ۲ غلطه؟ هر زبان جایگشتی که توسط اتوماتون متناهی M پذیرفته می شه پس منظمه که؟

چیزی که من از این سوال فهمیدم اینه که اگر رشته x متعلق به زبان بود باید حداقل یک جایگشت x هم متعلق به زبان باشه، در این صورت اون زبان جایگشتی محسوب میشه.
با یه کم دقت میشه فهمید که زبان های منظم و مستقل از متن، لزومی ندارد که حتما جایگشتی باشند. مثلا اگر یک زبان متناهی منظم رو مثال بزنیم که فقط رشته aabb رو داره واسه این که جایگشتی باشه باید حداقل یه جایگشت aabb مثلا bbaa رو داشته باشه که اینظور نیست. واسه مستقل از متن هم میشه به همین صورت مثال زد/.
پس تا اینجا گزینه یک و چهار غلطه.
برای غلط بودن گزینه ۲ :
اگر زبان [tex](01)^{\ast}[/tex] رو به عنوان یه زبان منظم داشته باشیم، در صورتی جایگشتی میشه که برای هر رشته عضو زبان حداقل یه جایگشت اون نیز عضو زبان باشه مثلا برای رشته ۰۱ باید ۱۰ نیز عضو زبان باشه که دیگه منظم حساب نمیشه.
پس فقط گزینه سه می مونه یعنی هر زبان جایگشتی ، مستقل از متن است.