سلام.بچه ها میشه این سوال رو برام توضیح بدید ممنون میشم.
فرض کنید [tex]A=\{0\}[/tex] و [tex]B=\{\lambda,1,10\}[/tex] دو زبان در [tex]\{0,1\}^{\ast}[/tex] باشند.در مورد معادله ی [tex]X=A\cup XB[/tex] برای زبان مجهول [tex]X\subseteq\{0,1\}^{\ast}[/tex] کدام گزاره صحیح است؟
۱- [tex]X=AB^{\ast}[/tex] تنها جواب یکتای این معادله است
۲- [tex]X=B^{\ast}A[/tex] تنها جواب یکتای این معادله است
۳- فقط برای هر زبان متناهی [tex]C\subseteq\{0,1\}^{\ast}[/tex]، [tex]X=B^{\ast}(A\cap C)[/tex] یک جواب معادله است
۴- برای هر زبان [tex]C\subseteq\{0,1\}^{\ast}[/tex] ، [tex]X=(A\cup C)B^{\ast}[/tex] یک جواب معادله است
وقتی می گه [tex]X=A\cup XB[/tex] مثل این می مونه که بگه:
[tex]X->A|XB[/tex]
حالا اگه این گرامرو یه کم پیش ببریم می رسیم به این:
[tex]X->XB->XBB->XBBB->...\: ->XB*-->AB*[/tex]
و واضحه که *AB تو این معادله صدق می کنه و گزینه دو و سه غلط هستند اما یه سوال پیش میاد آیا این تنها جواب مسئله است ؟
اگه گزینه ۴ درست باشه اونوقت *AB هم درسته پس گزینه ۴ حکم کلی تری رو اثبات می کنه.
مثلا به این مثال دقت کنید
[tex]C=\{1\}[/tex]
پس:
[tex]X=\{A\cup C\}B^{\ast}[/tex]
[tex]X=(0 1)B^{\ast}[/tex]
واضحه که اگه از*B رشته لاندا رو در نظر بگیریم[tex]A\subseteq X[/tex]
و از طرفی چون [tex]\lambda\in B[/tex] پس [tex]B^ =B^{\ast}[/tex]
[tex]XB=\{A\cup C\}B^{\ast}B=\{A\cup C\}B^ =\{A\cup C\}B^{\ast}=X[/tex]
پس:
[tex]XB=X[/tex] و [tex]A\subseteq X[/tex]
پس:
[tex]AUXB=X[/tex]
پس گزینه ۴ درسته
و دقت کنید که چون به ازای هر C متناهی [tex]X=\{A\cup C\}B^{\ast}[/tex] یک جواب معادله اس پس تعداد جواب های این معادله برابر است با تعداد مجموعه های متناهی C و چون C می تواند هر زیر مجموعه ی متناهی ای از سیگما استار باشد و سیگما استار نامتناهی تا عضو دارد پس تعداد C های متناهی ش هم نامتنهای تاست (به عنوان مثال زیر مجموعه های تک عضوی سیگما استار نامتناهی تا هستند)
پس این معادله نامتناهی تا جواب دارد