صفحه‌ها: ۱ ۲
[tex]L={uww^{R}v:u,v,w\in {a,b}^{ }}[/tex]
این زبان چرا منظمه؟
من متوجه نمیشم!!
پیتر لینز صفحه ۱۱۶ سوال ۱۹
u و v و w عضو {a,b}+ هستند
این زبان به خاطر اینکه قبل وبعد از wها حتما یه الفبا میاد منظم میشه اگه این الفبا می تونست لاندا باشه اون موقع دیگه منظم نبود.
میتونید W=a یا w=b بگیرید کلیه رشته هایی که شامل aa یا bb هستند چون جزو حالت گفته شده در بالا میشوند عضو این زبان هستند.
البته اگه nfa بکشید باید ۵ وضعیت بگذارید چون رشته های ما حداقل طولشان ۴ است.
مثلا aabbab که w=b ،u=aa, v=ab
عضو این زبان است.
یا baab
اینایی که گفتین درست. اما چرا وقتی الفبا بشه (a,b)* اونوقت دیگه منظم نیست؟؟ آیا نمی تونیم در این حالت، حالت شروع رو پذیرش بگیریم؟؟؟
(۱۰ بهمن ۱۳۸۹ ۰۷:۳۴ ب.ظ)zr2358 نوشته شده توسط: [tex]L={uww^{R}v:u,v,w\in {a,b}^{ }}[/tex]
این زبان چرا منظمه؟
من متوجه نمیشم!!
پیتر لینز صفحه ۱۱۶ سوال ۱۹
u و v و w عضو {a,b}+ هستند
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
ارسال ۴۲ به بعد رو بخونید اگر مبهم بود بگید.
نه در هر صورت منظمه
ممنون از جواب های همتون
پس با این حساب هر دو زبان چه استار و چه پلاس منظمه
یعنی وقتی یه رشته رو داریم، خودمون می تونیم u و v و w رو جوری درنظر بگیریم که گرامر منظم بتونه اونو تولید کنه و کاری به این نداریم که واقعا اینا چی بودن.
مثل همون abba که سپیدجان گفتند. با اینکه ممکنه اینجا منظور این باشه که u و v لاندا باشند و w، ab باشه ولی ما اونو اینجوری تغییر می دیم تا گرامر منظم بتونه تولیدش کنه. (u و v را a درنظر میگیریم و w را b)
درست گفتم؟ منظورتون همین بود دیگه؟
آره ببینید وقتی به ما میگن گرامر این رشته رو بپذیره یعنی یه رشته که به ما میدن دست بالا بگیریم و ببینیم که این رشته توی این گرامر هست یا نه! یعنی اگه فقط به ازای یک W,u,v خاص تونستیم که بگیم این رشته عضو زبان هست خوب دیگه حله!
یعنی اگه یه رشته رو گفتیم توی زبان نیست هیچ جوره نشه گفت که نه، عضو این زبانه !
مثلا من وقتی میگم رشته باید شامل aa , bb باشه و قبل و بعد این aa یا bb هم حداقل یک حرف داشته باشیم
یعنی وقتی رشته abab رو بهش میدم هیچ جوره نشه توی این زبان جاش داد و واقعا هم نمیشه!
اگه u و v بتونن مقدار لاندا رو بپذیرن در این حالت رشته با توجه به لم تزریق دیگه منظم نیست پس فقط در حا لتی منظمه که uوv پلاس باشن نه استار
ببین دوست عزیز این سوالا رو سعی کن واسش dfaبکشی
الان ایتجا wwR دو حالت محدود داره یا aaیا bb و بقیه رشته کا سمت چپ و راست این دوتا رشته هستند را v,w حساب میکنیم
پس الان به راحتی میشهdfaکشید پس منظمه اگه متوجه نشدی بگو تا dfaاش رو بکشم
هر کسی یه چیزی میگه و دلیل میاره همشونم به نظر میرسه درست باشند ولی متناقضند
آقای دکتر شما نمی تونید کمکمون کنید و نظرتون رو بگید؟
در مورد منظم بودن این گرامر که اینجا این همه بحث کردیم !!!!!!!!
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
آخه دکتر کارگهی را چه به اینجاها!! منظورم دکتر تنهایی بود.
کسی هست که به حرف خودش اطمینان صد در صد داشته باشه؟
ببینید علوم کامپیوتر ۸۵ یه سوال اومده که گفته کدام گزینه صحیح است توی یکی از گزینه‌ها این گرامر رو آورده و گفته منظم نیست اما گزینه صحیح یک گزینه دیگه هست پس یعنی این گرامر منظمه. میتونید تست رو توی هر کتابی که دارید پیدا کنید شاید کتاب من گزینه اشتباه رو انتخاب کرده.(البته اونجا الفبای زبان ۰و۱ است ولی فرقی ندارد)
عبارت منظم این زبان هم *(a+b) است.
شما یه رشته به من بدین که من نتونم u,w,v رو جوری انتخاب کنم که اون رشته عضو این زبان بشه اونوقت حرف شما قبول!!
حتی اگه رشته لاندا رو هم بدین میشه u=w=v=lambda که در این حالت حالت شروع همون حالت پایانیه دقیقا مثل dfa زبان *(a+b)
این زبان منظمه و دلیلش هم اینه که میتونیم w رو برابر یه رشته مثل لامبدا و یا یه حرف بگیریم. با توجه به وجود u و v هر ترکیبی رو میشه به راحتی با یه dfa ساده چک کرد که آیا عضو زبان هست یا نه. اگه w رو برابر لامبدا بگیریم که همه رشتهها رو شامل میشه و یک dfa داریم که یه حالت داره که پایانیه و به خودش برمیگرده( با رشتههای a و b )اگر هم w رو برابر یه زیر رشته محدود بگیریم با یه حالت آغازی که هر چیزی رو تولید میکنه و چند تا حالت که زیر رشته w و معکوسش رو تولید میکنه به یک حالت نهایی میرویم که با هر رشتهای به خودش بر میگرده. بنابراین تحت هر شرایطی میشه یه dfa برای این زبان ترسیم کرد.
سوال: آیا اگه u یا v وجود نداشت هنوز هم زبان منظم بود؟