تالار گفتمان مانشت

سلام.بچه ها میشه جواب این سوالو توضیح بدید!!دلایل رد گزینه ها و اثبات گزینه درست!!!
ممنون

(17 دى 1393 07:03 ب.ظ)miladcr7 نوشته شده توسط: [ -> ]سلام.بچه ها میشه جواب این سوالو توضیح بدید!!دلایل رد گزینه ها و اثبات گزینه درست!!!
ممنون

گزینه 3 میشه؟ درسته؟

اره گزینه 3 درسته

(17 دى 1393 08:33 ب.ظ)miladcr7 نوشته شده توسط: [ -> ]اره گزینه ۳ درسته

سلام یادم رفت بکنم
سلام
ببین برای اینکه یکم با اطمینان جواب بدیم میشه یه مثال نقض ساده بزنیم که گزینه ۲ و۴ میپره.
مثال نقض:
[tex]L1\: =\: \phi\: ,\: L2=\: \phi\: ,\: L3=\{a\}[/tex]

اما برای اثباتش:

[tex]L1\: =\: L2\: \cup\: L3L1 --> L3L1\subseteq\: L1,\: L2\subseteq L1 --> L3L3L1\subseteq L1\: ,\: L2\subseteq L1\: ...L1=L3^{\ast}L2[/tex]

ببخشید
[tex]L_1=L_2\cup L_3[/tex] از کجا اومد؟؟

(17 دى 1393 09:25 ب.ظ)miladcr7 نوشته شده توسط: [ -> ]ببخشید
[tex]L_1=L_2\cup L_3[/tex] از کجا اومد؟؟

میبخشید سوتی بود همون صورت سوال منظورم بود.

(17 دى 1393 09:31 ب.ظ)Imankhani نوشته شده توسط: [ -> ]

(17 دى 1393 09:25 ب.ظ)miladcr7 نوشته شده توسط: [ -> ]ببخشید
[tex]L_1=L_2\cup L_3[/tex] از کجا اومد؟؟

میبخشید سوتی بود همون صورت سوال منظورم بود.

میشه لطف کنید فرمولش رو درست کنید این حزوف اضافه اذیت میکنه

اینطوری من توضیح میدهم شاید راحتتر باشه البته پاسخ ایشون کاملا درسته
توی سوال گفته چی
[tex]L1 =\: L2\: \cup\: L3L1[/tex]

خوب وقتی الحاق L3 با L1 اجتماعش با L2 برابر L1 شده پس یعنی L3 , L2 هر دوشون زیر مجموعه L1 هستن دیگه
([tex]if\: a\subseteq\: b\: \: \longleftrightarrow\: a\: \cup\: b\: =\: b[/tex])
طبق این قضیه ریاضی که همه قبولش داریم
خوب پس داریم
[tex]L3L1\: \subseteq\: L1\: \: And\: \: \: L2\: \subseteq\: L1[/tex]

خوب وقتی الحاق L3 در L1 تاثیری نداشته چه یک بار چه هزار بار با L1 الحاق بشه تاثیری نداره خوب میشه نتیجه گرفته
[tex]L3^{\ast}L1\: \subseteq\: L1\: [/tex]
[tex]L2\: \subseteq\: L1\: [/tex]

حالا میشه نتیجه گرفت
L1 = L3*L2

پیشنهاد می کنم قبل از خواندن این جواب ، این تاپیک رو مطالعه کنید.

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

وقتی می گه [tex]L_1=L_2\cup L_3L_1[/tex] مثل این می مونه که بگه:
[tex]L_1->L_2|L_3L_1[/tex]
حالا اگه این گرامرو یه کم پیش ببریم می رسیم به این:
[tex]L_1->L_3L_1->L_3L_3L_1->L_3L_3L_3L_1->...->L_3^{\ast}L_1->L_3^{\ast}L_2[/tex]
پس واضحه که [tex]L_3^{\ast}L_2[/tex] تو این معادله صدق می کنه و گزینه های دیگه غلط هستند
اما اگه فرم این سوال مثل همون سوال علوم ۸۷ بود و دوتا گزینه داشت که یکی می گفت این تتنها جواب معادله است و یه گزینه دیگه می گفت به ازای هر c متناهی یه جواب به فرم [tex]L_3^{\ast}(L_2\cup C)[/tex] داره اونوقت باید کدوم گزینه رو بزنیم
به عبارت دیگر آیا این تنها جواب مسئله است ؟
پس اگر فرض کنیم:
[tex]L_1=L_3^{\ast}(L_2\cup C)[/tex]
واضحه که اگه از [tex]L_3^{\ast}[/tex] رشته لاندا رو در نظر بگیریم [tex]L_2\subseteq L_1[/tex]
اما چون [tex]\lambda\notin L_3[/tex] پس [tex]L_3^ \subseteq L_3^{\ast}[/tex]
پس:
[tex]L_3L_1=L_3L_3^{\ast}(L_2\cup C)=L_3^ (L_2\cup C)\subseteq L_1[/tex] (دقت کنید که آخرین علامت مساوی نیست)
پس:
[tex]L_3L_1\subseteq L_1[/tex] و [tex]L_2\subseteq L_1[/tex]
پس:
[tex]L_2UL_3L_1\subseteq L_1[/tex]
پس L1 نمی تواند به فرم [tex]L_3^{\ast}(L_2\cup C)[/tex] (که C هر زبان متناهی است) باشد
پس [tex]L_1=L_3^{\ast}L_2[/tex] تنها جواب این معادله است

دقت کنید که تفاوت این مسئله و با اون
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
یکی در اینه که اون زبانی که داره تکرار می شه و استار می گیره (منظوم B یا L3 اس) در اون جا در سمت راست بود این جا در سمت چپ است
و نکته ی مهم تر این که در اون جا لاندا عضو B بود پس معادله چندین جواب داشت اما در این جا لاندا عضو L3 نیست پس معادله تنها یک جواب داره