[
تعداد a, b مساوی چه ربطی به این سوال داره ؟ اصلاً قضیه اش با این سوال فرق داره
ربطش اینه که این مثال شما هم تعداد a و b هاش برابره
(۰۹ اسفند ۱۳۸۹ ۰۱:۲۶ ق.ظ)hsh88 نوشته شده توسط: قشنگ اون کسی فکر میکنه که توی رفتارشم قشنگ برخورد کنه آفاق خانم شما هم خیلی علم به همه آموختوندی هم خیلی وقت گذاشتیما بلد نیستیم گرامر بنویسیم.شما با لم تزریق ردش کن.
اینی که با یه c از شر لامبدا خلاص میشی بهتره از اینکه یه سری هزار تا c به صورت غیر قطعی پیدا میکنند
من دنبال لم تزریقم
l1 را رد کنم
اونایی هم که ادعا دارند CFهست یه گرامر یا pdaبسازند
دیگه باید مدرک بیاریم
(۰۹ اسفند ۱۳۸۹ ۰۱:۲۹ ق.ظ)shahryar نوشته شده توسط: [
تعداد a, b مساوی چه ربطی به این سوال داره ؟ اصلاً قضیه اش با این سوال فرق داره
ربطش اینه که این مثال شما هم تعداد a و b هاش برابره
بله ولی دقت کن اینجا ما ترتیب داریم اول m تا a داریم بعد باید m تا b بیاد و بعد m-1 حرف a و به همین صورت تا اونجایی که سواد من اجازه میده این با اون عبارتی که فکر کنم در ذهن شماست فرق داره اون میگفت w به طوری که تعداد aها و bها برابر باشه
ضمناٌ شما هنوز اون سوال بالای من را جواب ندادید ؟ لطفاٌ اگه نظری دارید روی اون سوال بگید شاید واقعاٌ من دارم اشتباه میکنم
اصلا میشه مثال را به گونه ای بزنی که تعداد a,bها مساوی نباشه اینا فقط مثاله
من فقط میخوام با مساوی در آوردن a,b کارم را در لم تزریق راحت کنم
اصلا سر منظم بودنش بحث نکنید این که منظم نیست شما فقط به خاطر اینکه زوجه میگید منظمه اصلا به مفهومه زبان توجه کنید چون باید بررسی کنه که w1, w2 با هم مساوی نیستند حداقلش اینه که به حافظه ای برای اینکار نیاز داریم و این حافظه خطی است و زبان حساس به متنه
حالا میشه ۱۰۰۰ تا رشته مثال زد که در صورت مسئله صدق میکنه ولی dfa جواب نمیده baab
فکر میکنم گرامر مستقل از متن این زبان شبیه همون گرامری هست که برای مثال کتاب لینز نوشته میشه، فقط به جای C از یک متغیر استفاده میکنیم که به لاندا میره.وسط رشته هم که به صورت غیر قطعی مشخص میشه.نظرتون چیه؟
(۰۹ اسفند ۱۳۸۹ ۰۷:۱۵ ب.ظ)hatami84 نوشته شده توسط: نظر من اینه که پست های قبلی را بخونید
من خوندم همه رو!قرار بود اونایی که میگن مستقل از متنه گرامر واسش پیدا کنن که یکم سخته.شما گرامر مثال رو میدونید چیه؟!
با سلام
اعتراض به کلید سازمان سنجش-گروه مهندسی کامپیوتر کد ۱۲۷۷-سوال ۶۲ درس نظریه زبان ها
مثال نقض برای اثبات مستقل از متن نبودن زبان L1:
رشته زیر عضو زبان L1 می باشد
[tex]L =\{ a^{2n}b^{2n}a^{2n} \}[/tex]
طول رشته زوج است و W1<>W2 می باشد(منطبق با صورت مساله)
رشته بالا مستقل از متن نمی باشد: چون در ابتدا حروف a را وارد پشته می کنیم(push) و بعد به همان تعداد حرف b از پشته می خوانیم(pop)، حال نوبت حروف a در انتهای رشته می باشد که چون تعداد a برای چک شدن با b از پشته خارج شده اند، دیگر به متغیر n دسترسی نداریم و نمی توانیم تعداد a های آخر رشته را بررسی کنیم. یعنی دیگر نمیدانیم در ابتدای رشته چه تعداد حرف a آمده است.(پس این زبان مستقل از متن نیست-بکمک یک پشته قابل تشخیص نیست)
توجه: زبان L در بالا به کمک لم پامپینگ(Pumping Lemmas) نیز قابل اثبات است که مستقل از متن نمی باشد.
پس زبان L1 در صورت سوال، باید بتواند زبان L(توضیح داده شده در بالا) را تشخیص دهد، و از آنجا که این زبان مستقل از متن نمی باشد(حساس به متن است)، پس زبان L1 هم نمی تواند مستقل از متن باشد.
گزینه ۳ صحیح می باشد(به اشتباه گزینه ۱ انتخاب شده است)
(۰۹ اسفند ۱۳۸۹ ۰۸:۱۰ ب.ظ)۸۷۸۵۵۶۱۱ نوشته شده توسط: فکر کنم یک مثال نقض برای اثبات مستقل از متن نبودن L1 این باشه:
[tex]L =\{ a^{n}b^{n}a^{n} \}[/tex]
توجه: طول رشته زوج است و W1<>W2 می باشد(منطبق با مساله ما)
خوب، میدونیم این یک زبان حساس به متن هست و باید توسط L1 پذیرفته شود که این امری غیر ممکن است.
درست گفتم؟
من اگه بگم [tex]a^{n}b^{n} \epsilon (a,b)^{*}[/tex]
چون یه زبان مستقل از متنه منظم بودن [tex](a,b)^{*}[/tex] رو نقض میکنه؟!!
منم با آفاق موافقم این جوری نمیشه بگید یک زبان مستقل از متن نیست با محدود کردن صورت یک مسئله امکان داره که زبان نوعش عوض بشه .
به نظرم یک استدلالش اونی است که در صفحات قبل گفتم ولی بازم دنبال یک دلیل پر و پا قرصتر هستم . هر کس هر دلیلی داره بگه
متاسفانه گرامر زبان L1 مستقل از متن هست و گرامر اون هم یافت شده.
طراح سوال هم به احتمال قریب به یقین گرامر این زبان رو میدونسته که این سوال رو داده.
نظر من اینه که اگر اعتراض دارید گزینه "وقت کافی برای این سوال وجود نداشت" رو بزنید بلکه شاید سوال حذف شه.
اعتراض به کلید سازمان سنجش-گروه مهندسی کامپیوتر کد ۱۲۷۷-سوال ۶۲ درس نظریه زبان ها
مثال نقض برای اثبات مستقل از متن نبودن زبان L1:
رشته زیر عضو زبان L1 می باشد
[tex]L =\{ a^{2n}b^{2n}a^{2n} \}[/tex]
طول رشته زوج است و W1<>W2 می باشد(منطبق با صورت مساله)
رشته بالا مستقل از متن نمی باشد: چون در ابتدا حروف a را وارد پشته می کنیم(push) و بعد به همان تعداد حرف b از پشته می خوانیم(pop)، حال نوبت حروف a در انتهای رشته می باشد که چون تعداد a برای چک شدن با b از پشته خارج شده اند، دیگر به متغیر n دسترسی نداریم و نمی توانیم تعداد a های آخر رشته را بررسی کنیم. یعنی دیگر نمیدانیم در ابتدای رشته چه تعداد حرف a آمده است.(پس این زبان مستقل از متن نیست-بکمک یک پشته قابل تشخیص نیست)
توجه: زبان L در بالا به کمک لم پامپینگ(Pumping Lemmas) نیز قابل اثبات است که مستقل از متن نمی باشد.
پس زبان L1 در صورت سوال، باید بتواند زبان L(توضیح داده شده در بالا) را تشخیص دهد، و از آنجا که این زبان مستقل از متن نمی باشد(حساس به متن است)، پس زبان L1 هم نمی تواند مستقل از متن باشد.
گزینه ۳ صحیح می باشد(به اشتباه گزینه ۱ انتخاب شده است)
(۱۱ اسفند ۱۳۸۹ ۰۵:۱۰ ب.ظ)۸۷۸۵۵۶۱۱ نوشته شده توسط: اعتراض به کلید سازمان سنجش-گروه مهندسی کامپیوتر کد ۱۲۷۷-سوال ۶۲ درس نظریه زبان هااین چیزی که شما می گی مثال نقض نیست.
مثال نقض برای اثبات مستقل از متن نبودن زبان L1:
رشته زیر عضو زبان L1 می باشد
[tex]L =\{ a^{2n}b^{2n}a^{2n} \}[/tex]
طول رشته زوج است و W1<>W2 می باشد(منطبق با صورت مساله)
رشته بالا مستقل از متن نمی باشد: چون در ابتدا حروف a را وارد پشته می کنیم(push) و بعد به همان تعداد حرف b از پشته می خوانیم(pop)، حال نوبت حروف a در انتهای رشته می باشد که چون تعداد a برای چک شدن با b از پشته خارج شده اند، دیگر به متغیر n دسترسی نداریم و نمی توانیم تعداد a های آخر رشته را بررسی کنیم. یعنی دیگر نمیدانیم در ابتدای رشته چه تعداد حرف a آمده است.(پس این زبان مستقل از متن نیست-بکمک یک پشته قابل تشخیص نیست)
توجه: زبان L در بالا به کمک لم پامپینگ(Pumping Lemmas) نیز قابل اثبات است که مستقل از متن نمی باشد.
پس زبان L1 در صورت سوال، باید بتواند زبان L(توضیح داده شده در بالا) را تشخیص دهد، و از آنجا که این زبان مستقل از متن نمی باشد(حساس به متن است)، پس زبان L1 هم نمی تواند مستقل از متن باشد.
گزینه ۳ صحیح می باشد(به اشتباه گزینه ۱ انتخاب شده است)
مثلا برای زبان [tex]L={n_{a}(w) = n_{b}(w)}[/tex] [tex]a^{n} b^{n}a ^{n} b^{n}[/tex]
زیر مجموعه ای از زبان اولیه است ولی مستقل از متن نیست.در صورتی که زبان اول مستقل از متن است.
(۱۱ اسفند ۱۳۸۹ ۰۵:۱۰ ب.ظ)۸۷۸۵۵۶۱۱ نوشته شده توسط: مثال نقض برای اثبات مستقل از متن نبودن زبان L1:
رشته زیر عضو زبان L1 می باشد
[tex]L =\{ a^{2n}b^{2n}a^{2n} \}[/tex]
اتفاقا این که مستقل از متنه!همون زبان معروف خودمونه: WW^R
(۱۱ اسفند ۱۳۸۹ ۰۵:۱۰ ب.ظ)۸۷۸۵۵۶۱۱ نوشته شده توسط: اعتراض به کلید سازمان سنجش-گروه مهندسی کامپیوتر کد ۱۲۷۷-سوال ۶۲ درس نظریه زبان هابله این زبانی که شما نوشتید مستقل از متن است و wwr میباشد دقت کنید این جوری نمیشه بگید که زبان مستقل از متن است یا نیست
مثال نقض برای اثبات مستقل از متن نبودن زبان L1:
رشته زیر عضو زبان L1 می باشد
[tex]L =\{ a^{2n}b^{2n}a^{2n} \}[/tex]
طول رشته زوج است و W1<>W2 می باشد(منطبق با صورت مساله)
رشته بالا مستقل از متن نمی باشد: چون در ابتدا حروف a را وارد پشته می کنیم(push) و بعد به همان تعداد حرف b از پشته می خوانیم(pop)، حال نوبت حروف a در انتهای رشته می باشد که چون تعداد a برای چک شدن با b از پشته خارج شده اند، دیگر به متغیر n دسترسی نداریم و نمی توانیم تعداد a های آخر رشته را بررسی کنیم. یعنی دیگر نمیدانیم در ابتدای رشته چه تعداد حرف a آمده است.(پس این زبان مستقل از متن نیست-بکمک یک پشته قابل تشخیص نیست)
توجه: زبان L در بالا به کمک لم پامپینگ(Pumping Lemmas) نیز قابل اثبات است که مستقل از متن نمی باشد.
پس زبان L1 در صورت سوال، باید بتواند زبان L(توضیح داده شده در بالا) را تشخیص دهد، و از آنجا که این زبان مستقل از متن نمی باشد(حساس به متن است)، پس زبان L1 هم نمی تواند مستقل از متن باشد.
گزینه ۳ صحیح می باشد(به اشتباه گزینه ۱ انتخاب شده است)
باید روی کل زبان تمرکز کنید . روی تعریف، این جوری سازمان سنجش هم از جوابتون زده میکنید
۱ . رشته نمیتونه طولش نامتناهی باشه فرض میکنیم طول رشتمون مثلا K هستش
۲ . مییدونیم هررشته که LL(K باشه حتما مستقل از متن هست
۳ . در نتیجه ما منتونیم رشته اول رو به طور کامل تو پشته بریزیم و موقع ریختن رشته دوم به طور غیر قطعی میریم و اولین حرف رشته اول رو چک میکنیم . اگه با هم برابر بودند که رشته پذیرفته نمیشه اگه برابر نبودند سراغ دومین حرف میریمو.....
درنتیجه گزینه ۱ میشه (وسط رشته یعنی جایی که تشخیص میدیم که رشته دوم داره ریخته میشه بصورت غیر قطعی تشخیص داده میشه)
این نظر رو تو یه تایپیک دیگه مطرح کردم که دوستان به واسطه مقایسه با WW ردش کردن منم پذیرفتم چون علمم بیشتر نمیکشید
این طرز فکر و از استادی پرسیدم و گفتند که این فکر کاملا درسته
همه جملات گفته شده در بالا از کتاب لینز گفته شده
اگه حواستید صفحاتشو میگم