(۰۸ اسفند ۱۳۸۹ ۱۰:۳۶ ق.ظ)mehrline نوشته شده توسط: اگه به سراغ کتاب لینز برین، در فصل ۴، توی یکی از تمرینها، یه چیزی تو مایه های این رو داده. خوده لینز هم که من کتاب زبان اصلیشو خوندم، اینو حل کرده و ابتدای پاسخش میگه که " شاید تعجب کنید . ولی این CF هست". راه حلیم واسش داده. این یه استثنا بود که باید حفظش می کردی!!!
دومی وقتی منظمه، یعنی مستقل از متن هم هست
اگه دقت کرده باشی در کتاب لینز گفته که طول دو رشته برابر نباشه و درسته اون موقعه مستقل از متن است ولی من یادمه دکتر کارگهی همین سوالی که در کنکور آمده را حل کرده و گفت اگر طول دو رشته مساوی باشند اونموقعه مستقل ازمتن نیست
دلیلش هم این است که شما رشته اول را داخل پشته میریزید و زمانی که طول دو رشته برابر نباشه به راحتی با هر حرفی که از ورودی میخوانی یکی هم از پشته pop میکنی و مهم نیست که چی داری pop میکنی و زمانی که ورودی تمام شد نباید پشته خالی شده باشد آن وقت رشته پذیرفته میشه پس مستقل از متن است یا پشته خالی شده ولی رشته تمام نشده اون موقعه به یک حالتی میری که فقط رشته ورودی را مصرف کند و در آخر پذیرفته میشود
ولی زمانی که طول دو رشته برابر است شما رشته اول را در پشته قرار میدهید و ابتدای رشته به ته پشته میرود حالا شما باید چک بکنی که ابتدای رشته دوم آیا با ابتدای رشته اول یکسان است ؟ ولی این کار رانمیتونی بکنی چون که ابتدای رشته اول ته پشته میباشد پس نمیتونه مستقل ازمتن باشه
پس زبانش چی میشه ؟ من میگم حساس به متنه و راه حلم هم اینه
این زبان رشته های به طول زوج داره پس با کمک قواعد زبان های حساس به متن میانه رشتهها را بدست می آوریم سپس یک علامت میگذاریم مثلاً @ . حالا به ابتدای رشته میرویم و هر چی در ابتدا بود مثلاً a را تبدیل به x میکنیم و حرکت میکنیم تا به میانه برسیم سپس چک میکنیم ببینیم آیا در ابتدای میانه هم a داریم دوباره به ابتدای رشته میریم و حرف دوم را بررسی میکنیم مثلاً b است با y جایگزین میکنیم و بعد به میانه رشته میرویم و عناصری را که تا کنون چک کرده ایم پشت سر میگذاریم وسپس میبینیم آیا حرف بعدی در میانه b هست یا نه و این کار را تا آخر ادامه میدهیم تا نیمه اول به میانه برسد و در آخر این رشته را اگر در شرایط زبان صدق میکرد میپذیریم
--------------------------------------------------------------------------
در کل نظر من اینه که زبان L1 مستقل ازمتن نیست
و زبان L2 مستقل ازمتن میباشد
پس گزینه ۳ درست است
هر کی هر نظری داره بگه
L1 مستقل از متن غیر قطعیه . تو کتاب لینز همین زبان با یه دونه c وسط دو تا رشته داده و تو حل تمرین اثبات شده که مستقل از متن قطعیه . کتاب پارسه هم همین رو گفته صفحهی ۱۳۵ .
حالا تنها فرق این سوال و تنها نکته اش اینه که یه دونه c نداره که باعث غیر قطعی بودنش می شه .
(۰۸ اسفند ۱۳۸۹ ۱۲:۴۳ ب.ظ)parsaNA نوشته شده توسط: L1 مستقل از متن غیر قطعیه . تو کتاب لینز همین زبان با یه دونه c وسط دو تا رشته داده و تو حل تمرین اثبات شده که مستقل از متن قطعیه . کتاب پارسه هم همین رو گفته صفحهی ۱۳۵ .
حالا تنها فرق این سوال و تنها نکته اش اینه که یه دونه c نداره که باعث غیر قطعی بودنش می شه .
صفحه ۳۹۴ قسمتsolution کتاب پیتر لینز(لاتین) تمرین ۱۰ بخش ۸/۱:
Perhaps surprisingly, this language is context-free. Construct an npda that counts to some value K by putting K tokens on the stack, and remembers the Kth symbol. It then examines the Kth symbol in W2.
If this does not match the remembered symbol, the string is accepted.
The npda chooses the K nondeterministically.
عین جملات را آوردم.
صورت سوال: L=W1cW2:W1<>W2
[/align]
(۰۸ اسفند ۱۳۸۹ ۱۲:۴۳ ب.ظ)parsaNA نوشته شده توسط: L1 مستقل از متن غیر قطعیه . تو کتاب لینز همین زبان با یه دونه c وسط دو تا رشته داده و تو حل تمرین اثبات شده که مستقل از متن قطعیه . کتاب پارسه هم همین رو گفته صفحهی ۱۳۵ .
حالا تنها فرق این سوال و تنها نکته اش اینه که یه دونه c نداره که باعث غیر قطعی بودنش می شه .
راستی یک چیزی یادم رفت بگم:
صفحه ۱۳۵ پارسه گفته که: W1<>W2^r قطعی است نه آن زبان مورد بحث ما.
در رابطه با مستقل از متن غیرقطعی بودم L1 شکی نیست.
ممکنه L2 کمی جای بحث داشته باشه که او هم با یه NPDA قابل پیاده سازیست.
همون طور که قبلا گفتم هر رشته ای عضو l2 است منظم است و مستقل از متن است.
برای مثال w=aaaaa میتوان گفت w1=lambda , w2=aaaaa است که عضو این زبان است .
[tex]n_{a}(w_{1})=0=n_{b}(w_{2})[/tex]
ببینید l2 همه رشتهها رو میپذیره پس دیگه نیازی نیست که واسش pda تعریف کنیم.
حتی اگر هم بخواهیم pda تعریف کنیم به صورت غیرقطعی یه باز w1 رو میگیره lambda بقیه اش w2 و چک میکنه.
یه باز w1= حرف اول و بقیه w2 و چک میکنه.
والی آخر.
بله هر چی هر رشته ایی شما بگی عضو این زبانه
اصلا هر رشته ایی رو میشه جوری خوردش کرد که تعداد a وb اون یکی باشه پس pda ما آسون طراحی میشه و هر زبونی بهش بدی رو بدون بررسی میفرستش توی حالت final
دو حالت داره یا m>n یا m<=n
حالت اول
مثلا abbabb خوب w1=abba و w2=bb
حالت دوم
aabaab خوب w1=aa و w2=baab
در مورد ربان l1 که مستقل ار متن نیست
شروع میکنیم که یک pda بکشیم
حالا فرض کنیم از همون اول وسط رشته را با c جدا کردیم یعنیw1cw2
خوب حالا تا قبل از cها رو توی پشته میریزیم بعدش به c میرسیم و باید Pop کنیم همزمان که داریم pop میکنیم باید چک کنیم که اون ته پشته با که سمبل اول w1 با سمبل اول w2 یکی نباشه خودمون میدونیم که این کار ممکن نیست اما فرض میکنیم این کار رو هم به صورت غیر قطعی انجام بدیم و بتونیم بریم توی حالت final اما ما مطمئن نیسیم که بتونیم بریم حالت پایانی چرا؟؟چون قرار بود طول کلw2 را طول کل w1چک کنیم اما اگه وسط رشته باشیم از طرفی نامشاوی بودنش چک شده اما از طرفی طولش تا ته w2 چک نشده که میبینیم قادر نیستیم با پشته اینکار رو بکنیم
اگر بین دو تا شزط "یا" بود میشد CF اما الان ;مه "و" هست Contex sensitive هست
(۰۸ اسفند ۱۳۸۹ ۱۰:۴۶ ب.ظ)shahryar نوشته شده توسط:آره دقیقا میشه از خاصیت همریختی استفاده کرد اول یه c اضافه گذاشت که مستقل از متنه و چون زبانهای مستقل از متن تحت همریختی بسته اند میشه h(c=lambda بگیریم و همون زبان l1 بدست میاد و مستقل از متنه.(08 اسفند ۱۳۸۹ ۱۰:۴۰ ب.ظ)afagh1389 نوشته شده توسط: این که چرا سنجش گفته l1 مستقل از متنه نظری ندارم ولی این که میگین وسط رشته رو نمیشه پیدا کرد.دقیقا همین طوره.
همونطور که توی WWR میتونستیم به طور غیر قطعی وسط رشته رو پیدا کنیم اینجا هم میتونیم.
موقعی که وسط رشته پیدا شد می شه مثل W1cW2 که w1 با w2 بربر نیست.این زبان هم طبق نظر لینز مستقل از متنه.
(۰۸ اسفند ۱۳۸۹ ۰۶:۲۳ ب.ظ)hsh88 نوشته شده توسط: در مورد ربان l1 که مستقل ار متن نیستاگه اینجوریه پس سوال سال ۸۹(W1W2R به شرطی که W1 = W2R باشه و طول W1 با W2 هم برابر باشه)باید مستقل از متن نباشه.
شروع میکنیم که یک pda بکشیم
حالا فرض کنیم از همون اول وسط رشته را با c جدا کردیم یعنیw1cw2
خوب حالا تا قبل از cها رو توی پشته میریزیم بعدش به c میرسیم و باید Pop کنیم همزمان که داریم pop میکنیم باید چک کنیم که اون ته پشته با که سمبل اول w1 با سمبل اول w2 یکی نباشه خودمون میدونیم که این کار ممکن نیست اما فرض میکنیم این کار رو هم به صورت غیر قطعی انجام بدیم و بتونیم بریم توی حالت final اما ما مطمئن نیسیم که بتونیم بریم حالت پایانی چرا؟؟چون قرار بود طول کلw2 را طول کل w1چک کنیم اما اگه وسط رشته باشیم از طرفی نامشاوی بودنش چک شده اما از طرفی طولش تا ته w2 چک نشده که میبینیم قادر نیستیم با پشته اینکار رو بکنیم
اگر بین دو تا شزط "یا" بود میشد CF اما الان ;مه "و" هست Contex sensitive هست
(۰۸ اسفند ۱۳۸۹ ۱۰:۵۰ ب.ظ)afagh1389 نوشته شده توسط:(08 اسفند ۱۳۸۹ ۱۰:۴۶ ب.ظ)shahryar نوشته شده توسط:آره دقیقا میشه از خاصیت همریختی استفاده کرد اول یه c اضافه گذاشت که مستقل از متنه و چون زبانهای مستقل از متن تحت همریختی بسته اند میشه h(c=lambda بگیریم و همون زبان l1 بدست میاد و مستقل از متنه.(08 اسفند ۱۳۸۹ ۱۰:۴۰ ب.ظ)afagh1389 نوشته شده توسط: این که چرا سنجش گفته l1 مستقل از متنه نظری ندارم ولی این که میگین وسط رشته رو نمیشه پیدا کرد.دقیقا همین طوره.
همونطور که توی WWR میتونستیم به طور غیر قطعی وسط رشته رو پیدا کنیم اینجا هم میتونیم.
موقعی که وسط رشته پیدا شد می شه مثل W1cW2 که w1 با w2 بربر نیست.این زبان هم طبق نظر لینز مستقل از متنه.
اصلا" خوشکل فکر نمیکنید!
(۰۹ اسفند ۱۳۸۹ ۱۲:۲۷ ق.ظ)۸۷۸۵۵۶۱۱ نوشته شده توسط:من این حرفی که زدم از خودم نزدم یادمه وقتی استادمون WcwR رو گفت مستقل از متن قطعی است و WWR گفت میتونیم از خاصیت بسته بودن زبانهای مستقل از متن نسبت به همریختی استفاده کنید و h(c=lambda بگذارید اینجوری میشه نتیجه گرفت که مستقل از متنه ولی در مورد قطعی بودن چون زبانهای مستقل از متن قطعی تحت همریختی بسته نیستند نمیشه نتیجه ای گرفت.(08 اسفند ۱۳۸۹ ۱۰:۵۰ ب.ظ)afagh1389 نوشته شده توسط:(08 اسفند ۱۳۸۹ ۱۰:۴۶ ب.ظ)shahryar نوشته شده توسط:آره دقیقا میشه از خاصیت همریختی استفاده کرد اول یه c اضافه گذاشت که مستقل از متنه و چون زبانهای مستقل از متن تحت همریختی بسته اند میشه h(c=lambda بگیریم و همون زبان l1 بدست میاد و مستقل از متنه.(08 اسفند ۱۳۸۹ ۱۰:۴۰ ب.ظ)afagh1389 نوشته شده توسط: این که چرا سنجش گفته l1 مستقل از متنه نظری ندارم ولی این که میگین وسط رشته رو نمیشه پیدا کرد.دقیقا همین طوره.
همونطور که توی WWR میتونستیم به طور غیر قطعی وسط رشته رو پیدا کنیم اینجا هم میتونیم.
موقعی که وسط رشته پیدا شد می شه مثل W1cW2 که w1 با w2 بربر نیست.این زبان هم طبق نظر لینز مستقل از متنه.
اصلا" خوشکل فکر نمیکنید!
حالا اگه حرف من به کام شما (و اونهایی که حرف شما رو تایید کردن )خوش نمیاد میتونید دلیل بیارید که حرف من اشتباهه.
در ضمن من اگر حرفی میزنم قصد ناراحت کردن کسی رو ندارم پس لطفا شما هم جوری جواب ندید که من ناراحت بشم. با تشکر
من از همه دوستان معذرت میخوام بچهها من یک مقدار از نظر قبلی خودم برمیگردم و فکر کنیم که بشه وسط رشته را به صورت غیر قطعی تشخیص داد (که فکر کنم بتونیم این کار را بکنیم )ولی حالا بگید چه جوری دارید این زبان را میگید که مستقل از متن است ؟
لطفاً استدلالتون را جوری به کار ببرید که بعدش در مورد ww صدق نکنه . و لطفاً حل تمرین لینز را دوباره پیش نکشید (به نظر من این تمرین حتی کامل هم نیست و ابهام داره البته این نظر، نظر دکتر کارگهی هست نه من )
چرا که به نظر من سوال توی کنکور بیشتر به ww شباهت داره تا تمرین لینز و دو تا دلیل هم دارم
۱/ در ww طول ۲ تا رشته با هم مساوی است ولی در تمرین لینز همچین حرفی نیست
۲/ اگه شما میگید این سوال مستقل ازمتنه به نظرتون اگه تغییری در صورت سوال بدید و بگید که w1=w2 به نظر من که فرقی نمیکنه چون شما با علم به اینکه میدونید طول دو رشته مساوی است دارید تا مرحله آخر چک میکنید که w1 مساوی با w2 نیست مثلاً امکان داره که در کاراکتر آخر این دو رشته ،این نامساوی بودن برقرار باشه، پس حتما میتونید تشخیص بدهید که حتی کاراکترهای آخر این دو رشته با هم مساوی هستند پس با این اوصاف شما تونستید بگید که ww هم مستقل ازمتن است . پس تناقض داریم اینجا .
لطفاً اگر کسی نظری همچنان روی مستقل ازمتن بودن این زبان داره بنده را با سوالهای که در بالا پرسیدم قانع کنه ممنون
دوستان پرسیدند که چرا برای ww نمیتونیم بگیم که wcw رو بگیم مستقل از متنه و بعد c رو برداریم !!
دوستان من گفتم اگر زبانی مستقل از متن قطعی باشه میشه از همریختی به این نتیجه رسید که زبان بدست اومده مستقل از متنه ولی WcW که مستقل از متن نیست چون ما وقتی c رو رد کردیم باید با کف استک چک کنیم که نمیشه!
--
اما این سوال l1 کنکور به خاطر اون مخالف بودن مستقل از متنه چون میشه گرامر واسش تعریف کرد مثلا اگه با حرف a شروع میشه وسطش با b شروع بشه اگه با b شروع میشه وسطش با a شروع بشه یه چیزی توی این مایه ها!!