۰
subtitle
ارسال: #۱
سال ۹۰ مهندسی سوال ۶۲
(۰۸ اسفند ۱۳۸۹ ۱۰:۳۶ ق.ظ)mehrline نوشته شده توسط: اگه به سراغ کتاب لینز برین، در فصل ۴، توی یکی از تمرین‌ها، یه چیزی تو مایه های این رو داده. خوده لینز هم که من کتاب زبان اصلیشو خوندم، اینو حل کرده و ابتدای پاسخش میگه که " شاید تعجب کنید . ولی این CF هست". راه حلیم واسش داده. این یه استثنا بود که باید حفظش می کردی!!!
دومی وقتی منظمه، یعنی مستقل از متن هم هست
اگه دقت کرده باشی در کتاب لینز گفته که طول دو رشته برابر نباشه و درسته اون موقعه مستقل از متن است ولی من یادمه دکتر کارگهی همین سوالی که در کنکور آمده را حل کرده و گفت اگر طول دو رشته مساوی باشند اونموقعه مستقل ازمتن نیست
دلیلش هم این است که شما رشته اول را داخل پشته میریزید و زمانی که طول دو رشته برابر نباشه به راحتی با هر حرفی که از ورودی میخوانی یکی هم از پشته pop میکنی و مهم نیست که چی داری pop میکنی و زمانی که ورودی تمام شد نباید پشته خالی شده باشد آن وقت رشته پذیرفته میشه پس مستقل از متن است یا پشته خالی شده ولی رشته تمام نشده اون موقعه به یک حالتی میری که فقط رشته ورودی را مصرف کند و در آخر پذیرفته میشود
ولی زمانی که طول دو رشته برابر است شما رشته اول را در پشته قرار میدهید و ابتدای رشته به ته پشته میرود حالا شما باید چک بکنی که ابتدای رشته دوم آیا با ابتدای رشته اول یکسان است ؟ ولی این کار رانمیتونی بکنی چون که ابتدای رشته اول ته پشته میباشد پس نمیتونه مستقل ازمتن باشه
پس زبانش چی میشه ؟ من میگم حساس به متنه و راه حلم هم اینه
این زبان رشته های به طول زوج داره پس با کمک قواعد زبان های حساس به متن میانه رشته‌ها را بدست می آوریم سپس یک علامت میگذاریم مثلاً @ . حالا به ابتدای رشته میرویم و هر چی در ابتدا بود مثلاً a را تبدیل به x میکنیم و حرکت میکنیم تا به میانه برسیم سپس چک میکنیم ببینیم آیا در ابتدای میانه هم a داریم دوباره به ابتدای رشته میریم و حرف دوم را بررسی میکنیم مثلاً b است با y جایگزین میکنیم و بعد به میانه رشته میرویم و عناصری را که تا کنون چک کرده ایم پشت سر میگذاریم وسپس میبینیم آیا حرف بعدی در میانه b هست یا نه و این کار را تا آخر ادامه میدهیم تا نیمه اول به میانه برسد و در آخر این رشته را اگر در شرایط زبان صدق میکرد میپذیریم
--------------------------------------------------------------------------
در کل نظر من اینه که زبان L1 مستقل ازمتن نیست
و زبان L2 مستقل ازمتن میباشد
پس گزینه ۳ درست است
هر کی هر نظری داره بگه
fatemeh69، در تاریخ ۱۱ آبان ۱۳۹۳ ۰۳:۱۹ ق.ظ برای این مطلب یک پانوشت گذاشته است:
صورت سوال
۱
ارسال: #۲
بررسی سوال ۶۲ (نظریه زبان‌ها )
L1 مستقل از متن غیر قطعیه . تو کتاب لینز همین زبان با یه دونه c وسط دو تا رشته داده و تو حل تمرین اثبات شده که مستقل از متن قطعیه . کتاب پارسه هم همین رو گفته صفحه‌ی ۱۳۵ .
حالا تنها فرق این سوال و تنها نکته اش اینه که یه دونه c نداره که باعث غیر قطعی بودنش می شه .
حالا تنها فرق این سوال و تنها نکته اش اینه که یه دونه c نداره که باعث غیر قطعی بودنش می شه .
ارسال: #۳
RE: بررسی سوال ۶۲ (نظریه زبان‌ها )
(۰۸ اسفند ۱۳۸۹ ۱۲:۴۳ ب.ظ)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 قطعی است نه آن زبان مورد بحث ما.
۱
ارسال: #۴
RE: بررسی سوال ۶۲ (نظریه زبان‌ها )
همون طور که قبلا گفتم هر رشته ای عضو l2 است منظم است و مستقل از متن است.
برای مثال w=aaaaa میتوان گفت w1=lambda , w2=aaaaa است که عضو این زبان است .
[tex]n_{a}(w_{1})=0=n_{b}(w_{2})[/tex]
برای مثال 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 و چک میکنه.
والی آخر.
حتی اگر هم بخواهیم pda تعریف کنیم به صورت غیرقطعی یه باز w1 رو میگیره lambda بقیه اش w2 و چک میکنه.
یه باز w1= حرف اول و بقیه w2 و چک میکنه.
والی آخر.
۱
ارسال: #۶
بررسی سوال ۶۲ (نظریه زبان‌ها )
بله هر چی هر رشته ایی شما بگی عضو این زبانه
اصلا هر رشته ایی رو میشه جوری خوردش کرد که تعداد a وb اون یکی باشه پس pda ما آسون طراحی میشه و هر زبونی بهش بدی رو بدون بررسی میفرستش توی حالت final
اصلا هر رشته ایی رو میشه جوری خوردش کرد که تعداد a وb اون یکی باشه پس pda ما آسون طراحی میشه و هر زبونی بهش بدی رو بدون بررسی میفرستش توی حالت final
۱
ارسال: #۷
بررسی سوال ۶۲ (نظریه زبان‌ها )
دو حالت داره یا m>n یا m<=n
حالت اول
مثلا abbabb خوب w1=abba و w2=bb
حالت دوم
aabaab خوب w1=aa و w2=baab
حالت اول
مثلا abbabb خوب w1=abba و w2=bb
حالت دوم
aabaab خوب w1=aa و w2=baab
۱
ارسال: #۸
بررسی سوال ۶۲ (نظریه زبان‌ها )
دوستان پرسیدند که چرا برای ww نمیتونیم بگیم که wcw رو بگیم مستقل از متنه و بعد c رو برداریم !!
دوستان من گفتم اگر زبانی مستقل از متن قطعی باشه میشه از همریختی به این نتیجه رسید که زبان بدست اومده مستقل از متنه ولی WcW که مستقل از متن نیست چون ما وقتی c رو رد کردیم باید با کف استک چک کنیم که نمیشه!
--
اما این سوال l1 کنکور به خاطر اون مخالف بودن مستقل از متنه چون میشه گرامر واسش تعریف کرد مثلا اگه با حرف a شروع میشه وسطش با b شروع بشه اگه با b شروع میشه وسطش با a شروع بشه یه چیزی توی این مایه ها!!
دوستان من گفتم اگر زبانی مستقل از متن قطعی باشه میشه از همریختی به این نتیجه رسید که زبان بدست اومده مستقل از متنه ولی WcW که مستقل از متن نیست چون ما وقتی c رو رد کردیم باید با کف استک چک کنیم که نمیشه!
--
اما این سوال l1 کنکور به خاطر اون مخالف بودن مستقل از متنه چون میشه گرامر واسش تعریف کرد مثلا اگه با حرف a شروع میشه وسطش با b شروع بشه اگه با b شروع میشه وسطش با a شروع بشه یه چیزی توی این مایه ها!!
۱
ارسال: #۹
RE: بررسی سوال ۶۲ (نظریه زبان‌ها )
تمرین شماره ۲۳ عکس ضمیمه را نگاه کنید!
از کتاب Sipser است.
از کتاب Sipser است.
ارسال: #۱۰
RE: بررسی سوال ۶۲ (نظریه زبان‌ها )
(۱۲ اسفند ۱۳۸۹ ۰۲:۴۴ ب.ظ)۸۷۸۵۵۶۱۱ نوشته شده توسط: تمرین شماره ۲۳ عکس ضمیمه را نگاه کنید!
از کتاب Sipser است.
پس مشخص شد که L1 مستقل از متنه . دوستان به نظرم به جای اینکه تلاش کنید ثابت کنید که مستقل از متن نیست، سعی کنید ثابت کنید که هست . تمرین ۲۳ این کتاب که دوستمون فرمودند دقیقا همون زبانه .
حالا شیطون کتاب Sipser دیگه چه صیغه ایه ؟ من که تا حالا اسمشم نشنیدم.
۱
ارسال: #۱۱
بررسی سوال ۶۲ (نظریه زبان‌ها )
چه جالب یعنی چون مخالف باید باشن w1,w2 پس فقط کافیه
na(w1)#na(w2)
, nb(w1)#nb(w2 .....
پس این l1 , l2 یه جورایی شبیه هم بودند!
na(w1)#na(w2)
, nb(w1)#nb(w2 .....
پس این l1 , l2 یه جورایی شبیه هم بودند!
۰
ارسال: #۱۲
RE: بررسی سوال ۶۲ (نظریه زبان‌ها )
در رابطه با مستقل از متن غیرقطعی بودم L1 شکی نیست.
ممکنه L2 کمی جای بحث داشته باشه که او هم با یه NPDA قابل پیاده سازیست.
ممکنه L2 کمی جای بحث داشته باشه که او هم با یه NPDA قابل پیاده سازیست.
۰
ارسال: #۱۳
بررسی سوال ۶۲ (نظریه زبان‌ها )
در مورد ربان l1 که مستقل ار متن نیست
شروع میکنیم که یک pda بکشیم
حالا فرض کنیم از همون اول وسط رشته را با c جدا کردیم یعنیw1cw2
خوب حالا تا قبل از cها رو توی پشته میریزیم بعدش به c میرسیم و باید Pop کنیم همزمان که داریم pop میکنیم باید چک کنیم که اون ته پشته با که سمبل اول w1 با سمبل اول w2 یکی نباشه خودمون میدونیم که این کار ممکن نیست اما فرض میکنیم این کار رو هم به صورت غیر قطعی انجام بدیم و بتونیم بریم توی حالت final اما ما مطمئن نیسیم که بتونیم بریم حالت پایانی چرا؟؟چون قرار بود طول کلw2 را طول کل w1چک کنیم اما اگه وسط رشته باشیم از طرفی نامشاوی بودنش چک شده اما از طرفی طولش تا ته w2 چک نشده که میبینیم قادر نیستیم با پشته اینکار رو بکنیم
اگر بین دو تا شزط "یا" بود میشد CF اما الان ;مه "و" هست Contex sensitive هست
شروع میکنیم که یک pda بکشیم
حالا فرض کنیم از همون اول وسط رشته را با c جدا کردیم یعنیw1cw2
خوب حالا تا قبل از cها رو توی پشته میریزیم بعدش به c میرسیم و باید Pop کنیم همزمان که داریم pop میکنیم باید چک کنیم که اون ته پشته با که سمبل اول w1 با سمبل اول w2 یکی نباشه خودمون میدونیم که این کار ممکن نیست اما فرض میکنیم این کار رو هم به صورت غیر قطعی انجام بدیم و بتونیم بریم توی حالت final اما ما مطمئن نیسیم که بتونیم بریم حالت پایانی چرا؟؟چون قرار بود طول کلw2 را طول کل w1چک کنیم اما اگه وسط رشته باشیم از طرفی نامشاوی بودنش چک شده اما از طرفی طولش تا ته w2 چک نشده که میبینیم قادر نیستیم با پشته اینکار رو بکنیم
اگر بین دو تا شزط "یا" بود میشد CF اما الان ;مه "و" هست Contex sensitive هست
ارسال: #۱۴
RE: بررسی سوال ۶۲ (نظریه زبان‌ها )
(۰۸ اسفند ۱۳۸۹ ۰۶:۲۳ ب.ظ)hsh88 نوشته شده توسط: در مورد ربان l1 که مستقل ار متن نیستاگه اینجوریه پس سوال سال ۸۹(W1W2R به شرطی که W1 = W2R باشه و طول W1 با W2 هم برابر باشه)باید مستقل از متن نباشه.
شروع میکنیم که یک pda بکشیم
حالا فرض کنیم از همون اول وسط رشته را با c جدا کردیم یعنیw1cw2
خوب حالا تا قبل از cها رو توی پشته میریزیم بعدش به c میرسیم و باید Pop کنیم همزمان که داریم pop میکنیم باید چک کنیم که اون ته پشته با که سمبل اول w1 با سمبل اول w2 یکی نباشه خودمون میدونیم که این کار ممکن نیست اما فرض میکنیم این کار رو هم به صورت غیر قطعی انجام بدیم و بتونیم بریم توی حالت final اما ما مطمئن نیسیم که بتونیم بریم حالت پایانی چرا؟؟چون قرار بود طول کلw2 را طول کل w1چک کنیم اما اگه وسط رشته باشیم از طرفی نامشاوی بودنش چک شده اما از طرفی طولش تا ته w2 چک نشده که میبینیم قادر نیستیم با پشته اینکار رو بکنیم
اگر بین دو تا شزط "یا" بود میشد CF اما الان ;مه "و" هست Contex sensitive هست
۰
ارسال: #۱۵
بررسی سوال ۶۲ (نظریه زبان‌ها )
من از همه دوستان معذرت میخوام بچه‌ها من یک مقدار از نظر قبلی خودم برمیگردم و فکر کنیم که بشه وسط رشته را به صورت غیر قطعی تشخیص داد (که فکر کنم بتونیم این کار را بکنیم )ولی حالا بگید چه جوری دارید این زبان را میگید که مستقل از متن است ؟
لطفاً استدلالتون را جوری به کار ببرید که بعدش در مورد ww صدق نکنه . و لطفاً حل تمرین لینز را دوباره پیش نکشید (به نظر من این تمرین حتی کامل هم نیست و ابهام داره البته این نظر، نظر دکتر کارگهی هست نه من )
چرا که به نظر من سوال توی کنکور بیشتر به ww شباهت داره تا تمرین لینز و دو تا دلیل هم دارم
۱/ در ww طول ۲ تا رشته با هم مساوی است ولی در تمرین لینز همچین حرفی نیست
۲/ اگه شما میگید این سوال مستقل ازمتنه به نظرتون اگه تغییری در صورت سوال بدید و بگید که w1=w2 به نظر من که فرقی نمیکنه چون شما با علم به اینکه میدونید طول دو رشته مساوی است دارید تا مرحله آخر چک میکنید که w1 مساوی با w2 نیست مثلاً امکان داره که در کاراکتر آخر این دو رشته ،این نامساوی بودن برقرار باشه، پس حتما میتونید تشخیص بدهید که حتی کاراکترهای آخر این دو رشته با هم مساوی هستند پس با این اوصاف شما تونستید بگید که ww هم مستقل ازمتن است . پس تناقض داریم اینجا .
لطفاً اگر کسی نظری همچنان روی مستقل ازمتن بودن این زبان داره بنده را با سوالهای که در بالا پرسیدم قانع کنه ممنون
لطفاً استدلالتون را جوری به کار ببرید که بعدش در مورد ww صدق نکنه . و لطفاً حل تمرین لینز را دوباره پیش نکشید (به نظر من این تمرین حتی کامل هم نیست و ابهام داره البته این نظر، نظر دکتر کارگهی هست نه من )
چرا که به نظر من سوال توی کنکور بیشتر به ww شباهت داره تا تمرین لینز و دو تا دلیل هم دارم
۱/ در ww طول ۲ تا رشته با هم مساوی است ولی در تمرین لینز همچین حرفی نیست
۲/ اگه شما میگید این سوال مستقل ازمتنه به نظرتون اگه تغییری در صورت سوال بدید و بگید که w1=w2 به نظر من که فرقی نمیکنه چون شما با علم به اینکه میدونید طول دو رشته مساوی است دارید تا مرحله آخر چک میکنید که w1 مساوی با w2 نیست مثلاً امکان داره که در کاراکتر آخر این دو رشته ،این نامساوی بودن برقرار باشه، پس حتما میتونید تشخیص بدهید که حتی کاراکترهای آخر این دو رشته با هم مساوی هستند پس با این اوصاف شما تونستید بگید که ww هم مستقل ازمتن است . پس تناقض داریم اینجا .
لطفاً اگر کسی نظری همچنان روی مستقل ازمتن بودن این زبان داره بنده را با سوالهای که در بالا پرسیدم قانع کنه ممنون
۰
ارسال: #۱۶
بررسی سوال ۶۲ (نظریه زبان‌ها )
اصلا سر منظم بودنش بحث نکنید این که منظم نیست شما فقط به خاطر اینکه زوجه میگید منظمه اصلا به مفهومه زبان توجه کنید چون باید بررسی کنه که w1, w2 با هم مساوی نیستند حداقلش اینه که به حافظه ای برای اینکار نیاز داریم و این حافظه خطی است و زبان حساس به متنه
حالا میشه ۱۰۰۰ تا رشته مثال زد که در صورت مسئله صدق میکنه ولی dfa جواب نمیده baab
حالا میشه ۱۰۰۰ تا رشته مثال زد که در صورت مسئله صدق میکنه ولی dfa جواب نمیده baab
۰
ارسال: #۱۷
بررسی سوال ۶۲ (نظریه زبان‌ها )
فکر میکنم گرامر مستقل از متن این زبان شبیه همون گرامری هست که برای مثال کتاب لینز نوشته میشه، فقط به جای C از یک متغیر استفاده میکنیم که به لاندا میره.وسط رشته هم که به صورت غیر قطعی مشخص میشه.نظرتون چیه؟
۰
ارسال: #۱۸
بررسی سوال ۶۲ (نظریه زبان‌ها )
منم با آفاق موافقم این جوری نمیشه بگید یک زبان مستقل از متن نیست با محدود کردن صورت یک مسئله امکان داره که زبان نوعش عوض بشه .
به نظرم یک استدلالش اونی است که در صفحات قبل گفتم ولی بازم دنبال یک دلیل پر و پا قرص‌تر هستم . هر کس هر دلیلی داره بگه
به نظرم یک استدلالش اونی است که در صفحات قبل گفتم ولی بازم دنبال یک دلیل پر و پا قرص‌تر هستم . هر کس هر دلیلی داره بگه
۰
ارسال: #۱۹
RE: بررسی سوال ۶۲ (نظریه زبان‌ها )
متاسفانه گرامر زبان L1 مستقل از متن هست و گرامر اون هم یافت شده.
طراح سوال هم به احتمال قریب به یقین گرامر این زبان رو میدونسته که این سوال رو داده.
نظر من اینه که اگر اعتراض دارید گزینه "وقت کافی برای این سوال وجود نداشت" رو بزنید بلکه شاید سوال حذف شه.
طراح سوال هم به احتمال قریب به یقین گرامر این زبان رو میدونسته که این سوال رو داده.
نظر من اینه که اگر اعتراض دارید گزینه "وقت کافی برای این سوال وجود نداشت" رو بزنید بلکه شاید سوال حذف شه.
۰
ارسال: #۲۰
بررسی سوال ۶۲ (نظریه زبان‌ها )
۱ . رشته نمیتونه طولش نامتناهی باشه فرض میکنیم طول رشتمون مثلا K هستش
۲ . مییدونیم هررشته که LL(K باشه حتما مستقل از متن هست
۳ . در نتیجه ما منتونیم رشته اول رو به طور کامل تو پشته بریزیم و موقع ریختن رشته دوم به طور غیر قطعی میریم و اولین حرف رشته اول رو چک میکنیم . اگه با هم برابر بودند که رشته پذیرفته نمیشه اگه برابر نبودند سراغ دومین حرف میریمو.....
درنتیجه گزینه ۱ میشه (وسط رشته یعنی جایی که تشخیص میدیم که رشته دوم داره ریخته میشه بصورت غیر قطعی تشخیص داده میشه)
این نظر رو تو یه تایپیک دیگه مطرح کردم که دوستان به واسطه مقایسه با WW ردش کردن منم پذیرفتم چون علمم بیشتر نمیکشید
این طرز فکر و از استادی پرسیدم و گفتند که این فکر کاملا درسته
همه جملات گفته شده در بالا از کتاب لینز گفته شده
اگه حواستید صفحاتشو میگم
۲ . مییدونیم هررشته که LL(K باشه حتما مستقل از متن هست
۳ . در نتیجه ما منتونیم رشته اول رو به طور کامل تو پشته بریزیم و موقع ریختن رشته دوم به طور غیر قطعی میریم و اولین حرف رشته اول رو چک میکنیم . اگه با هم برابر بودند که رشته پذیرفته نمیشه اگه برابر نبودند سراغ دومین حرف میریمو.....
درنتیجه گزینه ۱ میشه (وسط رشته یعنی جایی که تشخیص میدیم که رشته دوم داره ریخته میشه بصورت غیر قطعی تشخیص داده میشه)
این نظر رو تو یه تایپیک دیگه مطرح کردم که دوستان به واسطه مقایسه با WW ردش کردن منم پذیرفتم چون علمم بیشتر نمیکشید
این طرز فکر و از استادی پرسیدم و گفتند که این فکر کاملا درسته
همه جملات گفته شده در بالا از کتاب لینز گفته شده
اگه حواستید صفحاتشو میگم
ارسال: #۲۱
RE: بررسی سوال ۶۲ (نظریه زبان‌ها )
(۱۱ اسفند ۱۳۸۹ ۰۹:۲۹ ب.ظ)saria نوشته شده توسط: 1 . رشته نمیتونه طولش نامتناهی باشه فرض میکنیم طول رشتمون مثلا K هستش
۲ . مییدونیم هررشته که LL(K باشه حتما مستقل از متن هست
۳ . در نتیجه ما منتونیم رشته اول رو به طور کامل تو پشته بریزیم و موقع ریختن رشته دوم به طور غیر قطعی میریم و اولین حرف رشته اول رو چک میکنیم . اگه با هم برابر بودند که رشته پذیرفته نمیشه اگه برابر نبودند سراغ دومین حرف میریمو.....
درنتیجه گزینه ۱ میشه (وسط رشته یعنی جایی که تشخیص میدیم که رشته دوم داره ریخته میشه بصورت غیر قطعی تشخیص داده میشه)
این نظر رو تو یه تایپیک دیگه مطرح کردم که دوستان به واسطه مقایسه با WW ردش کردن منم پذیرفتم چون علمم بیشتر نمیکشید
این طرز فکر و از استادی پرسیدم و گفتند که این فکر کاملا درسته
همه جملات گفته شده در بالا از کتاب لینز گفته شده
اگه حواستید صفحاتشو میگم
بنظر من قانع کننده بود.مرسی
ارسال: #۲۲
RE: بررسی سوال ۶۲ (نظریه زبان‌ها )
(۱۱ اسفند ۱۳۸۹ ۰۹:۲۹ ب.ظ)saria نوشته شده توسط: 1 . رشته نمیتونه طولش نامتناهی باشه فرض میکنیم طول رشتمون مثلا K هستش
۲ . مییدونیم هررشته که LL(K باشه حتما مستقل از متن هست
۳ . در نتیجه ما منتونیم رشته اول رو به طور کامل تو پشته بریزیم و موقع ریختن رشته دوم به طور غیر قطعی میریم و اولین حرف رشته اول رو چک میکنیم . اگه با هم برابر بودند که رشته پذیرفته نمیشه اگه برابر نبودند سراغ دومین حرف میریمو.....
درنتیجه گزینه ۱ میشه (وسط رشته یعنی جایی که تشخیص میدیم که رشته دوم داره ریخته میشه بصورت غیر قطعی تشخیص داده میشه)
این نظر رو تو یه تایپیک دیگه مطرح کردم که دوستان به واسطه مقایسه با WW ردش کردن منم پذیرفتم چون علمم بیشتر نمیکشید
این طرز فکر و از استادی پرسیدم و گفتند که این فکر کاملا درسته
همه جملات گفته شده در بالا از کتاب لینز گفته شده
اگه حواستید صفحاتشو میگم
ببخشید ولی من ۲تا مشکل با قسمت سوم دارم ممنون میشم اگه توضیح بدید:
۱) اگه حرف اول برابر باشه رشته پذیرفته نمی شه؟ این که یه حرف تو ۲تا قسمت اول و دوم رشته برابر باشه دلیل بر این نمیشه که کل ۲ قسمت رشته برابر باشن
۲) رشته‌ی اول رو که در پشته بریزیم حرف اولش در انتهای پشته قرار میگیره و نه در بالای اون شما چه جوری اولین حرف اون رشته رو چک می کنید؟ به نظر کاملا غلط میاد
*البته به نظر من سنجش اشتباه نکرده ولی این اثبات هم درست به نظر نمی رسه
۰
ارسال: #۲۳
بررسی سوال ۶۲ (نظریه زبان‌ها )
توی جزوه نظریه طرح ۹۰ درصد امسال توی جدول آخر نوشته این زبان مستقل از متن نیست!صفحه ۵۴
تالیغف حاج سید جوادی بوده! اما دلیلشو ننوشته اگر کسی ایمیل حاج سید جوادی را داره ایمیل بزنه!
تالیغف حاج سید جوادی بوده! اما دلیلشو ننوشته اگر کسی ایمیل حاج سید جوادی را داره ایمیل بزنه!
۰
ارسال: #۲۴
بررسی سوال ۶۲ (نظریه زبان‌ها )
نه فرق دارند مثل abba، مثل اینکه مستقل از متن در اومد البته فعلاً . ممنون از دوستان
بچه‌ها من واقعاً موندم چرا ww پس مستقل از متن در نظر گرفته نمیشه ؟؟؟؟؟ کسی میدونه ؟؟؟؟
بچه‌ها من واقعاً موندم چرا ww پس مستقل از متن در نظر گرفته نمیشه ؟؟؟؟؟ کسی میدونه ؟؟؟؟
۰
ارسال: #۲۵
بررسی سوال ۶۲ (نظریه زبان‌ها )
ببینید اگه ww باشه مثلا من میگم همون abba خوب؟ این الان تعداد a,b های دو قسمت یکیه ولی ww نیست پس نمیشه از یکی بودن به جایی رسید اما وقتی یکی نباشه حتما ww نیست چون اگه ww باشه حتما یکی است.
یعنی نمیشه که دو طرف مساوی باشن ولی تعداد نمادها یکی نباشه! پس اگه تعداد نمادها یکی نبود حتما یکی نیستن!
اما میشه یکی نباشن ولی تعداد نمادها یکی باشه.پس از برابری نمادها نمیشه نتیجه ای گرفت.
من که نگفتم l1,l2 یکی هستند گفتم شبیه اند منظورم این بود که هردو روی تعداد سمبل‌ها کار میکنند.
یعنی نمیشه که دو طرف مساوی باشن ولی تعداد نمادها یکی نباشه! پس اگه تعداد نمادها یکی نبود حتما یکی نیستن!
اما میشه یکی نباشن ولی تعداد نمادها یکی باشه.پس از برابری نمادها نمیشه نتیجه ای گرفت.
من که نگفتم l1,l2 یکی هستند گفتم شبیه اند منظورم این بود که هردو روی تعداد سمبل‌ها کار میکنند.
۰
ارسال: #۲۶
RE: بررسی سوال ۶۲ (نظریه زبان‌ها )
با NoOne موافقم . به نظرم طراح نظریه امسال، هم کتاب پارسه( دکتر نورالله )و هم جزوه ۹۰ %( حاج سید جوادی )رو دیده بوده و متوجه این اشتباهشون( البته اشتباهاتشون، چون به نظرم بازم ایراد هست )شده بوده و خواسته با این تست این نکته رو به اونها گوشزد کنه . البته نباید منکر زحمات این دو عزیز شد ولی به هر حال باید دقت بیشتری داشته باشند تا بچه‌ها تو تله های اینچنینی نیفتند. البته خوشبختانه من نیفتادم و سر کنکور با یه استدلال ساده گزینه یک رو زدم . اگه کتاب پارسه ملکه ذهنم بود قطعا اشتباه می زدم. سعی کردم تحلیل کنم ولی انصافا پیدا کردن گرامر واسه این زبان اونم سرکنکور غیرممکنه مگه قبلا جایی دیده باشی .
در مورد کتاب مذکور هم موافقم که بچه های سال بعد این کتاب رو یه منبع مهم واسه درس نظریه بدونند، واسه راحتی شون من لینک دانلود این کتاب رو که ۲۰ مگابایته تو همین پست می ذارم، البته جاش تو آرشیو پیوندهاست ولی خوب اینجا هم خیلی بی ربط نیست .
در مورد کتاب مذکور هم موافقم که بچه های سال بعد این کتاب رو یه منبع مهم واسه درس نظریه بدونند، واسه راحتی شون من لینک دانلود این کتاب رو که ۲۰ مگابایته تو همین پست می ذارم، البته جاش تو آرشیو پیوندهاست ولی خوب اینجا هم خیلی بی ربط نیست .
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
۰
ارسال: #۲۷
بررسی سوال ۶۲ (نظریه زبان‌ها )
اعتماد به نفس ندارم منم که گفتم به احتمال خیلی زیاد مستقل از متنه (طبق شواهدی که دوستان داشتند)
آخه میدونی چیه من یکم محافظه کارم و یکم به جواب سوالات به خصوص نظریه بدبین .(همیشه امکان این وجود داره که جواب یک چیزه دیگه باشه که شما فکرش نمیکنید )
و دلیل آخرم اینکه سید جوادی، دکتر کارگهی کم کسانی نیستند، آخه همه اینها متفقل قول میگن این زبان مستقل از متن نیست نکنه یک نکته داره که کسی به اون دقت نکرده
ثانیا من هنوز سر ww قانع نشدم . مگه pda یا npda برای این زبان نداریم و اگه دو رشته ای که کاراکترهای آخر یکسانی ندارند جز این زبان است و توسط این زبان پذیرفته میشه درسته ؟! پس چرا نمیتونه ww را تشخیص بده، اصلا حرفهای بالام را بیخیال همین سوال منو جواب بدید.خیلی تو قانع شدنم کمک میکنه (حقیقت آفاق خانم نظر شما را متوجه نشدم یکم واضحتر توضیح میدید)
آخه میدونی چیه من یکم محافظه کارم و یکم به جواب سوالات به خصوص نظریه بدبین .(همیشه امکان این وجود داره که جواب یک چیزه دیگه باشه که شما فکرش نمیکنید )
و دلیل آخرم اینکه سید جوادی، دکتر کارگهی کم کسانی نیستند، آخه همه اینها متفقل قول میگن این زبان مستقل از متن نیست نکنه یک نکته داره که کسی به اون دقت نکرده
ثانیا من هنوز سر ww قانع نشدم . مگه pda یا npda برای این زبان نداریم و اگه دو رشته ای که کاراکترهای آخر یکسانی ندارند جز این زبان است و توسط این زبان پذیرفته میشه درسته ؟! پس چرا نمیتونه ww را تشخیص بده، اصلا حرفهای بالام را بیخیال همین سوال منو جواب بدید.خیلی تو قانع شدنم کمک میکنه (حقیقت آفاق خانم نظر شما را متوجه نشدم یکم واضحتر توضیح میدید)
ارسال: #۲۸
RE: بررسی سوال ۶۲ (نظریه زبان‌ها )
(۱۲ اسفند ۱۳۸۹ ۰۷:۲۸ ب.ظ)hatami84 نوشته شده توسط: اعتماد به نفس ندارم منم که گفتم به احتمال خیلی زیاد مستقل از متنه (طبق شواهدی که دوستان داشتند)
آخه میدونی چیه من یکم محافظه کارم و یکم به جواب سوالات به خصوص نظریه بدبین .(همیشه امکان این وجود داره که جواب یک چیزه دیگه باشه که شما فکرش نمیکنید )
و دلیل آخرم اینکه سید جوادی، دکتر کارگهی کم کسانی نیستند، آخه همه اینها متفقل قول میگن این زبان مستقل از متن نیست نکنه یک نکته داره که کسی به اون دقت نکرده
ثانیا من هنوز سر ww قانع نشدم . مگه pda یا npda برای این زبان نداریم و اگه دو رشته ای که کاراکترهای آخر یکسانی ندارند جز این زبان است و توسط این زبان پذیرفته میشه درسته ؟! پس چرا نمیتونه ww را تشخیص بده، اصلا حرفهای بالام را بیخیال همین سوال منو جواب بدید.خیلی تو قانع شدنم کمک میکنه (حقیقت آفاق خانم نظر شما را متوجه نشدم یکم واضحتر توضیح میدید)
چیزی که من از حرف شما متوجه شدم اینه که میگید اگه wawb جزو این زبانه و توسط این زبان پذیرفته میشه پس چرا ww رو نمی پذیره؟ اگه اشتباه می کنم لطف کنید و ۲ باره و دقیقتر سوال رو مطرح کنید و اگه سوال رو درست متوجه شدم خب دلیلش اینه که در واقع این گرامر فقط تمرکزش روی اون ۲ تا کاراکتری که قراره متفاوت باشند هستش یعنی بقیه، هم می تونن مساوی باشن هم می تونن نباشن. برای این مثال شما هم گرامر اصلا حواسش به این نیست که رشته های شما wa و wb هستن و حتی اگه [tex]wa[/tex] و [tex]w'b[/tex] هم بودن بازم می پذیرفت.
نمی دونم تونستم منظورم رو برسونم یا نه؟
۰
ارسال: #۲۹
بررسی سوال ۶۲ (نظریه زبان‌ها )
نه بحث سر کاراکترهای آخر نیست!!
چیزی که من برداشت کردم اینه که میاد تعداد a های w1 رو میشمره تعداد b هاش رو هم همینطور حالا اگه تعداد a های w1 با تعداد a های w2 یکی نبود یا تعداد b هاشون یکی نبود یعنی w1#w2 است.
اما اگه بخوایم بگیم w1=w2 مساوی بودن تعداد نمادها کمکی نمیکنه چون توی abba تعداد نمادهای دو قسمت یکیه ولی خودشون یکی نیستن.
چیزی که من برداشت کردم اینه که میاد تعداد a های w1 رو میشمره تعداد b هاش رو هم همینطور حالا اگه تعداد a های w1 با تعداد a های w2 یکی نبود یا تعداد b هاشون یکی نبود یعنی w1#w2 است.
اما اگه بخوایم بگیم w1=w2 مساوی بودن تعداد نمادها کمکی نمیکنه چون توی abba تعداد نمادهای دو قسمت یکیه ولی خودشون یکی نیستن.
۰
ارسال: #۳۰
بررسی سوال ۶۲ (نظریه زبان‌ها )
من یکم دیر اومدم و مثل اینکه دارین نتیجه گیری میکنید! بچه‌ها لطفا نظر من رو هم بررسی کنید
اثبات درستی گزینه ۳ به این صورت هست:
در مورد l2 بحثی نیست و هر رشته ای رو بگی تعداد a و b در اون مساویست پس هر رشته ای رو میپذیره و خب منظم میشه.
و اما l1 این زبون قطعا آزاد نیست . فرض کنید شرط w1=w2 بود که سوال (طول هم که یکسان هست!) میشد l1={ww} که آزاد نیست. دوستان هیج فرقی نداره، اگر نتونیم با پشته چک کنیم که برابرند خب نمیتونیمم چک کنیم که برابر نیستند .
ما باید هر دو رشته رو از ابتداشون حرف به حرف چک کنیم و اگه حداقل یک اختلاف پیدا شد یا اگر طولشون یکسان نبود بگیم برابر نیستند و ما بعد از قرار دادن w1 در پشته به ابتداش واسه مقایسه با w2 دسترسی نداریم.
در ضمن برابری طول هم تفاوتی ایجاد نمیکنه.
اثبات درستی گزینه ۳ به این صورت هست:
در مورد l2 بحثی نیست و هر رشته ای رو بگی تعداد a و b در اون مساویست پس هر رشته ای رو میپذیره و خب منظم میشه.
و اما l1 این زبون قطعا آزاد نیست . فرض کنید شرط w1=w2 بود که سوال (طول هم که یکسان هست!) میشد l1={ww} که آزاد نیست. دوستان هیج فرقی نداره، اگر نتونیم با پشته چک کنیم که برابرند خب نمیتونیمم چک کنیم که برابر نیستند .
ما باید هر دو رشته رو از ابتداشون حرف به حرف چک کنیم و اگه حداقل یک اختلاف پیدا شد یا اگر طولشون یکسان نبود بگیم برابر نیستند و ما بعد از قرار دادن w1 در پشته به ابتداش واسه مقایسه با w2 دسترسی نداریم.
در ضمن برابری طول هم تفاوتی ایجاد نمیکنه.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close