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

سلام بچه ها خسته نباشید.توی جزوه دکتر کارگاهی صفحه 6 نوشته در بعضی زبان ها L*=L.میشه این جمله رو توضیح بدید که توی چه حالت هایی L*=L هست و تو چه حالت هایی نیست و فرق L* رو با *∑ هم توضیح بدید ممنون میشم

سلام. وقت بخیر. زبانی به این شکل رو نمیشه به سادگی تعریف کرد. بستار ستاره به معنی اجتماع زبان به ازای تمام توانهاست. سیکمااستار به معنی تمام رشته های روی الفباست. مثلاً روی الفبای [tex]\{a,b\}[/tex] داریم [tex]{\sum}^*=\{\lambda,a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,bab,...\}[/tex]. درنظر بگیرید [tex]L=\{aab\}[/tex] داریم [tex]L^*=\{\lambda,aab,aabaab,aabaabaab,...\}[/tex].

[tex]L^{\ast}[/tex] در واقع مجموعه ی زیر است:
[tex]L^{\ast}=L^0\cup L\cup L^2\cup L^3\cup...[/tex]
حالا [tex]L^0و\: L^2وL^3و...[/tex] چی هستند
[tex]L^2[/tex] یعنی ما بیایم به انتهای رشتهای زبان تک تک رشته های زبان را الحاق کنیم یعنی مثلا اگر زبان ما {a,ab} باشد ما باید یک باربه انتهای رشته ی a، خود a را بیفزاییم یک باز هم به انتخایش ab را بیفزاییم
و نیز همین کار را برای ab انجام دهیم یعنی یک بار یه انتهای آن a بیفزاییم یک بازر ab پس با این زبانی که ما مثال زدیم [tex]L^2[/tex]آ ن می شود{aa,aab,aba,abab} .
خب برای بدست آوردن [tex]L^3[/tex] کافی است همین روند را یک بار دیگر انجام دهیم مثلا [tex]L^3[/tex] زبانی که مثال زده ایم می شود:
{aaa,aaab,aaba,aabab,abaa,abaab,ababa,ababab}
پس [tex]L^2[/tex] یعنی زبان L را دو بار به هم ملحق کنیم [tex]L^3[/tex] یعنی سه بار ملحق کنیم و...
حالا [tex]L^0[/tex] یعنی چه یعنی هیچ بار رشته های L را به هم ملحق نکنیم که می شود [tex]L^0=\{\lambda\}[/tex]
خب برای این که بررسی کنیم آیا در یک زبانی [tex]L^{\ast}=L[/tex] هست یا نه باید دو مورد را بررسی کنیم:
آیا [tex]L\subseteq L^{\ast}[/tex] است؟
آیا [tex]L^{\ast}\subseteq L^{ }[/tex]ست؟
خب مورد اول که واضح است چون [tex]L^{\ast}=L\cup....[/tex]پس رابطه اول برقرار است (در مورد هر زبانی)
و در مورد هر زبانی فقط کافیست رابطه دوم را چک کنیم .
واضح است که اگر زبان متناهی باشد هیچ گاه رابطه دوم صادق نیست
اما رابطه دوم تنها در مورد بعضی زبان های نامتناهی صادق است (اگر زبانی لامبدا نداشته باشد رابطه دوم برقرار نیست)
پس در وحله اول باید لامبدا عضو زبان باشد از این به بعد فرض می کنبم لامبدا عضو زبان هست:
و برای این که برقرار بودن رابطه دوم را چک کنیم یک راه میان بر هست
به جای این که چک کنیم که آیا [tex]L^{\ast}\subseteq L.[/tex] چک کنیم که آیا [tex]L^2\subseteq L.[/tex] است یا نه
خب واضح است که اگر [tex]L^2\subseteq L.[/tex]باشد به این معنا است ه اگر من به تک تک رشت های زبانم یک بار دیگر رشته های زبان را الحاق کنم از زبان بیرون نمی افتند و دوباره داخل زبانند پس اگر یک بار دیگر یا صد بار دیگر هم همین کار را بکنم باز هم داخل زبانند پس اگر لامبدا عضو زبانی باشد و [tex]L^2\subseteq L.[/tex] باشد می توان نتیجه گرفت که د آن زبان [tex]L^{\ast}=L.[/tex] است.

مرسی بسیار ممنونم