قول میدم این سوال آخری باشه که امروز میپرسم.
این زبان به نظر خودم منظم نیست. نظر دوستان چیه؟
[tex]uww^{R}v : u,v,w\in \left \{ a,b \right \}^{ }[/tex]
فکر کنم مشکل من با اون + باشه و نتونستم درست متوجه بشم.
(۰۷ مهر ۱۳۹۲ ۰۸:۴۶ ب.ظ)zimenswall نوشته شده توسط: قول میدم این سوال آخری باشه که امروز میپرسم.
این زبان به نظر خودم منظم نیست. نظر دوستان چیه؟
[tex]uww^{R}v : u,v,w\in \left \{ a,b \right \}^{ }[/tex]
فکر کنم مشکل من با اون + باشه و نتونستم درست متوجه بشم.
در یکی دو تا تاپیک سوالای مشابه این بحث شده؛
مثلا یه راه ساده اینه که اول اون قسمت wwr رو بزارید کنار؛ چیزی که باقی میمونه u در اول و v در آخر هر کدوم به تنهایی قادر سیگما پلاس رو تولید کنن؛ بنابراین الحاق اونها هم میشه سیگما پلاس؛ بزرگترین مجموعه ای که میشه با حروف الفبای یه زبان ساخت سیگما استاره؛ از طرفی سیگما پلاس فقط یه لاندا از سیگما استار کمتر داره؛ حالا وقتی اون قسمت wwr رو اضافه بکنید، از اونجایی که w نمیتونه لاندا باشه، زبان حاصل بزرگتر از همون سیگما پلاس نخواهد بود (سیگما پلاس هم که منظمه)؛
(۰۷ مهر ۱۳۹۲ ۱۰:۴۷ ب.ظ)Ghiasoddin نوشته شده توسط:(07 مهر ۱۳۹۲ ۰۸:۴۶ ب.ظ)zimenswall نوشته شده توسط: قول میدم این سوال آخری باشه که امروز میپرسم.
این زبان به نظر خودم منظم نیست. نظر دوستان چیه؟
[tex]uww^{R}v : u,v,w\in \left \{ a,b \right \}^{ }[/tex]
فکر کنم مشکل من با اون + باشه و نتونستم درست متوجه بشم.
در یکی دو تا تاپیک سوالای مشابه این بحث شده؛
مثلا یه راه ساده اینه که اول اون قسمت wwr رو بزارید کنار؛ چیزی که باقی میمونه u در اول و v در آخر هر کدوم به تنهایی قادر سیگما پلاس رو تولید کنن؛ بنابراین الحاق اونها هم میشه سیگما پلاس؛ بزرگترین مجموعه ای که میشه با حروف الفبای یه زبان ساخت سیگما استاره؛ از طرفی سیگما پلاس فقط یه لاندا از سیگما استار کمتر داره؛ حالا وقتی اون قسمت wwr رو اضافه بکنید، از اونجایی که w نمیتونه لاندا باشه، زبان حاصل بزرگتر از همون سیگما پلاس نخواهد بود (سیگما پلاس هم که منظمه)؛
تشکر
اول اینکه تو انجمن سخت میشه اینجور سوالها رو پیدا کرد چون معمولا تیتر سوالها مبین خود سوال نیست و اگه تکراری بود شرمنده
دوم اینکه اینطور که شما میگید کاربرد سیگما پلاس در اثبات منظم بودن زبانها مثل سیگما استار هست. یعنی اگه تونستیم اثبات کنیم که یه زبانی سیگما استار یا سیگما پلاس بشه پس منظمه.
(۰۸ مهر ۱۳۹۲ ۰۱:۴۳ ق.ظ)afshin18 نوشته شده توسط: به نظر من منظم نیست چون که احتیاج به حافظه داره وقتی w بیاد پشتش wrیعنی ما باید جایی(استک) رو برای ذخیره ی w داشته باشیم اگه منظم هست من نمی دونم چرا توضیحات رو هم نفهمیدم
افشین عزیز، هرچند W و عکسش پشت هم اومده و باید حافظه برای تولیدش داشت اما به دلیل اینکه زبان بالا همون سیگما پلاسه احتیاجی به حافظه نداره چون سیگما پلاس منظمه و احتیاجی به حافظه نیست.
توی همین انجمن قبلا من ۵ سوال در مورد منظم بودن ۵ زبان پرسیدم که خیلی خیلی مباحث استدلالی زیبایی توسط دوستان گفته شد.
اگه اونا رو مطالعه کنی به راحتی میتونی مفهوم جمله ای که در بالا گفتم رو بفهمی و البته خیلی راحت میتونی سوالات مربوط به منظم بودن و نامنظم بودن و حتی مستقل از متن را حل کنی.
(۰۸ مهر ۱۳۹۲ ۱۲:۰۶ ق.ظ)zimenswall نوشته شده توسط: یعنی اگه تونستیم اثبات کنیم که یه زبانی سیگما استار یا سیگما پلاس بشه پس منظمه.
همینطوره (:
(۰۷ مهر ۱۳۹۲ ۱۰:۴۷ ب.ظ)Ghiasoddin نوشته شده توسط:(07 مهر ۱۳۹۲ ۰۸:۴۶ ب.ظ)zimenswall نوشته شده توسط: [tex]uww^{R}v : u,v,w\in \left \{ a,b \right \}^{ }[/tex]
مثلا یه راه ساده اینه که اول اون قسمت wwr رو بزارید کنار؛
یه شبهه ای برام پیش اومده، اینکه آیا ما میتونیم ww^R را کنار بذاریم و به این نتیجه برسیم که سیگما پلاسه؟
آخه طول w نمیتونه صفر باشه و کنار گذاشتنش به نظرم منطقی نمیاد
فکر کنم راه حل اشتباهی بود چون این زبان سیگما پلاس نیست
چون اگه سیگما پلاس باشه باید بتونه رشته abab را بسازه در صورتی که اینجور نیست
بلکه این یه زبانیه که حتما باید وسطش یه چیز قرینه بیاد و اول آخرش دیگه مهم نیست چی باشه
مثلا فرض که w=Sa (برای Sb هم به همین شکل اثبات میشه) و [tex]w^{R}[/tex] هم میشه aS. که S هر ترکیبی از a,b هست.
پس رشته ما به شکل زیر در میاد
[tex]uSaaSv[/tex]
پس زبان به شکل زیر در میاد که
[tex](a b)^{ } (a b)^{*} aa (a b)^{*} (a b)^{ }[/tex]
و در نتیجه میشه به شکل زیر با استفاده از این قانون که [tex]\sum^{*}.\sum^{ }=\sum^{ }[/tex]
[tex](a b)^{ } aa (a b)^{ }[/tex]
خب این زبان هم مشخصه که منظمه . یعنی اول و آخرش هر چی خواست بیاد، فقط وسطش حتما یکی از حالتهای aa یا bb اومده باشه
پس ما به اشتباه نتیجه گرفتیم که زبان بالا میشه سیگما پلاس
(۰۸ مهر ۱۳۹۲ ۰۳:۱۱ ب.ظ)zimenswall نوشته شده توسط: پس زبان به شکل زیر در میاد که
[tex](a b)^{ } (a b)^{*} aa (a b)^{*} (a b)^{ }[/tex]
و در نتیجه میشه به شکل زیر با استفاده از این قانون که [tex]\sum^{*}.\sum^{ }=\sum^{ }[/tex]
[tex](a b)^{ } aa (a b)^{ }[/tex]
بله درست میگید، پاسخ خودتون کاملتره:
[tex](a b)^{ } (aa bb) (a b)^{ }[/tex]
(۰۸ مهر ۱۳۹۲ ۰۵:۳۳ ب.ظ)Ghiasoddin نوشته شده توسط:(08 مهر ۱۳۹۲ ۰۳:۱۱ ب.ظ)zimenswall نوشته شده توسط: پس زبان به شکل زیر در میاد که
[tex](a b)^{ } (a b)^{*} aa (a b)^{*} (a b)^{ }[/tex]
و در نتیجه میشه به شکل زیر با استفاده از این قانون که [tex]\sum^{*}.\sum^{ }=\sum^{ }[/tex]
[tex](a b)^{ } aa (a b)^{ }[/tex]
بله درست میگید، پاسخ خودتون کاملتره:
[tex](a b)^{ } (aa bb) (a b)^{ }[/tex]
ممنون از شما که در بحث شرکت کردید.
باز هم مثل اون چندتا سوال قبلی که پرسیده بودم زیادی ذهنم به سیگما بودن زبان متوجه میشد و اینبار هم همینطور شد.
در کل هرچند سیگما شدن زبان یکی از راههای خوب واسه تشخیص نوع زبان هست ولی امثال من که دقت کافی ندارن باید دقتشون را بالا ببرن که سوال را اشتباه حل نکنند